login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006666 Number of halving steps to reach 1 in '3x+1' problem, or -1 if this never happens.
(Formerly M3733)
43

%I M3733

%S 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,

%T 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,

%U 71,71,14,22,14,22,14,14,68,68,6,19,19,19,11,11,11,65,16,73,16,11,16

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

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

%C A092892(a(n)) = n and A092892(m) <> n for m < a(n). - _Reinhard Zumkeller_, Mar 14 2014

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

%D R. K. Guy, Unsolved Problems in Number Theory, E16.

%D J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A006666/b006666.txt">Table of n, a(n) for n = 1..10000</a>

%H David Eisenbud and Brady Haran, <a href="https://www.youtube.com/watch?v=5mFpVDpKX70">UNCRACKABLE? The Collatz Conjecture</a>, Numberphile Video, 2016.

%H Lynn E. Garner, <a href="https://doi.org/10.1016/S0012-365X(85)80020-0">On Heights in the Collatz 3n+1 Problem</a>, Discrete Math. 55 (1985) 57-64.

%H J. C. Lagarias, <a href="http://www.cecm.sfu.ca/organics/papers/lagarias/paper/html/paper.html">The 3x+1 problem and its generalizations</a>, Amer. Math. Monthly, m92 (1985), 3-23.

%H K. Matthews, <a href="http://www.numbertheory.org/php/collatz.html">The Collatz Conjecture</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CollatzProblem.html">Collatz Problem</a>

%H <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>

%F a(2^n) = n. - _Bob Selcoe_, Apr 16 2015

%F a(n) = ceiling(log(n*3^A006667(n))/log(2)). - _Joe Slater_, Aug 30 2017

%F a(2^k-1) = a(2^(k+1)-1)-1, for odd k>1. - _Joe Slater_, May 17 2018

%e 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.

%p # A014682

%p T:=proc(n) if n mod 2 = 0 then n/2 else (3*n+1)/2; fi; end;

%p # A006666

%p t1:=[0]:

%p for n from 2 to 100 do

%p L:=1; p := n;

%p while T(p) <> 1 do p:=T(p); L:=L+1; od:

%p t1:=[op(t1),L];

%p od: t1;

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

%o (Haskell)

%o a006666 = length . filter even . takeWhile (> 1) . (iterate a006370)

%o -- _Reinhard Zumkeller_, Oct 08 2011

%o (Python)

%o def a(n):

%o if n==1: return 0

%o x=0

%o while True:

%o if n%2==0:

%o n/=2

%o x+=1

%o else: n = 3*n + 1

%o if n<2: break

%o return x

%o print [a(n) for n in xrange(1, 101)] # _Indranil Ghosh_, Apr 14 2017

%o (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

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

%K nonn,nice,look,easy

%O 1,3

%A _N. J. A. Sloane_, _Bill Gosper_

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

%E Name edited by _M. F. Hasler_, May 07 2018

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 20 10:09 EST 2019. Contains 329334 sequences. (Running on oeis4.)