|
|
A006666
|
|
Number of halving steps to reach 1 in '3x+1' problem, or -1 if this never happens.
(Formerly M3733)
|
|
47
|
|
|
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) 57-64.
J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, m92 (1985), 3-23.
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
|
|
|
|