OFFSET
0,3
COMMENTS
Antidiagonal sums of array A099026.
LINKS
Michel Marcus, Table of n, a(n) for n = 0..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, 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