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

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, 41, 21, 44, 11, 47, 24, 50, 6, 53, 27, 56, 14, 59, 30, 62, 0, 65, 33, 68, 17, 71, 36, 74, 9, 77, 39, 80, 20, 83, 42, 86, 5, 89, 45, 92, 23, 95, 48, 98, 12, 101, 51, 104, 26, 107, 54, 110, 3

Offset: 0

Author

Howard A. Landman, Feb 22 2010

Keywords

• easy
• nonn

Comments

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.

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

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

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

A204418(a(n)) = 1. - Reinhard Zumkeller, Apr 29 2012

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

Examples

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

Links

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

Crossrefs

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

Programs

C

#include  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)); } }

Haskell

a173732 n = a173732_list !! n
a173732_list = f $ tail a025480_list where f (x :  :  : xs) = x : f xs
-- Reinhard Zumkeller, Apr 29 2012

Mathematica

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

PARI

odd(n) = n >> valuation(n, 2);
a(n) = (odd(6*n+4) - 1)/2; \\ Amiram Eldar, Aug 26 2024

Formula

From Amiram Eldar, Aug 26 2024: (Start)

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

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

Extensions

Name changed by Michael De Vlieger, Oct 07 2019