A099027 a(n) = Sum_{k=0..n} n-k AND NOT k.

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

Author

Ralf Stephan, Sep 26 2004

Keywords

• nonn

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.

Crossrefs

Cf. A006581, A006582, A006583, A099026.

Programs

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 *)

PARI

a(n) = sum(k=0, n, bitand(n-k, bitneg(k))); \\ Michel Marcus, Oct 30 2022

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]