login
Largest k such that 2^k appears in the trajectory of the Collatz 3x+1 sequence started at n.
13

%I #27 Apr 16 2022 09:33:28

%S 0,1,4,2,4,4,4,3,4,4,4,4,4,4,4,4,4,4,4,4,6,4,4,4,4,4,4,4,4,4,4,5,4,4,

%T 4,4,4,4,4,4,4,6,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,6,4,4,4,4,

%U 4,4,4,4,4,4,8,4,4,4,4,4,4,4,4,6,8,4,4

%N Largest k such that 2^k appears in the trajectory of the Collatz 3x+1 sequence started at n.

%C Most of the first eighty terms in the sequence are 4, because the trajectories finish with 16 -> 8 -> 4 -> 2 -> 1. - _R. J. Mathar_, Dec 12 2007

%C Most of the first ten thousand terms are 4, and there only appear 4, 6, 8, and 10 in the extent, unless n is power of 2. In the other words, it seems that the trajectory of the Collatz 3x + 1 sequence ends with either 16, 64, 256 or 1024. There are few exceptional terms, for example a(10920) = 12, a(10922) = 14. It also seems all terms are even unless n is an odd power of 2. - _Masahiko Shin_, Mar 16 2010

%C It is true that all terms are even unless n is an odd power of 2: 2 == -1 mod 3, 2 * 2 == -1 * -1 == 1 mod 3. Therefore only even-indexed powers of 2 are congruent to 1 mod 3 and thus reachable by either a halving step or a "tripling step," whereas the odd-indexed powers of 2 are only reachable by a halving step or as an initial value. - _Alonso del Arte_, Aug 15 2010

%H T. D. Noe, <a href="/A135282/b135282.txt">Table of n, a(n) for n = 1..10000</a>

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

%F a(n) = A006577(n) - A208981(n) (after _Alonso del Arte_'s comment in A208981), if A006577(n) is not -1. - _Omar E. Pol_, Apr 10 2022

%e a(6) = 4 because the sequence is 6, 3, 10, 5, 16, 8, 4, 2, 1; there 16 = 2^4 is the largest power of 2 encountered.

%p A135282 := proc(n) local k,threen1 ; k := 0 : threen1 := n ; while threen1 > 1 do if 2^ilog[2](threen1) = threen1 then k := max(k,ilog[2](threen1)) ; fi ; if threen1 mod 2 = 0 then threen1 := threen1/2 ; else threen1 := 3*threen1+1 ; fi ; od: RETURN(k) ; end: for n from 1 to 80 do printf("%d, ",A135282(n)) ; od: # _R. J. Mathar_, Dec 12 2007

%t Collatz[n_] := If[EvenQ[n], n/2, 3*n + 1]; Log[2, Table[NestWhile[Collatz, n, ! IntegerQ[Log[2, #]] &], {n, 100}]] (* _T. D. Noe_, Mar 05 2012 *)

%o (C) #include <stdio.h> int main(){ int i, s, f; for(i = 2; i < 10000; i++){ f = 0; s = i; while(s != 1){ if(s % 2 == 0){ s = s/2; f++;} else{ f = 0; s = 3 * s + 1; } } printf("%d,", f); } return 0; } /* _Masahiko Shin_, Mar 16 2010 */

%o (Haskell)

%o a135282 = a007814 . head . filter ((== 1) . a209229) . a070165_row

%o -- _Reinhard Zumkeller_, Jan 02 2013

%Y Cf. A007814, A209229, A070165, A232503.

%Y Cf. A006577, A208981.

%K nonn

%O 1,3

%A _Masahiko Shin_, Dec 02 2007

%E Edited and extended by _R. J. Mathar_, Dec 12 2007

%E More terms from _Masahiko Shin_, Mar 16 2010