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

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

Offset: 0

Author

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

Keywords

• nonn
• easy
• nice

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

• Markus Sigg, Table of n, a(n) for n = 0..125 (first 71 terms from T. D. Noe, terms up to n = 120 from Bert Dobbelaere).
• 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.
• Jeffrey C. Lagarias, The 3x+1 Problem: An Overview, arXiv:2111.02635 [math.NT], 2021.
• Wolfdieter Lang, On Collatz Words, Sequences, and Trees, Journal of Integer Sequences, Vol 17 (2014), Article 14.11.7.
• Hugo Pfoertner, Ratio of successive terms, illustration of deviation from (3+sqrt(21))/6.
• Markus Sigg, Heuristic argument for the asymptotic value (3+sqrt(21))/6 of the ratio a(n+1)/a(n).
• Wikipedia, The beginning of the Collatz directed graph
• Index entries for sequences related to 3x+1 (or Collatz) problem

Crossrefs

Cf. A088975, A176014, A176866.

Programs

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 *)

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

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

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; }

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
def A005186_list(n_max):
    lst=[0]*(n_max+1)
    search(1,n_max,lst)
    return lst[::-1]
# Bert Dobbelaere, Sep 09 2018

Extensions

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