cp's OEIS Frontend

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

%I A006666 M3733 #141 Feb 16 2025 08:32:30
%S A006666 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 A006666 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 A006666 71,71,14,22,14,22,14,14,68,68,6,19,19,19,11,11,11,65,16,73,16,11,16
%N A006666 Number of halving steps to reach 1 in '3x+1' problem, or -1 if this never happens.
%C A006666 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 A006666 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 A006666 R. K. Guy, Unsolved Problems in Number Theory, E16.
%D A006666 J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010.
%D A006666 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006666 T. D. Noe, <a href="/A006666/b006666.txt">Table of n, a(n) for n = 1..10000</a>
%H A006666 David Eisenbud and Brady Haran, <a href="https://www.youtube.com/watch?v=5mFpVDpKX70">UNCRACKABLE? The Collatz Conjecture</a>, Numberphile Video, 2016.
%H A006666 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 A006666 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 A006666 Jeffrey C. Lagarias, <a href="https://arxiv.org/abs/2111.02635">The 3x+1 Problem: An Overview</a>, arXiv:2111.02635 [math.NT], 2021.
%H A006666 K. Matthews, <a href="http://www.numbertheory.org/php/collatz.html">The Collatz Conjecture</a>
%H A006666 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CollatzProblem.html">Collatz Problem</a>
%H A006666 <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%F A006666 A092892(a(n)) = n and A092892(m) <> n for m < a(n). - _Reinhard Zumkeller_, Mar 14 2014
%F A006666 a(2^n) = n. - _Bob Selcoe_, Apr 16 2015
%F A006666 a(n) = ceiling(log(n*3^A006667(n))/log(2)). - _Joe Slater_, Aug 30 2017
%F A006666 a(2^k-1) = a(2^(k+1)-1)-1, for odd k>1. - _Joe Slater_, May 17 2018
%F A006666 a(n) = a(A085062(n)) + A007814(n+1) + 1 for n >= 2. - _Alan Michael Gómez Calderón_, Feb 01 2025
%e A006666 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 A006666 # A014682
%p A006666 T:=proc(n) if n mod 2 = 0 then n/2 else (3*n+1)/2; fi; end;
%p A006666 # A006666
%p A006666 t1:=[0]:
%p A006666 for n from 2 to 100 do
%p A006666 L:=1; p := n;
%p A006666 while T(p) <> 1 do p:=T(p); L:=L+1; od:
%p A006666 t1:=[op(t1),L];
%p A006666 od: t1;
%t A006666 Table[Count[NestWhileList[If[OddQ[#],3#+1,#/2]&,n,#>1&],_?(EvenQ[#]&)], {n,80}] (* _Harvey P. Dale_, Sep 30 2011 *)
%o A006666 (Haskell)
%o A006666 a006666 = length . filter even . takeWhile (> 1) . (iterate a006370)
%o A006666 -- _Reinhard Zumkeller_, Oct 08 2011
%o A006666 (Python)
%o A006666 def a(n):
%o A006666     if n==1: return 0
%o A006666     x=0
%o A006666     while True:
%o A006666         if not n%2:
%o A006666             n//=2
%o A006666             x+=1
%o A006666         else: n = 3*n + 1
%o A006666         if n<2: break
%o A006666     return x
%o A006666 print([a(n) for n in range(1, 101)]) # _Indranil Ghosh_, Apr 14 2017
%o A006666 (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 A006666 Cf. A006370, A006577, A006667 (tripling steps), A014682, A092892, A127789 (record indices of 2^a(n)/(3^A006667(n)*n)).
%K A006666 nonn,nice,look,easy
%O A006666 1,3
%A A006666 _N. J. A. Sloane_, _Bill Gosper_
%E A006666 More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001
%E A006666 Name edited by _M. F. Hasler_, May 07 2018