|
%I M4323 #194 Mar 19 2024 13:48:35
%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
%C 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
%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 Christian Hercher, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Hercher/hercher5.html">There are no Collatz m-Cycles with m <= 91</a>, J. Int. Seq. (2023) Vol. 26, Article 23.3.5.
%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, <a href="https://planetmath.org/collatzproblem">Collatz problem</a>, PlanetMath.org.
%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 Jeffrey C. Lagarias, <a href="https://arxiv.org/abs/2111.02635">The 3x+1 Problem: An Overview</a>, arXiv:2111.02635 [math.NT], 2021.
%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 N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, p. 8.
%H G. Villemin's Almanach of Numbers, <a href="http://translate.google.com/translate?hl=en&sl=fr&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="https://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
%F 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
%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 range(1, 101)]) # _Indranil Ghosh_, Jun 05 2017
%o (Python)
%o def A006577(n):
%o ct = 0
%o while n != 1: n = A006370(n); ct += 1
%o return ct # _Ya-Ping Lu_, Feb 22 2024
%Y See A070165 for triangle giving trajectories of n = 1, 2, 3, ....
%Y Cf. A006370, A125731, A127885, A127886, A008908, A112695, A135282, A208981.
%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
|
