login
A224923
a(n) = Sum_{i=0..n} Sum_{j=0..n} (i XOR j), where XOR is the binary logical exclusive-or operator.
4
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,2
LINKS
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