login
Number of tripling steps to reach 1 from n in '3x+1' problem, or -1 if 1 is never reached.
(Formerly M0019)
58

%I M0019 #85 Aug 08 2023 12:15:23

%S 0,0,2,0,1,2,5,0,6,1,4,2,2,5,5,0,3,6,6,1,1,4,4,2,7,2,41,5,5,5,39,0,8,

%T 3,3,6,6,6,11,1,40,1,9,4,4,4,38,2,7,7,7,2,2,41,41,5,10,5,10,5,5,39,39,

%U 0,8,8,8,3,3,3,37,6,42,6,3,6,6,11,11,1,6,40,40,1,1,9,9,4,9,4,33,4,4,38

%N Number of tripling steps to reach 1 from n in '3x+1' problem, or -1 if 1 is never reached.

%C A075680, which gives the values for odd n, isolates the essential behavior of this sequence. - _T. D. Noe_, Jun 01 2006

%C a(n) = A078719(n) - 1; a(A000079(n))=0; a(A062052(n))=1; a(A062053(n))=2; a(A062054(n))=3; a(A062055(n))=4; a(A062056(n))=5; a(A062057(n))=6; a(A062058(n))=7; a(A062059(n))=8; a(A062060(n))=9. - _Reinhard Zumkeller_, Oct 08 2011

%C A033959 and A033958 give record values and where they occur. - _Reinhard Zumkeller_, Jan 08 2014

%C a(n*2^k) = a(n), for all k >= 0. - _L. Edson Jeffery_, Aug 11 2014

%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 204, Problem 22.

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

%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="/A006667/b006667.txt">Table of n, a(n) for n = 1..10000</a>

%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, 92 (1985), 3-23.

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

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Collatz_conjecture">Collatz conjecture</a>

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

%F a(1) = 0, a(n) = a(n/2) if n is even, a(n) = a(3n+1)+1 if n>1 is odd. The Collatz conjecture is that this defines a(n) for all n >= 1.

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

%p a:= proc(n) option remember; `if`(n<2, 0,

%p `if`(n::even, a(n/2), 1+a(3*n+1)))

%p end:

%p seq(a(n), n=1..100); # _Alois P. Heinz_, Aug 08 2023

%t Table[Count[Differences[NestWhileList[If[EvenQ[#],#/2,3#+1]&,n,#>1&]], _?Positive], {n,100}] (* _Harvey P. Dale_, Nov 14 2011 *)

%o (PARI) for(n=2,100,s=n; t=0; while(s!=1,if(s%2==0,s=s/2,s=(3*s+1)/2; t++); if(s==1,print1(t,","); ); ))

%o (Haskell)

%o a006667 = length . filter odd . takeWhile (> 2) . (iterate a006370)

%o a006667_list = map a006667 [1..]

%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: n/=2

%o else:

%o n = 3*n + 1

%o x+=1

%o if n<2: break

%o return x

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

%Y Equals A078719(n)-1.

%Y Cf. A000079, A006370, A006577, A006666 (halving steps), A092893, A127789.

%K nonn,nice,hear

%O 1,3

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

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

%E "Escape clause" added to definition by _N. J. A. Sloane_, Jun 06 2017