A224923 a(n) = Sum_{i=0..n} Sum_{j=0..n} (i XOR j), where XOR is the binary logical exclusive-or operator.

0, 2, 12, 24, 68, 114, 168, 224, 408, 594, 788, 984, 1212, 1442, 1680, 1920, 2672, 3426, 4188, 4952, 5748, 6546, 7352, 8160, 9096, 10034, 10980, 11928, 12908, 13890, 14880, 15872, 18912, 21954, 25004, 28056, 31140, 34226, 37320, 40416, 43640, 46866, 50100, 53336, 56604

Offset: 0

Author

Alex Ratushnyak, Apr 19 2013

Keywords

• nonn
• base

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1023
• 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, A224924.

Programs

Mathematica

Array[Sum[BitXor[i, j], {i, 0, #}, {j, 0, #}] &, 45, 0] (* Michael De Vlieger, Nov 03 2022 *)

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=",") # Alex Ratushnyak, Apr 19 2013

Python

# O(log(n)) version, whereas program above is O(n^2)
def countPots2Until(n):
    nbPots = {1:n>>1}
    lftMask = ~3
    rgtMask = 1
    digit = 2
    while True:
        lft = (n & lftMask) >> 1
        rgt = n & rgtMask
        nbDigs = lft
        if n & digit:
            nbDigs |= rgt
        if nbDigs == 0:
            return nbPots
        nbPots[digit] = nbDigs
        rgtMask |= digit
        digit <<= 1
        lftMask = lftMask ^ digit
def sumXorSquare(n):
    """Returns sum(i^j for i, j <= n)"""
    n += 1
    nbPots = countPots2Until(n)
    return 2 * sum(pot * freq * (n - freq) for pot, freq in nbPots.items())
print([sumXorSquare(n) for n in range(100)])  # Miguel Garcia Diaz, Nov 19 2014

Python

# O(log(n)) version, same as previous, but simpler and about 3x faster.
def xor_square(n: int) -> int:
    return sum((((n + 1 >> i) ** 2 >> 1 << i) +
               ((n + 1) & ((1 << i) - 1)) * (n + 1 + (1 << i) >> i + 1 << 1)
               << 2 * i) for i in range(n.bit_length()))
print([xor_square(n) for n in range(100)]) # Gabriel F. Ushijima, Feb 24 2024