cp's OEIS Frontend

A208981 Number of iterations required to reach a power of 2 in the 3x+1 sequence starting at n.

%I A208981 #83 Feb 16 2025 08:33:16
%S A208981 0,0,3,0,1,4,12,0,15,2,10,5,5,13,13,0,8,16,16,3,1,11,11,6,19,6,107,14,
%T A208981 14,14,102,0,22,9,9,17,17,17,30,4,105,2,25,12,12,12,100,7,20,20,20,7,
%U A208981 7,108,108,15,28,15,28,15,15,103,103,0,23,23,23,10,10,10
%N A208981 Number of iterations required to reach a power of 2 in the 3x+1 sequence starting at n.
%C A208981 The original name was: Number of iterations of the Collatz recursion required to reach a power of 2.
%C A208981 The statement that all paths must eventually reach a power of 2 is equivalent to the Collatz conjecture.
%C A208981 A006577(n) - a(n) gives the exponent for the first power of 2 reached in the Collatz trajectory of n. - _Alonso del Arte_, Mar 05 2012
%C A208981 Number of nonpowers of 2 in the 3x+1 sequence starting at n. - _Omar E. Pol_, Sep 05 2021
%H A208981 Reinhard Zumkeller, <a href="/A208981/b208981.txt">Table of n, a(n) for n = 1..10000</a>
%H A208981 John Smith, <a href="https://planetmath.org/collatzsequence">Collatz sequence</a>, PlanetMath.
%H A208981 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CollatzProblem.html">Collatz problem</a>.
%H A208981 <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%F A208981 For x>0 an integer, define f_0(x)=x, and for r=1,2,..., f_r(x)=f_{r-1}(x)/2 if f_{r-1}(x) is even, else f_r(x)=3*f_{r-1}(x)+1. Then a(n) = min(k such that f_k(n) is equal to a power of 2).
%F A208981 a(n) = A006577(n) - A135282(n) (after _Alonso del Arte_'s comment), if A006577(n) is not -1. - _Omar E. Pol_, Apr 10 2022
%e A208981 a(7) = 12 because the Collatz trajectory for 7 is 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ... which reached 16 = 2^4 in 12 steps.
%p A208981 a:= proc(n) option remember; `if`(n=2^ilog2(n), 0,
%p A208981       1+a(`if`(n::odd, 3*n+1, n/2)))
%p A208981     end:
%p A208981 seq(a(n), n=1..100);  # _Alois P. Heinz_, Sep 05 2021
%t A208981 Collatz[n_?OddQ] := 3*n + 1; Collatz[n_?EvenQ] := n/2; Table[-1 + Length[NestWhileList[Collatz, n, Not[IntegerQ[Log[2, #]]] &]], {n, 50}] (* _Alonso del Arte_, Mar 04 2012 *)
%o A208981 (Haskell)
%o A208981 a208981 = length . takeWhile ((== 0) . a209229) . a070165_row
%o A208981 -- _Reinhard Zumkeller_, Jan 02 2013
%o A208981 (PARI) ispow2(n)=n>>=valuation(n,2); n==1
%o A208981 a(n)=my(s); while(!ispow2(n), n=if(n%2, 3*n+1, n/2); s++); s \\ _Charles R Greathouse IV_, Jul 31 2016
%Y A208981 Row sums of A347519.
%Y A208981 Cf. A006577 (and references therein).
%Y A208981 Cf. A347270 (gives all 3x+1 sequences).
%Y A208981 Cf. A070165, A010120, A057716, A135282, A209229.
%K A208981 nonn,nice,look
%O A208981 1,3
%A A208981 _L. Edson Jeffery_, Mar 04 2012
%E A208981 Name clarified by _Omar E. Pol_, Apr 10 2022