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

Author

Alex Ratushnyak, Feb 23 2013

Keywords

• nonn
• base

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<=kA213673(n). - R. J. Mathar, Aug 22 2013

Examples

			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.
		

Links

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

Crossrefs

Cf. A004125.

Programs

Mathematica

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

PARI

a(n) = sum(k=0, n, bitand(n, k)); \\ Michel Marcus, May 17 2015

Python

for n in range(99):
    s = 0
    for k in range(n+1):
        s += n & k
    print(s, end=",")

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