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

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,3

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

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

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

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

Formula

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

Example

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.

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

Prog

(Haskell)
a006666 = length . filter even . takeWhile (> 1) . (iterate a006370)
-- Reinhard Zumkeller, Oct 08 2011
(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
(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

Crossrefs

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

Sequence in context: A112597 A257700 A334206 * A267830 A163334 A029683

Adjacent sequences: A006663 A006664 A006665 * A006667 A006668 A006669

Keyword

nonn,nice,look,easy

Author

N. J. A. Sloane, Bill Gosper

Extensions

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

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

Status

approved