A006667 Number of tripling steps to reach 1 from n in '3x+1' problem, or -1 if 1 is never reached.

0, 0, 2, 0, 1, 2, 5, 0, 6, 1, 4, 2, 2, 5, 5, 0, 3, 6, 6, 1, 1, 4, 4, 2, 7, 2, 41, 5, 5, 5, 39, 0, 8, 3, 3, 6, 6, 6, 11, 1, 40, 1, 9, 4, 4, 4, 38, 2, 7, 7, 7, 2, 2, 41, 41, 5, 10, 5, 10, 5, 5, 39, 39, 0, 8, 8, 8, 3, 3, 3, 37, 6, 42, 6, 3, 6, 6, 11, 11, 1, 6, 40, 40, 1, 1, 9, 9, 4, 9, 4, 33, 4, 4, 38

Offset: 1

Author

N. J. A. Sloane and Bill Gosper

Keywords

• nonn
• nice
• hear

Comments

A075680, which gives the values for odd n, isolates the essential behavior of this sequence. - T. D. Noe, Jun 01 2006

A033959 and A033958 give record values and where they occur. - Reinhard Zumkeller, Jan 08 2014

References

• J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 204, Problem 22.
• R. K. Guy, Unsolved Problems in Number Theory, E16.
• 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 = 1..10000
• J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
• Eric Weisstein's World of Mathematics, Collatz Problem.
• Wikipedia, Collatz conjecture
• Index entries for sequences related to 3x+1 (or Collatz) problem

Crossrefs

Equals A078719(n)-1.

Cf. A000079, A000265, A006370, A006577, A006666 (halving steps), A092893, A127789, A139391, A209229.

Programs

Haskell

a006667 = length . filter odd . takeWhile (> 2) . (iterate a006370)
a006667_list = map a006667 [1..]
-- Reinhard Zumkeller, Oct 08 2011

Maple

a:= proc(n) option remember; `if`(n<2, 0,
      `if`(n::even, a(n/2), 1+a(3*n+1)))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 08 2023

Mathematica

Table[Count[Differences[NestWhileList[If[EvenQ[#],#/2,3#+1]&,n,#>1&]], ?Positive], {n,100}] (* _Harvey P. Dale, Nov 14 2011 *)

PARI

for(n=2,100,s=n; t=0; while(s!=1,if(s%2==0,s=s/2,s=(3*s+1)/2; t++); if(s==1,print1(t,","); ); ))

Python

def a(n):
    if n==1: return 0
    x=0
    while True:
        if n%2==0: n/=2
        else:
            n = 3*n + 1
            x+=1
        if n<2: break
    return x
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Apr 14 2017

Formula

a(1) = 0, a(n) = a(n/2) if n is even, a(n) = a(3n+1)+1 if n>1 is odd. The Collatz conjecture is that this defines a(n) for all n >= 1.

a(n) = A078719(n) - 1; a(A000079(n))=0; a(A062052(n))=1; a(A062053(n))=2; a(A062054(n))=3; a(A062055(n))=4; a(A062056(n))=5; a(A062057(n))=6; a(A062058(n))=7; a(A062059(n))=8; a(A062060(n))=9. - Reinhard Zumkeller, Oct 08 2011

a(n*2^k) = a(n), for all k >= 0. - L. Edson Jeffery, Aug 11 2014

a(n) = floor(log(2^A006666(n)/n)/log(3)). - Joe Slater, Aug 30 2017

a(n) = a(A085062(n)) + A007814(n+1) for n >= 2. - Alan Michael Gómez Calderón, Feb 07 2025

From Alan Michael Gómez Calderón, Mar 31 2025: (Start)

a(n) = a(A139391(n)) + (n mod 2) for n >= 2;

a(n) = a(A139391(A000265(n))) - A209229(n) + 1 for n >= 2;

a(n) = a(A000265(A139391(n))) + (n mod 2) for n >= 2. (End)

Extensions

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

"Escape clause" added to definition by N. J. A. Sloane, Jun 06 2017