A006581 a(n) = Sum_{k=1..n-1} (k AND n-k). (Formerly M3225)

1, 0, 4, 4, 5, 0, 12, 16, 21, 16, 24, 20, 17, 0, 32, 48, 65, 64, 84, 84, 85, 64, 92, 96, 101, 80, 88, 68, 49, 0, 80, 128, 177, 192, 244, 260, 277, 256, 316, 336, 357, 336, 360, 340, 321, 256, 336, 368, 401, 384, 420, 404, 389, 320, 364, 352, 341, 272, 264, 196

Offset

2,3

References

Marc LeBrun, personal communication.

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

Links

Alois P. Heinz, Table of n, a(n) for n = 2..8191

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. 6, 24, 38-39, 64.

M. Le Brun, Email to N. J. A. Sloane, Jul 1991

Formula

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

a(0) = a(1) = 0, a(2n) = 2*a(n-1) + 2*a(n) + n, a(2n+1) = 4*a(n).

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

Mathematica

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

Prog

(Python)
def A006581(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

Crossrefs

Cf. A090889(n) - A000292(n-2).

Antidiagonal sums of array A003985.

Sequence in context: A255241 A200694 A021696 * A370717 A255902 A019922

Adjacent sequences: A006578 A006579 A006580 * A006582 A006583 A006584

Keyword

nonn

Author

N. J. A. Sloane

Status

approved