A127886 -id:A127886 - cp's OEIS frontend

A127887 Indices of nonzero terms of A127886.

9, 18, 27, 28, 31, 33, 36, 37, 39, 41, 43, 47, 49, 50, 54, 55, 56, 57, 59, 62, 63, 65, 66, 71, 72, 73, 74, 78, 79, 82, 83, 86, 87, 89, 91, 94, 95, 97, 98, 99, 100, 103, 105, 107, 108, 109, 110, 111, 112, 114, 115, 118, 119, 121, 123, 124, 125, 126, 129, 130, 131, 132, 133, 134, 135, 137, 139, 142, 143, 144, 145

Offset: 1

David Applegate and N. J. A. Sloane, Feb 04 2007

nonn

These are the numbers for which allowing the choice of x/2 or 3x+1 in the "3x+1" iteration makes a difference in the minimal number of steps to reach 1.

Thus these are the n for which A006577(n) > A127885(n).

Antti Karttunen, Table of n, a(n) for n = 1..695 (computed from the b-files of A006577 and A127885)

Cf. A006577, A127885, A127886.

Position[#, k_ /; k > 0][[All, 1]] &@ Table[Length@ NestWhileList[If[OddQ@ #, 3 # + 1, #/2] &, n, # > 1 &] - Length@ NestWhileList[Flatten[# /. {k_ /; OddQ@ k :> 3 k + 1, k_ /; EvenQ@ k :> {k/2, 3 k + 1}}] &, {n}, FreeQ[#, 1] &], {n, 126}] (* Michael De Vlieger, Aug 20 2017 *)

More terms from Antti Karttunen, Aug 18 2017

A006577 Number of halving and tripling steps to reach 1 in '3x+1' problem, or -1 if 1 is never reached.

Original entry on oeis.org

0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24, 24, 11, 11, 112, 112, 19, 32, 19, 32, 19, 19, 107, 107, 6, 27, 27, 27, 14, 14, 14, 102, 22

Offset: 1

N. J. A. Sloane, Bill Gosper

The 3x+1 or Collatz problem is as follows: start with any number n. If n is even, divide it by 2, otherwise multiply it by 3 and add 1. Do we always reach 1? This is a famous unsolved problem. It is conjectured that the answer is yes.
It seems that about half of the terms satisfy a(i) = a(i+1). For example, up to 10000000, 4964705 terms satisfy this condition.
n is an element of row a(n) in triangle A127824. - Reinhard Zumkeller, Oct 03 2012
The number of terms that satisfy a(i) = a(i+1) for i being a power of ten from 10^1 through 10^10 are: 0, 31, 365, 4161, 45022, 477245, 4964705, 51242281, 526051204, 5378743993. - John Mason, Mar 02 2018
5 seems to be the only number whose value matches its total number of steps (checked to n <= 10^9). - Peter Woodward, Feb 15 2021

			a(5)=5 because the trajectory of 5 is (5,16,8,4,2,1).

R. K. Guy, Unsolved Problems in Number Theory, E16.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
David Eisenbud and Brady Haran, UNCRACKABLE? The Collatz Conjecture, Numberphile video, 2016.
Geometry.net, Links on Collatz Problem
Christian Hercher, There are no Collatz m-Cycles with m <= 91, J. Int. Seq. (2023) Vol. 26, Article 23.3.5.
Jason Holt, Log-log plot of first billion terms
Jason Holt, Plot of 1 billion values of the number of steps to drop below n (A060445), log scale on x axis
Jason Holt, Plot of 10 billion values of the number of steps to drop below n (A060445), log scale on x axis
A. Krowne, Collatz problem, PlanetMath.org.
J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
J. C. Lagarias, How random are 3x+1 function iterates?, in The Mathemagician and the Pied Puzzler - A Collection in Tribute to Martin Gardner, Ed. E. R. Berlekamp and T. Rogers, A. K. Peters, 1999, pp. 253-266.
J. C. Lagarias, The 3x+1 Problem: an annotated bibliography, II (2000-2009), arXiv:0608208 [math.NT], 2006-2012.
J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010.
Jeffrey C. Lagarias, The 3x+1 Problem: An Overview, arXiv:2111.02635 [math.NT], 2021.
M. Le Brun, Email to N. J. A. Sloane, Jul 1991
Mathematical BBS, Biblography on Collatz Sequence
P. Picart, Algorithme de Collatz et conjecture de Syracuse
E. Roosendaal, On the 3x+1 problem
J. L. Simons, On the nonexistence of 2-cycles for the 3x+1 problem, Math. Comp. 75 (2005), 1565-1572.
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 8.
G. Villemin's Almanach of Numbers, Cycle of Syracuse
Eric Weisstein's World of Mathematics, Collatz Problem
Wikipedia, Collatz Conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem

See A070165 for triangle giving trajectories of n = 1, 2, 3, ....
Cf. A006370, A125731, A127885, A127886, A008908, A112695, A135282, A208981, A025586.
See also A008884, A161021, A161022, A161023.

import Data.List (findIndex)
import Data.Maybe (fromJust)
a006577 n = fromJust $ findIndex (n `elem`) a127824_tabf
-- Reinhard Zumkeller, Oct 04 2012, Aug 30 2012

A006577 := proc(n)
        local a,traj ;
        a := 0 ;
        traj := n ;
        while traj > 1 do
                if type(traj,'even') then
                        traj := traj/2 ;
                else
                        traj := 3*traj+1 ;
                end if;
                a := a+1 ;
        end do:
        return a;
end proc: # R. J. Mathar, Jul 08 2012

f[n_] := Module[{a=n,k=0}, While[a!=1, k++; If[EvenQ[a], a=a/2, a=a*3+1]]; k]; Table[f[n],{n,4!}] (* Vladimir Joseph Stephan Orlovsky, Jan 08 2011 *)
Table[Length[NestWhileList[If[EvenQ[#],#/2,3#+1]&,n,#!=1&]]-1,{n,80}] (* Harvey P. Dale, May 21 2012 *)

a(n)=if(n<0,0,s=n; c=0; while(s>1,s=if(s%2,3*s+1,s/2); c++); c)

step(n)=if(n%2,3*n+1,n/2);
A006577(n)=if(n==1,0,A006577(step(n))+1); \\ Michael B. Porter, Jun 05 2010

def a(n):
    if n==1: return 0
    x=0
    while True:
        if n%2==0: n//=2
        else: n = 3*n + 1
        x+=1
        if n<2: break
    return x
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 05 2017

def A006577(n):
    ct = 0
    while n != 1: n = A006370(n); ct += 1
    return ct # Ya-Ping Lu, Feb 22 2024

collatz<-function(n) ifelse(n==1,0,1+ifelse(n%%2==0,collatz(n/2),collatz(3*n+1))); sapply(1:72, collatz) # Christian N. K. Anderson, Oct 09 2024

a(n) = A006666(n) + A006667(n).
a(n) = A112695(n) + 2 for n > 2. - Reinhard Zumkeller, Apr 18 2008
a(n) = A008908(n) - 1. - L. Edson Jeffery, Jul 21 2014
a(n) = A135282(n) + A208981(n) (after Alonso del Arte's comment in A208981), if 1 is reached, otherwise a(n) = -1. - Omar E. Pol, Apr 10 2022
a(n) = 2*A007814(n + 1) + a(A085062(n)) + 1 for n > 1. - Wing-Yin Tang, Jan 06 2025

More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001

"Escape clause" added to definition by N. J. A. Sloane, Jun 06 2017

A127885 a(n) = minimal number of steps to get from n to 1, where a step is x -> 3x+1 if x is odd, or x -> either x/2 or 3x+1 if x is even; or -1 if 1 is never reached.

Original entry on oeis.org

0, 1, 7, 2, 5, 8, 16, 3, 11, 6, 14, 9, 9, 17, 17, 4, 12, 12, 20, 7, 7, 15, 15, 10, 23, 10, 23, 10, 18, 18, 31, 5, 18, 13, 13, 13, 13, 21, 26, 8, 21, 8, 21, 16, 16, 16, 29, 11, 16, 16, 24, 11, 11, 24, 24, 11, 24, 19, 24, 19, 19, 32, 32, 6, 19, 19, 27, 14, 14, 14, 27, 14, 27, 14, 14, 22, 22, 27, 27, 9, 22, 22, 22, 9, 9, 22, 22, 17, 22, 17, 30, 17, 17, 30, 30, 12, 30, 17, 17, 17

Offset: 1

David Applegate and N. J. A. Sloane, Feb 04 2007

nonn

In contrast to the "3x+1" problem (see A006577), here you are free to choose either step if x is even.

See A125731 for the number of steps in the reverse direction, from 1 to n.

			Several early values use the path:
6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.
The first path where choosing 3x+1 for even x helps is:
9 -> 28 -> 85 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1.

M. J. Halm, Sequences (Re)discovered, Mpossibilities 81 (Aug. 2002), p. 1.

David Applegate, Table of n, a(n) for n = 1..1000
Index entries for sequences related to 3x+1 (or Collatz) problem

A127886 gives the difference between A006577 and this sequence.
Cf. A006577, A125731, A127887, A125195, A125686, A125719, A261870.
Cf. A290100 (size of the final set when using Alekseyev's algorithm).
Cf. also A257265.

# Code from David Applegate: Be careful - the function takes an iteration limit and returns the limit if it wasn't able to determine the answer (that is, if A127885(n,lim) == lim, all you know is that the value is >= lim). To use it, do manual iteration on the limit.
A127885 := proc(n,lim) local d,d2; options remember;
if (n = 1) then return 0; end if;
if (lim <= 0) then return 0; end if;
if (n > 2 ^ lim) then return lim; end if;
if (n mod 2 = 0) then
d := A127885(n/2,lim-1);
d2 := A127885(3*n+1,d);
if (d2 < d) then d := d2; end if;
else
d := A127885(3*n+1,lim-1);
end if;
return 1+d;
end proc;

Table[-1 + Length@ NestWhileList[Flatten[# /. {k_ /; OddQ@ k :> 3 k + 1, k_ /; EvenQ@ k :> {k/2, 3 k + 1}}] &, {n}, FreeQ[#, 1] &], {n, 126}] (* Michael De Vlieger, Aug 20 2017 *)

{ A127885(n) = my(S,k); S=[n]; k=0; while( S[1]!=1, k++; S=vecsort( concat(apply(x->3*x+1,S), apply(x->x\2, select(x->x%2==0,S) )),,8);  ); k } /* Max Alekseyev, Sep 03 2015 */

a(1) = 0; and for n > 1, if n is odd, a(n) = 1 + a(3n+1), and if n is even, a(n) = 1 + min(a(3n+1),a(n/2)). [But with a similar caveat as in A257265] - Antti Karttunen, Aug 20 2017

Escape clause added to definition by N. J. A. Sloane, Aug 20 2017

A291213 Start from the singleton set S = {n}, and unless 1 is already a member of S, generate on each iteration a new set where each odd number k is replaced by 3k+1, and each even number k is replaced by 3k+1 and k/2. a(n) is the total size of the set from the singleton through after the first iteration which has produced 1 as a member, inclusive.

Original entry on oeis.org

1, 3, 36, 6, 20, 72, 1168, 11, 216, 35, 576, 143, 111, 2422, 1657, 19, 336, 378, 6253, 66, 51, 1167, 820, 241, 24096, 180, 18805, 215, 3833, 3488, 368905, 31, 3460, 575, 426, 716, 576, 12387, 57556, 110, 10513, 83, 8948, 2303, 1782, 1656, 175195, 387, 1647

Offset: 1

Michael De Vlieger, Aug 26 2017

nonn

See comments at A290100.
A290100(n) is the size of the set at the last iteration, while this sequence is the sum of sizes of all generations including the last iteration.
A290100(n)/A291213(n) < 29/90 for n = {6, 67, 81, 92, 102, 153, 155, 165, 198, 201, 202, 204, 205, 217, 228, 235, 264, 265, 289, 299, 308, 309, 349, 353, 360, 396, 408, 434, ...}, with n = 6 the greatest observed difference. - Michael De Vlieger, Aug 30 2017

			For n = 5:
Generation   Set
1 (1 term)   5
2 (1 term)   16
3 (2 terms)  8, 49
4 (3 terms)  4, 25, 148
5 (5 terms)  2, 13, 74, 76, 445
6 (8 terms)  1, 7, 37, 38, 40, 223, 229, 1336
thus a(5) = 20 and A290100(5) = 8.

Michael De Vlieger, Table of n, a(n) for n = 1..450

Cf. A006577, A127885, A127886, A290100.

Table[Length@ Flatten@ NestWhileList[Union@ Flatten[# /. {k_ /; OddQ@ k :> 3 k + 1, k_ /; EvenQ@ k :> {k/2, 3 k + 1}}] &, {n}, FreeQ[#, 1] &], {n, 49}]

cp's OEIS Frontend

A127887 Indices of nonzero terms of A127886.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A006577 Number of halving and tripling steps to reach 1 in '3x+1' problem, or -1 if 1 is never reached.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

R

Formula

Extensions

A127885 a(n) = minimal number of steps to get from n to 1, where a step is x -> 3x+1 if x is odd, or x -> either x/2 or 3x+1 if x is even; or -1 if 1 is never reached.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica