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,3

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

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

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

Example

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.

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

Prog

(Haskell)
a208981 = length . takeWhile ((== 0) . a209229) . a070165_row
-- Reinhard Zumkeller, Jan 02 2013
(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

Crossrefs

Row sums of A347519.

Cf. A006577 (and references therein).

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

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

Sequence in context: A352449 A079520 A229001 * A357892 A261158 A207543

Adjacent sequences: A208978 A208979 A208980 * A208982 A208983 A208984

Keyword

nonn,nice,look

Author

L. Edson Jeffery, Mar 04 2012

Extensions

Name clarified by Omar E. Pol, Apr 10 2022

Status

approved