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

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, 14, 14, 102, 0, 22, 9, 9, 17, 17, 17, 30, 4, 105, 2, 25, 12, 12, 12, 100, 7, 20, 20, 20, 7, 7, 108, 108, 15, 28, 15, 28, 15, 15, 103, 103, 0, 23, 23, 23, 10, 10, 10

Offset: 1

Author

L. Edson Jeffery, Mar 04 2012

Keywords

• nonn
• nice
• look

Comments

The original name was: Number of iterations of the Collatz recursion required to reach a power of 2.

The statement that all paths must eventually reach a power of 2 is equivalent to the Collatz conjecture.

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

Number of nonpowers of 2 in the 3x+1 sequence starting at n. - Omar E. Pol, Sep 05 2021

Examples

			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.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• John Smith, Collatz sequence, PlanetMath.
• Eric Weisstein's World of Mathematics, Collatz problem.
• Index entries for sequences related to 3x+1 (or Collatz) problem

Crossrefs

Row sums of A347519.

Cf. A006577 (and references therein).

Cf. A347270 (gives all 3x+1 sequences).

Cf. A070165, A010120, A057716, A135282, A209229.

Programs

Haskell

a208981 = length . takeWhile ((== 0) . a209229) . a070165_row
-- Reinhard Zumkeller, Jan 02 2013

Maple

a:= proc(n) option remember; `if`(n=2^ilog2(n), 0,
      1+a(`if`(n::odd, 3*n+1, n/2)))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Sep 05 2021

Mathematica

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 *)

PARI

ispow2(n)=n>>=valuation(n,2); n==1
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

Formula

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

a(n) = A006577(n) - A135282(n) (after Alonso del Arte's comment), if A006577(n) is not -1. - Omar E. Pol, Apr 10 2022

Extensions

Name clarified by Omar E. Pol, Apr 10 2022