A099027 - OEIS

%I #29 Sep 30 2024 06:10:35

%S 0,1,2,6,6,11,16,28,24,29,34,50,54,71,88,120,104,105,106,126,126,147,

%T 168,212,208,229,250,298,318,367,416,496,448,433,418,438,422,443,464,

%U 524,504,525,546,610,630,695,760,872,840,857,874,942,958,1027,1096

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

%C Antidiagonal sums of array A099026.

%H Michel Marcus, <a href="/A099027/b099027.txt">Table of n, a(n) for n = 0..8191</a>

%H Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, p. 39.

%F 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]

%t (* Using definition *)

%t Table[Sum[BitAnd[n - k, BitNot[k]], {k, 0, n}], {n, 0, 100}]

%t (* Using recurrence -- faster *)

%t 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])];

%t Table[a[n], {n, 0, 100}] (* _Paolo Xausa_, Sep 30 2024 *)

%o (PARI) a(n) = sum(k=0, n, bitand(n-k, bitneg(k))); \\ _Michel Marcus_, Oct 30 2022

%Y Cf. A006581, A006582, A006583, A099026.

%K nonn

%O 0,3

%A _Ralf Stephan_, Sep 26 2004