cp's OEIS Frontend

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

%I A224923 #38 Mar 12 2024 23:48:25
%S A224923 0,2,12,24,68,114,168,224,408,594,788,984,1212,1442,1680,1920,2672,
%T A224923 3426,4188,4952,5748,6546,7352,8160,9096,10034,10980,11928,12908,
%U A224923 13890,14880,15872,18912,21954,25004,28056,31140,34226,37320,40416,43640,46866,50100,53336,56604
%N A224923 a(n) = Sum_{i=0..n} Sum_{j=0..n} (i XOR j), where XOR is the binary logical exclusive-or operator.
%H A224923 Alois P. Heinz, <a href="/A224923/b224923.txt">Table of n, a(n) for n = 0..1023</a>
%H A224923 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, pp. 42-43.
%t A224923 Array[Sum[BitXor[i, j], {i, 0, #}, {j, 0, #}] &, 45, 0] (* _Michael De Vlieger_, Nov 03 2022 *)
%o A224923 (Python)
%o A224923 for n in range(99):
%o A224923     s = 0
%o A224923     for i in range(n+1):
%o A224923         for j in range(n+1):
%o A224923             s += i ^ j
%o A224923     print(s, end=",") # _Alex Ratushnyak_, Apr 19 2013
%o A224923 (Python) # O(log(n)) version, whereas program above is O(n^2)
%o A224923 def countPots2Until(n):
%o A224923     nbPots = {1:n>>1}
%o A224923     lftMask = ~3
%o A224923     rgtMask = 1
%o A224923     digit = 2
%o A224923     while True:
%o A224923         lft = (n & lftMask) >> 1
%o A224923         rgt = n & rgtMask
%o A224923         nbDigs = lft
%o A224923         if n & digit:
%o A224923             nbDigs |= rgt
%o A224923         if nbDigs == 0:
%o A224923             return nbPots
%o A224923         nbPots[digit] = nbDigs
%o A224923         rgtMask |= digit
%o A224923         digit <<= 1
%o A224923         lftMask = lftMask ^ digit
%o A224923 def sumXorSquare(n):
%o A224923     """Returns sum(i^j for i, j <= n)"""
%o A224923     n += 1
%o A224923     nbPots = countPots2Until(n)
%o A224923     return 2 * sum(pot * freq * (n - freq) for pot, freq in nbPots.items())
%o A224923 print([sumXorSquare(n) for n in range(100)])  # _Miguel Garcia Diaz_, Nov 19 2014
%o A224923 (Python) # O(log(n)) version, same as previous, but simpler and about 3x faster.
%o A224923 def xor_square(n: int) -> int:
%o A224923     return sum((((n + 1 >> i) ** 2 >> 1 << i) +
%o A224923                ((n + 1) & ((1 << i) - 1)) * (n + 1 + (1 << i) >> i + 1 << 1)
%o A224923                << 2 * i) for i in range(n.bit_length()))
%o A224923 print([xor_square(n) for n in range(100)]) # _Gabriel F. Ushijima_, Feb 24 2024
%Y A224923 Cf. A004125, A222423, A224915, A224924.
%K A224923 nonn,base
%O A224923 0,2
%A A224923 _Alex Ratushnyak_, Apr 19 2013