

A006666


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


46



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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) 5764.
J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, m92 (1985), 323.
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^k1) = 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 n%2==0:
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: A202494 A112597 A257700 * 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



