cp's OEIS Frontend

A005186 a(n) is the number of integers m which take n steps to reach 1 in '3x+1' problem.

%I A005186 M0305 #144 Sep 07 2024 16:27:54
%S A005186 1,1,1,1,1,2,2,4,4,6,6,8,10,14,18,24,29,36,44,58,72,91,113,143,179,
%T A005186 227,287,366,460,578,732,926,1174,1489,1879,2365,2988,3780,4788,6049,
%U A005186 7628,9635,12190,15409,19452,24561,31025,39229,49580,62680,79255,100144
%N A005186 a(n) is the number of integers m which take n steps to reach 1 in '3x+1' problem.
%C A005186 Appears to settle into approximately exponential growth after about 25 terms or so with a ratio between adjacent terms of roughly 1.264. - _Howard A. Landman_, May 24 2003
%C A005186 _David W. Wilson_ (Jun 10 2003) gives a heuristic argument that the constant should be the largest eigenvalue of the matrix [ 1 0 0 1 0 0 / 0 0 0 0 1/3 0 / 0 1 0 0 1 0 / 0 0 0 0 1/3 0 / 0 0 1 0 0 1 / 0 0 0 0 1/3 0 ], which is (3 + sqrt(21))/6 = 1.2637626... = A176014.
%C A005186 Merlini and Sala (1999) deduce the value (1 + sqrt(7/3))/2 (A176014) for the asymptotic ratio a(n+1)/a(n) for n -> oo and call this "Collatz's constant". This is the same value as the constant mentioned above, see the "Heuristic argument for the asymptotic value (3 + sqrt(21))/6 of the ratio a(n+1)/a(n)" note in the Links section. - _Markus Sigg_, Nov 27 2020
%D A005186 R. K. Guy, personal communication.
%D A005186 J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010; see p. 33.
%D A005186 Danilo Merlini and Nicoletta Sala, On the Fibonacci's Attractor and the Long Orbits in the 3n+1 Problem, International Journal of Chaos Theory and Applications, Vol. 4, No. 2-3 (1999), 75-84.
%D A005186 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005186 Markus Sigg, <a href="/A005186/b005186.txt">Table of n, a(n) for n = 0..125</a> (first 71 terms from T. D. Noe, terms up to n = 120 from Bert Dobbelaere).
%H A005186 S. N. Anderson, <a href="http://www.jstor.org/stable/3617045">Struggling with the 3x+1 problem</a>, Math. Gazette, 71 (1987), 271-274.
%H A005186 S. N. Anderson, <a href="/A005186/a005186_1.pdf">Struggling with the 3x+1 problem</a>, Math. Gazette, 71 (1987), 271-274. [Annotated scanned copy]
%H A005186 R. K. Guy, S. N. Anderson, and N. J. A. Sloane, <a href="/A005186/a005186.pdf">Correspondence</a>, 1988.
%H A005186 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 A005186 Wolfdieter Lang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Lang/lang6.html">On Collatz Words, Sequences, and Trees</a>, Journal of Integer Sequences, Vol 17 (2014), Article 14.11.7.
%H A005186 Hugo Pfoertner, <a href="/A005186/a005186.png">Ratio of successive terms</a>, illustration of deviation from (3+sqrt(21))/6.
%H A005186 Markus Sigg, <a href="/A005186/a005186_4.pdf">Heuristic argument for the asymptotic value (3+sqrt(21))/6 of the ratio a(n+1)/a(n)</a>.
%H A005186 Wikipedia, <a href="http://en.wikipedia.org/wiki/File:Collatz-graph-20-iterations.svg">The beginning of the Collatz directed graph</a>
%H A005186 <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%t A005186 (* This program is not suitable to compute more than 20 terms *) maxiSteps = 20; mMaxi = 2*10^6; Clear[a]; a[_] = 0; steps[m_] := steps[m] = Module[{n = m, ns = 0}, While[n != 1, If[Mod[n, 2] == 0, n = n/2, n = 3*n+1]; ns++]; ns]; Do[sn = steps[m]; If[sn <= maxiSteps, a[sn] = a[sn]+1; Print["m = ", m, " a(", sn, ") = ", a[sn]]], {m, 1, mMaxi}]; Table[a[n], {n, 0, maxiSteps}] (* _Jean-François Alcover_, Oct 18 2013 *)
%t A005186 (* 60 terms in under a minute *) s = {1}; t = Join[{1}, Table[s = Union[2*s, (Select[s, Mod[#, 3] == 1 && OddQ[(# - 1)/3] && (# - 1)/3 > 1 &] - 1)/3]; Length[s], {n, 60}]] (* _T. D. Noe_, Oct 18 2013 *)
%o A005186 (Perl) #!/usr/bin/perl @old = ( 1 ); while (1) { print scalar(@old), " "; @new = ( ); foreach $n (@old) { $used{$n} = 1; if (($n % 6) == 4) { $m = ($n-1)/3; push(@new,$m) unless ($used{$m}); } $m = $n + $n; push(@new,$m) unless ($used{$m}); } @old = @new; }
%o A005186 (PARI) first(n)=my(v=vector(n+1), u=[1], old=u, w); v[1]=1; for(i=1, n, w=List(); for(j=1, #u, listput(w, 2*u[j]); if(u[j]%6==4, listput(w, u[j]\3))); old=setunion(old, u); u=setminus(Set(w), old); v[i+1]=#u); v \\ _Charles R Greathouse IV_, Jun 26 2017
%o A005186 (PARI) first(n)={my(v=Vec([1, 1, 1, 1, 1], n+1), u=[16]); for(i=5, n, u=concat(2*u, [x\3 | x<-u, x%6==4 ]); v[i+1]=#u); v} \\ _Joe Slater_, Sep 01 2024
%o A005186 (Python)
%o A005186 def search(x,d,lst):
%o A005186     while d>0:
%o A005186         lst[d]+=1
%o A005186         if x%6==4 and x>4:
%o A005186             search(x//3,d-1,lst)
%o A005186         x*=2
%o A005186         d-=1
%o A005186     lst[d]+=1
%o A005186 def A005186_list(n_max):
%o A005186     lst=[0]*(n_max+1)
%o A005186     search(1,n_max,lst)
%o A005186     return lst[::-1]
%o A005186 # _Bert Dobbelaere_, Sep 09 2018
%Y A005186 Cf. A088975, A176014, A176866.
%K A005186 nonn,easy,nice
%O A005186 0,6
%A A005186 _N. J. A. Sloane_, _R. K. Guy_
%E A005186 More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001