A375551 - OEIS

%I #26 Oct 01 2024 12:05:05

%S 0,2,4,12,12,22,32,56,48,58,68,100,108,142,176,240,208,210,212,252,

%T 252,294,336,424,416,458,500,596,636,734,832,992,896,866,836,876,844,

%U 886,928,1048,1008,1050,1092,1220,1260,1390,1520,1744,1680,1714,1748,1884,1916

%N a(n) = Sum_{k=0..n} k XOR n-k, where XOR is the bitwise exclusive disjunction. Row sums of A003987.

%H Paolo Xausa, <a href="/A375551/b375551.txt">Table of n, a(n) for n = 0..10000</a>

%F a(n) = 2*A099027(n).

%F a(n) = 2*n + A006582(n).

%F a(2^n - 1) = 4^n - 2^n = A020522(n).

%F a(2^n) = 4^n - 2^n*(n - 1) = 2*A376585(n).

%F 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.

%p XOR := (n, k) -> Bits:-Xor(n, k):

%p a := n -> local k; add(XOR(k, n-k), k=0..n):

%p seq(a(n), n = 0..52);

%t (* Using definition *)

%t Table[Sum[BitXor[n - k, k], {k, 0, n}], {n, 0, 100}]

%t (* Using recurrence -- faster *)

%t 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])];

%t Table[a[n], {n, 0, 100}] (* _Paolo Xausa_, Oct 01 2024 *)

%o (PARI) a(n) = sum(k=0, n, bitxor(k, n-k)); \\ _Michel Marcus_, Sep 28 2024

%Y Cf. A003986, A003987, A006582, A020522, A051933, A099027, A224915, A376585.

%K nonn

%O 0,2

%A _Peter Luschny_, Sep 27 2024