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

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.

Links

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

Formula

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

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

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

Example

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.

Prog

(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 };

Crossrefs

See A306607 for a similar sequence.

Cf. A000120, A133457, A209229.

Sequence in context: A352556 A368282 A285099 * A063250 A348967 A285308

Adjacent sequences: A306751 A306752 A306753 * A306755 A306756 A306757

Keyword

sign,base

Author

Rémy Sigrist, Mar 08 2019

Status

approved