A208981 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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: A375546 A079520 A229001 * A357892 A261158 A207543