A224924 Sum_{i=0..n} Sum_{j=0..n} (i AND j), where AND is the binary logical AND operator.

0, 1, 3, 12, 16, 33, 63, 112, 120, 153, 211, 300, 408, 553, 735, 960, 976, 1041, 1155, 1324, 1536, 1809, 2143, 2544, 2952, 3433, 3987, 4620, 5320, 6105, 6975, 7936, 7968, 8097, 8323, 8652, 9072, 9601, 10239, 10992, 11800, 12729, 13779, 14956, 16248, 17673, 19231, 20928

Offset: 0

Author

Alex Ratushnyak, Apr 19 2013

Keywords

• nonn
• base

Comments

For n>0, a(2^n)-A000217(2^n)=a(2^n-1)-A000217(2^n-1) [See links]. - R. J. Cano, Aug 21 2013

Links

• Enrique Pérez Herrero, Table of n, a(n) for n = 0..1000
• R. J. Cano, Additional information
• Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 42-43.

Crossrefs

Cf. A004125, A222423, A224915, A224923, A000217.

Programs

Maple

read("transforms") :
A224924 := proc(n)
    local a,i,j ;
    a := 0 ;
    for i from 0 to n do
    for j from 0 to n do
        a := a+ANDnos(i,j) ;
    end do:
    end do:
    a ;
end proc: # R. J. Mathar, Aug 22 2013

Mathematica

a[n_] := Sum[BitAnd[i, j], {i, 0, n}, {j, 0, n}];
Table[a[n], {n, 0, 20}]
(* Enrique Pérez Herrero, May 30 2015 *)

PARI

a(n)=sum(i=0,n,sum(j=0,n,bitand(i,j))); \\ R. J. Cano, Aug 21 2013

Python

for n in range(99):
    s = 0
    for i in range(n+1):
      for j in range(n+1):
        s += i & j
    print(s, end=',')

Formula

a(2^n) = a(2^n - 1) + 2^n.

a(n) -a(n-1) = 2*A222423(n) -n. - R. J. Mathar, Aug 22 2013