OFFSET
0,2
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.
MATHEMATICA
Array[Sum[BitXor[i, j], {i, 0, #}, {j, 0, #}] &, 45, 0] (* Michael De Vlieger, Nov 03 2022 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Alex Ratushnyak, Apr 19 2013
STATUS
approved