login
A099027
a(n) = Sum_{k=0..n} n-k AND NOT k.
3
0, 1, 2, 6, 6, 11, 16, 28, 24, 29, 34, 50, 54, 71, 88, 120, 104, 105, 106, 126, 126, 147, 168, 212, 208, 229, 250, 298, 318, 367, 416, 496, 448, 433, 418, 438, 422, 443, 464, 524, 504, 525, 546, 610, 630, 695, 760, 872, 840, 857, 874, 942, 958, 1027, 1096
OFFSET
0,3
COMMENTS
Antidiagonal sums of array A099026.
LINKS
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.
FORMULA
Recurrence: a(0) = 0, a(2n) = 2a(n) + 2a(n-1), a(2n+1) = 4a(n) + n+1. [corrected by Peter J. Taylor, May 30 2024]
MATHEMATICA
(* Using definition *)
Table[Sum[BitAnd[n - k, BitNot[k]], {k, 0, n}], {n, 0, 100}]
(* Using recurrence -- faster *)
a[0] = 0; a[n_] := a[n] = If[OddQ[n], 4*a[(n-1)/2] + (n-1)/2 + 1, 2*(a[n/2] + a[n/2-1])];
Table[a[n], {n, 0, 100}] (* Paolo Xausa, Sep 30 2024 *)
PROG
(PARI) a(n) = sum(k=0, n, bitand(n-k, bitneg(k))); \\ Michel Marcus, Oct 30 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Ralf Stephan, Sep 26 2004
STATUS
approved