[seqfan] An unexpected formula related to the Hamming weight of integers

Thomas Baruchel baruchel at gmx.com
Tue Feb 28 19:54:47 CET 2023

Dear fellow seqfans,

I recently managed to build the following summation for the parity of
the Hamming weight, more precisely for the term (-1)^H(n) where H(n) is
the Hamming weight of n. These are the terms of the Thue-Morse sequence
(see https://oeis.org/A106400 ).

I am not sure whether this formula can be found in the literature or if
it has any interest, but I found it rather unexpected since it doesn't
rely on any bitwise operation. The formula is indeed a finite sum of
products of sines.

The formula being a little heavy, I typeset it online at https://mathb.in/74443
but you can also figure it out from the two following snippets of code:

Pari/GP version

f(n)=  my(l); l = 2*floor(log(n+1)/log(4)+1);    sum(k=0,l, (sqrt(3)/2)^(l-k-1)* sum(m=0, ceil(2^(k-1)-1),  sin( Pi*(  (6*m+1)*(2*n+1) - (-2)^(k-1) ) /(3*2^k)  )  * prod(i=0,k, sin((6*m+1)*Pi/3*(-2)^i/2^k   ))  ))

Mathematica version

f[n_] := Module[ {l = Floor[Log[4, n+1]+1]}, Sum[ (Sqrt[3]/2)^(2*l-k-1) * Sum[ Sin[ ((6*m+1)*(2*n+1)-(-2)^(k-1)) * Pi / (3*2^k) ] * Product[ Sin[ (6*m+1)*(-2)^i * Pi / (3*2^k) ], {i, 0, k}], {m, 0, Ceiling[2^(k-1)-1]}], {k, 0, 2*l}] ]

Best regards,

Thomas Baruchel

More information about the SeqFan mailing list