This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006577 Number of halving and tripling steps to reach 1 in '3x+1' problem, or -1 if 1 is never reached.
(Formerly M4323)

%I M4323

%S 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,

%T 18,18,18,106,5,26,13,13,21,21,21,34,8,109,8,29,16,16,16,104,11,24,24,

%U 24,11,11,112,112,19,32,19,32,19,19,107,107,6,27,27,27,14,14,14,102,22

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

%C 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.

%C It seems that about half of the terms satisfy a(i) = a(i+1). For example, up to 10000000, 4964705 terms satisfy this condition.

%C n is an element of row a(n) in triangle A127824. - _Reinhard Zumkeller_, Oct 03 2012

%C 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

%D R. K. Guy, Unsolved Problems in Number Theory, E16.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H N. J. A. Sloane, <a href="/A006577/b006577.txt">Table of n, a(n) for n = 1..10000</a>

%H David Eisenbud and Brady Haran, <a href="https://www.youtube.com/watch?v=5mFpVDpKX70">UNCRACKABLE? The Collatz Conjecture</a>, Numberphile video, 2016.

%H Geometry.net, <a href="http://www.geometry.net/theorems_and_conjectures/collatz_problem.html">Links on Collatz Problem</a>

%H Jason Holt, <a href="/A006577/a006577_1Blog.png">Log-log plot of first billion terms</a>

%H Jason Holt, <a href="/A006577/a006577_1B.png">Plot of 1 billion values of the number of steps to drop below n</a> (A060445), log scale on x axis

%H Jason Holt, <a href="/A006577/a006577_10B.png">Plot of 10 billion values of the number of steps to drop below n</a> (A060445), log scale on x axis

%H A. Krowne, PlanetMath.org, <a href="http://planetmath.org/encyclopedia/CollatzProblem.html">Collatz problem</a>

%H J. C. Lagarias, <a href="http://www.cecm.sfu.ca/organics/papers/lagarias/paper/html/paper.html">The 3x+1 problem and its generalizations</a>, Amer. Math. Monthly, 92 (1985), 3-23.

%H J. C. Lagarias, <a href="http://www.cfrd.cl/~moises/DVD/05Bibliografia%20-%20Geometria%20Sagrada/Matematica%20Recreativa/Martin%20Gardner/Martin%20Gardner%20-%20The%20Mathemagician%20and%20Pied%20Puzzler%20-%20A%20Collection%20in%20Tribute%20to%20Martin%20Gardner.pdf">How random are 3x+1 function iterates?</a>, 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.

%H J. C. Lagarias, <a href="http://arxiv.org/abs/math/0608208">The 3x+1 Problem: an annotated bibliography, II (2000-2009)</a>, arXiv:0608208 [math.NT], 2006-2012.

%H J. C. Lagarias, ed., <a href="http://www.ams.org/bookstore-getitem/item=mbk-78">The Ultimate Challenge: The 3x+1 Problem</a>, Amer. Math. Soc., 2010.

%H M. Le Brun, <a href="/A006577/a006577.pdf">Email to N. J. A. Sloane, Jul 1991</a>

%H Mathematical BBS, <a href="http://felix.unife.it/Root/d-Mathematics/d-Number-theory/b-3x+1">Biblography on Collatz Sequence</a>

%H P. Picart, <a href="http://trucsmaths.free.fr/js_syracuse.htm">Algorithme de Collatz et conjecture de Syracuse</a>

%H E. Roosendaal, <a href="http://www.ericr.nl/wondrous/index.html">On the 3x+1 problem</a>

%H J. L. Simons, <a href="http://dx.doi.org/10.1090/S0025-5718-04-01728-4">On the nonexistence of 2-cycles for the 3x+1 problem</a>, Math. Comp. 75 (2005), 1565-1572.

%H G. Villemin's Almanach of Numbers, <a href="http://translate.google.com/translate?hl=en&amp;sl=fr&amp;u=http://villemin.gerard.free.fr/Wwwgvmm/Iteration/Syracuse.htm#top">Cycle of Syracuse</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CollatzProblem.html">Collatz Problem</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Collatz_conjecture">Collatz Conjecture</a>

%H <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>

%F a(n) = A006666(n) + A006667(n).

%F a(n) = A112695(n) + 2 for n > 2. - _Reinhard Zumkeller_, Apr 18 2008

%F a(n) = A008908(n) - 1. - _L. Edson Jeffery_, Jul 21 2014

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

%p A006577 := proc(n)

%p local a,traj ;

%p a := 0 ;

%p traj := n ;

%p while traj > 1 do

%p if type(traj,'even') then

%p traj := traj/2 ;

%p else

%p traj := 3*traj+1 ;

%p end if;

%p a := a+1 ;

%p end do:

%p return a;

%p end proc: # _R. J. Mathar_, Jul 08 2012

%t 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 *)

%t Table[Length[NestWhileList[If[EvenQ[#],#/2,3#+1]&,n,#!=1&]]-1,{n,80}] (* _Harvey P. Dale_, May 21 2012 *)

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

%o (PARI) step(n)=if(n%2,3*n+1,n/2);

%o A006577(n)=if(n==1,0,A006577(step(n))+1); \\ _Michael B. Porter_, Jun 05 2010

%o (Haskell)

%o import Data.List (findIndex)

%o import Data.Maybe (fromJust)

%o a006577 n = fromJust $ findIndex (n `elem`) a127824_tabf

%o -- _Reinhard Zumkeller_, Oct 04 2012, Aug 30 2012

%o (Python)

%o def a(n):

%o if n==1: return 0

%o x=0

%o while True:

%o if n%2==0: n/=2

%o else: n = 3*n + 1

%o x+=1

%o if n<2: break

%o return x

%o print [a(n) for n in xrange(1, 101)] # _Indranil Ghosh_, Jun 05 2017

%Y See A070165 for triangle giving trajectories of n = 1, 2, 3, ....

%Y Cf. A006370, A125731, A127885, A127886, A008908, A112695.

%Y See also A008884, A161021, A161022, A161023.

%K nonn,nice,easy,hear,look

%O 1,3

%A _N. J. A. Sloane_, _Bill Gosper_

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

%E "Escape clause" added to definition by _N. J. A. Sloane_, Jun 06 2017

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 22 16:25 EST 2019. Contains 329396 sequences. (Running on oeis4.)