A006583 a(n) = Sum_{k=1..n-1} (k OR n-k).

1, 6, 8, 16, 25, 42, 44, 56, 69, 94, 108, 136, 165, 210, 208, 224, 241, 278, 296, 336, 377, 442, 460, 504, 549, 622, 668, 744, 821, 930, 912, 928, 945, 998, 1016, 1072, 1129, 1226, 1244, 1304

Offset: 2

Author

N. J. A. Sloane

Keywords

• nonn
• base

References

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

Links

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

Crossrefs

Antidiagonal sums of array A003986.

Programs

Mathematica

Table[Sum[BitOr[k,n-k],{k,n-1}],{n,2,50}] (* Harvey P. Dale, Dec 05 2020 *)

PARI

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

Python

def A006583(n): return (sum(k|n-k for k in range(1,n+1>>1))<<1)+(0 if n&1 else n>>1) # Chai Wah Wu, May 07 2023

Formula

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

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

a(n) = 2*(Sum_{k=1..floor((n-1)/2)} k OR n-k) + m where m is 0 if n is odd and n/2 otherwise. - Chai Wah Wu, May 07 2023