A048644 Differences between partial sums of Gray code (A048641) and triangular numbers (A000217).

0, 0, 1, 0, 2, 4, 3, 0, 4, 8, 13, 16, 14, 12, 7, 0, 8, 16, 25, 32, 42, 52, 59, 64, 60, 56, 53, 48, 38, 28, 15, 0, 16, 32, 49, 64, 82, 100, 115, 128, 148, 168, 189, 208, 222, 236, 247, 256, 248, 240, 233, 224, 218, 212, 203, 192, 172, 152, 133, 112, 86, 60, 31, 0, 32, 64

Offset

0,5

Comments

a(2^n-1) = 0 for all n.

Links

Michael De Vlieger, Table of n, a(n) for n = 0..10000

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. 40.

Formula

a(n) = sum(XORnos(j, floor(j/2)), j=0..n)-((n^2+n)/2).

Mathematica

{0}~Join~MapIndexed[#1 - PolygonalNumber[First[#2]] &, Accumulate[Array[BitXor[#, Floor[#/2]] &, 65]]] (* Michael De Vlieger, Oct 29 2022 *)

Prog

(PARI) a(n) = sum(k=0, n, bitxor(k, k>>1)) - n*(n+1)/2; \\ Michel Marcus, Oct 02 2015

Crossrefs

Cf. A000217, A048461, A048643.

Sequence in context: A134138 A351427 A201911 * A246713 A106137 A213381

Adjacent sequences: A048641 A048642 A048643 * A048645 A048646 A048647

Keyword

easy,nonn

Author

Antti Karttunen, Jul 14 1999

Extensions

Corrected by Don Reble, May 01 2006

Status

approved