A222423 Sum of (n AND k) for k = 0, 1, 2, ..., n, where AND is the bitwise AND operator.

0, 1, 2, 6, 4, 11, 18, 28, 8, 21, 34, 50, 60, 79, 98, 120, 16, 41, 66, 94, 116, 147, 178, 212, 216, 253, 290, 330, 364, 407, 450, 496, 32, 81, 130, 182, 228, 283, 338, 396, 424, 485, 546, 610, 668, 735, 802, 872, 816, 889, 962, 1038, 1108, 1187, 1266, 1348, 1400

Offset

0,3

Comments

If n = 2^x, (n AND k) = 0 for k < n, therefore a(n) = n if and only if n = 0 or n = 2^x.

Row sums of A080099. - R. J. Mathar, Apr 26 2013

The associated incomplete sum_{0<=k<n} (n AND k) = a(n)-n starts 0, 0, 0, 3, 0, 6, 12, 21, 0, 12, 24, 39, 48, 66, 84, 105, .... and appears to be 3*A213673(n). - R. J. Mathar, Aug 22 2013

Links

Ivan Neretin, Table of n, a(n) for n = 0..8192

Formula

a(2^n-1) = A006516(n) for all n, since k AND 2^n-1 = k for all k<2^n. - M. F. Hasler, Feb 28 2013

Example

a(3) = 6 because 1 AND 3 = 1; 2 AND 3 = 2; 3 AND 3 = 3; and 1 + 2 + 3 = 6.
a(4) = 4 because 1 AND 4 = 0; 2 AND 4 = 0; 3 AND 4 = 0; 4 AND 4 = 4; and 0 + 0 + 0 + 4 = 4.
a(5) = 11 because 1 AND 5 = 1; 2 AND 5 = 0; 3 AND 5 = 1; 4 AND 5 = 4; 5 AND 5 = 5; and 1 + 0 + 1 + 4 + 5 = 11.

Mathematica

Table[Sum[BitAnd[n, k], {k, 0, n}], {n, 0, 63}] (* Alonso del Arte, Feb 24 2013 *)

Prog

(Python)
for n in range(99):
    s = 0
    for k in range(n+1):
        s += n & k
    print(s, end=", ")
(PARI) a(n) = sum(k=0, n, bitand(n, k)); \\ Michel Marcus, May 17 2015

Crossrefs

Cf. A004125.

Sequence in context: A242901 A353731 A266013 * A059909 A145177 A007517

Adjacent sequences: A222420 A222421 A222422 * A222424 A222425 A222426

Keyword

nonn,base

Author

Alex Ratushnyak, Feb 23 2013

Status

approved