login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005186 a(n) = number of m which take n steps to reach 1 in '3x+1' problem.
(Formerly M0305)
11
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

REFERENCES

R. K. Guy, personal communication.

J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010; see p. 33.

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

LINKS

T. D. Noe, Table of n, a(n) for n = 0..70

S. N. Anderson, Struggling with the 3x+1 problem, Math. Gazette, 71 (1987), 271-274.

S. N. Anderson, Struggling with the 3x+1 problem, Math. Gazette, 71 (1987), 271-274. [Annotated scanned copy]

R. K. Guy, S. N. Anderson, and N. J. A. Sloane, Correspondence, 1988.

Wolfdieter Lang, On Collatz Words, Sequences, and Trees, Journal of Integer Sequences, Vol 17 (2014), Article 14.11.7.

Wikipedia, The beginning of the Collatz directed graph

Index entries for sequences related to 3x+1 (or Collatz) problem

FORMULA

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

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

CROSSREFS

Cf. A088975.

Sequence in context: A052928 A137501 A285999 * A259881 A238132 A278296

Adjacent sequences:  A005183 A005184 A005185 * A005187 A005188 A005189

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane, R. K. Guy

EXTENSIONS

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

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified September 24 04:27 EDT 2017. Contains 292403 sequences.