|
%I M0305 #131 Nov 05 2021 09:35:08
%S 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 227,287,366,460,578,732,926,1174,1489,1879,2365,2988,3780,4788,6049,
%U 7628,9635,12190,15409,19452,24561,31025,39229,49580,62680,79255,100144
%N a(n) is the number of integers m which take n steps to reach 1 in '3x+1' problem.
%C 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 _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 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 R. K. Guy, personal communication.
%D J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010; see p. 33.
%D 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 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Bert Dobbelaere, <a href="/A005186/b005186.txt">Table of n, a(n) for n = 0..120</a> (first 71 terms from T. D. Noe)
%H 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 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 R. K. Guy, S. N. Anderson, and N. J. A. Sloane, <a href="/A005186/a005186.pdf">Correspondence</a>, 1988.
%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 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 Hugo Pfoertner, <a href="/A005186/a005186.png">Ratio of successive terms</a>, illustration of deviation from (3+sqrt(21))/6.
%H 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 Wikipedia, <a href="http://en.wikipedia.org/wiki/File:Collatz-graph-20-iterations.svg">The beginning of the Collatz directed graph</a>
%H <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%t (* 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 (* 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 (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 (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 (Python)
%o def search(x,d,lst):
%o while d>0:
%o lst[d]+=1
%o if x%6==4 and x>4:
%o search(x//3,d-1,lst)
%o x*=2
%o d-=1
%o lst[d]+=1
%o def A005186_list(n_max):
%o lst=[0]*(n_max+1)
%o search(1,n_max,lst)
%o return lst[::-1]
%o # _Bert Dobbelaere_, Sep 09 2018
%Y Cf. A088975, A176014, A176866.
%K nonn,easy,nice
%O 0,6
%A _N. J. A. Sloane_, _R. K. Guy_
%E More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001
|
