[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