A006666 Number of halving steps to reach 1 in '3x+1' problem, or -1 if this never happens.

0, 1, 5, 2, 4, 6, 11, 3, 13, 5, 10, 7, 7, 12, 12, 4, 9, 14, 14, 6, 6, 11, 11, 8, 16, 8, 70, 13, 13, 13, 67, 5, 18, 10, 10, 15, 15, 15, 23, 7, 69, 7, 20, 12, 12, 12, 66, 9, 17, 17, 17, 9, 9, 71, 71, 14, 22, 14, 22, 14, 14, 68, 68, 6, 19, 19, 19, 11, 11, 11, 65, 16, 73, 16, 11, 16

Offset: 1

Author

N. J. A. Sloane, Bill Gosper

Keywords

• nonn
• nice
• look
• easy

Comments

Equals the total number of steps to reach 1 under the modified '3x+1' map: T(n) = n/2 if n is even, (3n+1)/2 if n is odd (see A014682).

Pairs of consecutive integers of the same height occur infinitely often and in infinitely many different patterns (Garner 1985). - Joe Slater, May 24 2018

Examples

			2 -> 1 so a(2) = 1; 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1, with 5 halving steps, so a(3) = 5; 4 -> 2 -> 1 has two halving steps, so a(4) = 2; etc.
		

References

• R. K. Guy, Unsolved Problems in Number Theory, E16.
• J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010.
• 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
• David Eisenbud and Brady Haran, UNCRACKABLE? The Collatz Conjecture, Numberphile Video, 2016.
• Lynn E. Garner, On Heights in the Collatz 3n+1 Problem, Discrete Math. 55 (1985) 57-64.
• J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, m92 (1985), 3-23.
• Jeffrey C. Lagarias, The 3x+1 Problem: An Overview, arXiv:2111.02635 [math.NT], 2021.
• K. Matthews, The Collatz Conjecture
• Eric Weisstein's World of Mathematics, Collatz Problem
• Index entries for sequences related to 3x+1 (or Collatz) problem

Crossrefs

Cf. A006370, A006577, A006667 (tripling steps), A014682, A092892, A127789 (record indices of 2^a(n)/(3^A006667(n)*n)).

Programs

Haskell

a006666 = length . filter even . takeWhile (> 1) . (iterate a006370)
-- Reinhard Zumkeller, Oct 08 2011

Maple

# A014682
T:=proc(n) if n mod 2 = 0 then n/2 else (3*n+1)/2; fi; end;
# A006666
t1:=[0]:
for n from 2 to 100 do
L:=1; p := n;
while T(p) <> 1 do p:=T(p); L:=L+1; od:
t1:=[op(t1),L];
od: t1;

Mathematica

Table[Count[NestWhileList[If[OddQ[#],3#+1,#/2]&,n,#>1&],?(EvenQ[#]&)], {n,80}] (* _Harvey P. Dale, Sep 30 2011 *)

PARI

a(n)=my(t); while(n>1, if(n%2, n=3*n+1, n>>=1; t++)); t \\ Charles R Greathouse IV, Jun 21 2017

Python

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

Formula

A092892(a(n)) = n and A092892(m) <> n for m < a(n). - Reinhard Zumkeller, Mar 14 2014

a(2^n) = n. - Bob Selcoe, Apr 16 2015

a(n) = ceiling(log(n*3^A006667(n))/log(2)). - Joe Slater, Aug 30 2017

a(2^k-1) = a(2^(k+1)-1)-1, for odd k>1. - Joe Slater, May 17 2018

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

Extensions

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

Name edited by M. F. Hasler, May 07 2018