A306754 The bottom entry in the difference table of the positions of the ones in the binary representation of n.

0, 0, 1, 1, 2, 2, 1, 0, 3, 3, 2, 1, 1, -1, 0, 0, 4, 4, 3, 2, 2, 0, 1, 1, 1, -2, -1, -2, 0, 1, 0, 0, 5, 5, 4, 3, 3, 1, 2, 2, 2, -1, 0, -1, 1, 2, 1, 1, 1, -3, -2, -4, -1, -1, -2, -3, 0, 2, 1, 3, 0, -1, 0, 0, 6, 6, 5, 4, 4, 2, 3, 3, 3, 0, 1, 0, 2, 3, 2, 2, 2, -2

Offset: 0

Author

Rémy Sigrist, Mar 08 2019

Keywords

• sign
• base

Comments

By convention, a(0) = 0.

For any n > 0:

- let (b_1, b_2, ..., b_h) be the positions of the ones in the binary representation of n,

- h = A000120(n) and 0 <= b_1 < b_2 < ... < b_h,

- n = Sum_{k = 1..h} 2^b_k,

- a(n) is the unique value remaining after taking successively the first differences of (b_1, ..., b_h) h-1 times.

Examples

			For n = 59:
- the binary representation of 59 is "111011",
- so h = 5 and b_1 = 0, b_2 = 1, b_3 = 3, b_4 = 4, b_5 = 5,
- the corresponding difference table is:
        0   1   3   4   5
          1   2   1   1
            1  -1   0
             -2   1
                3
- hence a(59) = 3.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..16384

Crossrefs

See A306607 for a similar sequence.

Cf. A000120, A133457, A209229.

Programs

PARI

a(n) = { my (h=hammingweight(n), o=0, v=0); forstep (k=h-1, 0, -1, my (w=valuation(n, 2)); o += w; v += (-1)^k * binomial(h-1, k) * o; o++; n\=2^(1+w)); v };

Formula

a(2^k) = k for any k >= 0.

a(2^k-1) = [k=2].

a(2*n) = a(n) + A209229(n).