A006582 a(n) = Sum_{k=1..n-1} k XOR n-k.

0, 6, 4, 12, 20, 42, 32, 40, 48, 78, 84, 116, 148, 210, 176, 176, 176, 214, 212, 252, 292, 378, 368, 408, 448, 542, 580, 676, 772, 930, 832, 800, 768, 806, 772, 812, 852, 970, 928, 968, 1008, 1134, 1172, 1300, 1428, 1650, 1584, 1616, 1648, 1782, 1812, 1948

Offset: 2

Author

N. J. A. Sloane

Keywords

• nonn

References

• Marc LeBrun, personal communication.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• R. J. Mathar, Table of n, a(n) for n = 2..1000
• 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. 38-39.
• M. Le Brun, Email to N. J. A. Sloane, Jul 1991

Crossrefs

Antidiagonal sums of array A003987.

Programs

Maple

A006582 := proc(n)
    add(A003987(k,n-k),k=1..n-1) ;
end proc: # R. J. Mathar, Apr 17 2013

Mathematica

Array[Sum[BitXor[k, # - k], {k, # - 1}] &, 52, 2] (* Michael De Vlieger, Oct 27 2022 *)

PARI

a(n)=if(n<2,0,if(n%2==0,2*a(n/2)+2*a(n/2-1)+4*(n/2-1),4*a((n-1)/2)+6*((n-1)/2)))

PARI

a(n)=sum(k=1,n-1, bitxor(k,n-k)) \\ Charles R Greathouse IV, Aug 11 2017

Python

def A006582(n): return sum(k^n-k for k in range(1,n+1>>1))<<1 # Chai Wah Wu, May 07 2023

Formula

G.f.: 1/(1-x)^2 * Sum_{k>=0} 2^k * t^3(4t+6)/(1+t)^2, t=x^2^k. - Ralf Stephan, Feb 12 2003

a(0) = a(1) = 0, a(2n) = 2a(n) + 2a(n-1) + 4n - 4, a(2n+1) = 4a(n) + 6n. - Ralf Stephan, Oct 09 2003

a(n) = 2*(Sum_{k=1..floor((n-1)/2)} k XOR n-k). - Chai Wah Wu, May 07 2023