A173732 - OEIS

%I #35 Aug 26 2024 05:00:13

%S 0,2,0,5,3,8,2,11,6,14,0,17,9,20,5,23,12,26,3,29,15,32,8,35,18,38,2,

%T 41,21,44,11,47,24,50,6,53,27,56,14,59,30,62,0,65,33,68,17,71,36,74,9,

%U 77,39,80,20,83,42,86,5,89,45,92,23,95,48,98,12,101,51,104,26,107,54,110,3

%N a(n) = (A016957(n)/2^A007814(A016957(n)) - 1)/2, with A016957(n) = 6*n+4 and A007814(n) the 2-adic valuation of n.

%C All positive integers eventually reach 1 in the Collatz problem iff all nonnegative integers eventually reach 0 with repeated application of this map, i.e., if for all n, the sequence n, a(n), a(a(n)), a(a(a(n))), ... eventually hits 0.

%C 0 <= a(n) <= (3n+1)/2, with the upper bound being achieved for all odd n.

%C The positions of the zeros are given by A020988 = (2/3)*(4^n-1). This is because if n = (2/3)*(4^k-1), then m = 2n+1 = (1/3)*(4^(k+1)-1), and 3m+1 = 4^(k+1) is a power of 4. - _Howard A. Landman_, Mar 14 2010

%C Subsequence of A025480, a(n) = A025480(3n+1), i.e., A025480 = 0,[0],1,0,[2],1,3,[0],4,2,[5],1,6,[3],7,0,[8],4,9,[2],10,5,[11],1,12,[6],13,3,[14],... with elements of A173732 in brackets. - Paul Tarau, Mar 21 2010

%C A204418(a(n)) = 1. - _Reinhard Zumkeller_, Apr 29 2012

%C Original name: "A compression of the Collatz (or 3x+1) sequence considered as a map from odd numbers to odd numbers." - _Michael De Vlieger_, Oct 07 2019

%H Reinhard Zumkeller, <a href="/A173732/b173732.txt">Table of n, a(n) for n = 0..10000</a>

%H Eric Weisstein's World of Mathematics,<a href="http://mathworld.wolfram.com/CollatzProblem.html">Collatz Problem</a>.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Collatz_conjecture">Collatz conjecture</a>.

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

%F From _Amiram Eldar_, Aug 26 2024: (Start)

%F a(n) = (A075677(n+1) - 1)/2.

%F Sum_{k=1..n} a(k) ~ n^2 / 2. (End)

%e a(0) = 0 because 2n+1 = 1 (the first odd number), 3*1 + 1 = 4, dividing all powers of 2 out of 4 leaves 1, and (1-1)/2 = 0.

%e a(1) = 2 because 2n+1 = 3, 3*3 + 1 = 10, dividing all powers of 2 out of 10 leaves 5, and (5-1)/2 = 2.

%t Array[(#/2^IntegerExponent[#, 2] - 1)/2 &[6 # + 4] &, 75, 0] (* _Michael De Vlieger_, Oct 06 2019 *)

%o (C) #include <stdio.h> main() { int k,m,n; for (k = 0; ; k++) { n = 2*k + 1 ; m = 3*n + 1 ; while (!(m & 1)) { m >>= 1 ; } printf("%d,",((m - 1) >> 1)); } }

%o (Haskell)

%o a173732 n = a173732_list !! n

%o a173732_list = f $ tail a025480_list where f (x : _ : _ : xs) = x : f xs

%o -- _Reinhard Zumkeller_, Apr 29 2012

%o (PARI) odd(n) = n >> valuation(n, 2);

%o a(n) = (odd(6*n+4) - 1)/2; \\ _Amiram Eldar_, Aug 26 2024

%Y Cf. A006370, A007494 (range), A007814, A016957, A020988, A025480, A075677.

%K easy,nonn

%O 0,2

%A _Howard A. Landman_, Feb 22 2010

%E Name changed by _Michael De Vlieger_, Oct 07 2019