A006581 a(n) = Sum_{k=1..n-1} (k AND n-k).
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
Keywords
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
Programs
-
Mathematica
Array[Sum[BitAnd[k, # - k], {k, # - 1}] &, 60, 2] (* Michael De Vlieger, Oct 27 2022 *) -
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
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