login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #39 Jun 08 2020 07:21:30

%S 0,1,2,6,4,11,18,28,8,21,34,50,60,79,98,120,16,41,66,94,116,147,178,

%T 212,216,253,290,330,364,407,450,496,32,81,130,182,228,283,338,396,

%U 424,485,546,610,668,735,802,872,816,889,962,1038,1108,1187,1266,1348,1400

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

%C 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.

%C Row sums of A080099. - _R. J. Mathar_, Apr 26 2013

%C 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

%H Ivan Neretin, <a href="/A222423/b222423.txt">Table of n, a(n) for n = 0..8192</a>

%F 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

%e a(3) = 6 because 1 AND 3 = 1; 2 AND 3 = 2; 3 AND 3 = 3; and 1 + 2 + 3 = 6.

%e 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.

%e 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.

%t Table[Sum[BitAnd[n, k], {k, 0, n}], {n, 0, 63}] (* _Alonso del Arte_, Feb 24 2013 *)

%o (Python)

%o for n in range(99):

%o s = 0

%o for k in range(n+1):

%o s += n & k

%o print(s, end=",")

%o (PARI) a(n) = sum(k=0, n, bitand(n, k)); \\ _Michel Marcus_, May 17 2015

%Y Cf. A004125.

%K nonn,base

%O 0,3

%A _Alex Ratushnyak_, Feb 23 2013