login
A375551
a(n) = Sum_{k=0..n} k XOR n-k, where XOR is the bitwise exclusive disjunction. Row sums of A003987.
1
0, 2, 4, 12, 12, 22, 32, 56, 48, 58, 68, 100, 108, 142, 176, 240, 208, 210, 212, 252, 252, 294, 336, 424, 416, 458, 500, 596, 636, 734, 832, 992, 896, 866, 836, 876, 844, 886, 928, 1048, 1008, 1050, 1092, 1220, 1260, 1390, 1520, 1744, 1680, 1714, 1748, 1884, 1916
OFFSET
0,2
FORMULA
a(n) = 2*A099027(n).
a(n) = 2*n + A006582(n).
a(2^n - 1) = 4^n - 2^n = A020522(n).
a(2^n) = 4^n - 2^n*(n - 1) = 2*A376585(n).
Recurrence: a(0) = 0; a(2*n) = 2*(a(n) + a(n-1)); a(2*n+1) = 2*(2*a(n) + n + 1). - Paolo Xausa, Oct 01 2024, derived from recurrence in A099027.
MAPLE
XOR := (n, k) -> Bits:-Xor(n, k):
a := n -> local k; add(XOR(k, n-k), k=0..n):
seq(a(n), n = 0..52);
MATHEMATICA
(* Using definition *)
Table[Sum[BitXor[n - k, k], {k, 0, n}], {n, 0, 100}]
(* Using recurrence -- faster *)
a[0] = 0; a[n_] := a[n] = If[OddQ[n], 4*a[(n-1)/2] + n + 1, 2*(a[n/2] + a[n/2-1])];
Table[a[n], {n, 0, 100}] (* Paolo Xausa, Oct 01 2024 *)
PROG
(PARI) a(n) = sum(k=0, n, bitxor(k, n-k)); \\ Michel Marcus, Sep 28 2024
KEYWORD
nonn
AUTHOR
Peter Luschny, Sep 27 2024
STATUS
approved