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

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

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.

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)

Example

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.

Mathematica

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

Prog

(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)); } }
(Haskell)
a173732 n = a173732_list !! n
a173732_list = f $ tail a025480_list where f (x : _ : _ : xs) = x : f xs
-- Reinhard Zumkeller, Apr 29 2012
(PARI) odd(n) = n >> valuation(n, 2);
a(n) = (odd(6*n+4) - 1)/2; \\ Amiram Eldar, Aug 26 2024

Crossrefs

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

Sequence in context: A154954 A095245 A324245 * A086280 A349950 A164976

Adjacent sequences: A173729 A173730 A173731 * A173733 A173734 A173735

Keyword

easy,nonn

Author

Howard A. Landman, Feb 22 2010

Extensions

Name changed by Michael De Vlieger, Oct 07 2019

Status

approved