A008908 a(n) = (1 + number of halving and tripling steps to reach 1 in the Collatz (3x+1) problem), or -1 if 1 is never reached.

1, 2, 8, 3, 6, 9, 17, 4, 20, 7, 15, 10, 10, 18, 18, 5, 13, 21, 21, 8, 8, 16, 16, 11, 24, 11, 112, 19, 19, 19, 107, 6, 27, 14, 14, 22, 22, 22, 35, 9, 110, 9, 30, 17, 17, 17, 105, 12, 25, 25, 25, 12, 12, 113, 113, 20, 33, 20, 33, 20, 20, 108, 108, 7, 28, 28, 28, 15, 15, 15, 103

Offset: 1

Author

N. J. A. Sloane, Bill Gosper

Keywords

• nonn
• nice
• look

Comments

The number of steps (iterations of the map A006370) to reach 1 is given by A006577, this sequence counts 1 more. - M. F. Hasler, Nov 05 2017

When Collatz 3N+1 function is seen as an isometry over the dyadics, the halving step necessarily following each tripling is not counted, hence N -> N/2, if even, but N -> (3N+1)/2, if odd. Counting iterations of this map until reaching 1 leads to sequence A064433. - Michael Vielhaber (vielhaber(AT)gmail.com), Nov 18 2009

References

• R. K. Guy, Unsolved Problems in Number Theory, E16.

Links

• Reinhard Zumkeller, 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.
• Nitrxgen, Collatz Calculator
• Wikipedia, Collatz conjecture
• Index entries for sequences related to 3x+1 (or Collatz) problem

Crossrefs

Cf. A006577, A006370, A006667, A075677.

Programs

Haskell

a008908 = length . a070165_row
-- Reinhard Zumkeller, May 11 2013, Aug 30 2012, Jul 19 2011

Maple

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

Mathematica

Table[Length[NestWhileList[If[EvenQ[ # ], #/2, 3 # + 1] &, i, # != 1 &]], {i, 75}]

PARI

a(n)=my(c=1); while(n>1, n=if(n%2, 3*n+1, n/2); c++); c \\ Charles R Greathouse IV, May 18 2015

Python

def a(n):
    if n==1: return 1
    x=1
    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 15 2017

Formula

a(n) = A006577(n) + 1.

a(n) = f(n,1) with f(n,x) = if n=1 then x else f(A006370(n),x+1).

a(A033496(n)) = A159999(A033496(n)). - Reinhard Zumkeller, May 04 2009

a(n) = A006666(n) + A078719(n).

a(n) = length of n-th row in A070165. - Reinhard Zumkeller, May 11 2013

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

Edited by M. F. Hasler, Nov 05 2017