|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
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
(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())
(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()))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,base
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|