A072481 a(n) = Sum_{k=1..n} Sum_{d=1..k} (k mod d).
0, 0, 0, 1, 2, 6, 9, 17, 25, 37, 50, 72, 89, 117, 148, 184, 220, 271, 318, 382, 443, 513, 590, 688, 773, 876, 988, 1113, 1237, 1388, 1526, 1693, 1860, 2044, 2241, 2459, 2657, 2890, 3138, 3407, 3665, 3962, 4246, 4571, 4899, 5238, 5596, 5999, 6373, 6787, 7207
Offset: 0
Keywords
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
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.
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
A258438 Sum_{i=1..n} Sum_{j=1..n} (i OR j), where OR is the binary logical OR operator.
0, 1, 9, 24, 64, 117, 189, 280, 456, 657, 889, 1152, 1464, 1813, 2205, 2640, 3376, 4161, 5001, 5896, 6864, 7893, 8989, 10152, 11448, 12817, 14265, 15792, 17416, 19125, 20925, 22816, 25824, 28929, 32137, 35448, 38880, 42421, 46077, 49848, 53800
Offset: 0
Links
- Giovanni Resta, Table of n, a(n) for n = 0..10000
- 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, p. 42.
Crossrefs
Cf. A224924.
Programs
-
Maple
A[0]:= 0: for n from 1 to 100 do A[n]:= A[n-1] + n + 2*add(Bits[Or](i,n),i=1..n-1) od: seq(A[i],i=0..100); # Robert Israel, Jun 11 2015
-
Mathematica
a[n_] := Sum[BitOr[i, j], {i, 1, n}, {j, 1, n}]; Table[a[n], {n, 0, 40}] -
PARI
a(n) = sum(i=1, n, sum(j=1, n, bitor(i, j))); \\ Michel Marcus, May 31 2015
Formula
a(2^k) = (3*8^k+5*4^k)/4-2^k. - Giovanni Resta, May 30 2015
a(2^k-1) = 2^(k-2) * (4 - 7*2^k + 3*4^k). - Enrique Pérez Herrero, Jun 10 2015
a(n) = n^3 + n^2 - A224924(n). - Robert Israel, Jun 11 2015
Comments
Links
Crossrefs
Programs
Maple
Mathematica
a[n_] := n(n+1)(2n+1)/6 - Sum[DivisorSigma[1, k] (n-k+1), {k, 1, n}]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Mar 08 2019, after Omar E. Pol *)PARI
Python
for n in range(99): s = 0 for k in range(1,n+1): for d in range(1,k+1): s += k % d print(str(s), end=',')Python
Formula
Extensions