|
| |
|
|
A005186
|
|
a(n) is the number of integers m which take n steps to reach 1 in '3x+1' problem.
(Formerly M0305)
|
|
20
|
|
|
|
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, 227, 287, 366, 460, 578, 732, 926, 1174, 1489, 1879, 2365, 2988, 3780, 4788, 6049, 7628, 9635, 12190, 15409, 19452, 24561, 31025, 39229, 49580, 62680, 79255, 100144
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,6
|
|
|
COMMENTS
|
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
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.
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
|
|
|
REFERENCES
|
R. K. Guy, personal communication.
J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010; see p. 33.
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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
|
|
|
MATHEMATICA
|
(* 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 *)
(* 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 *)
|
|
|
PROG
|
(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; }
(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
(Python)
def search(x, d, lst):
while d>0:
lst[d]+=1
if x%6==4 and x>4:
search(x//3, d-1, lst)
x*=2
d-=1
lst[d]+=1
lst=[0]*(n_max+1)
search(1, n_max, lst)
return lst[::-1]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001
|
|
|
STATUS
|
approved
|
| |
|
|
