Sum of $p$'th powers of all integers $\leq n$ with exactly $k$ set bits

137 Views Asked by At

$F(n,k,p)$ is the sum of $p$'th powers of all integers $\leq n$ with exactly $k$ set bits in their binary representation.

$F(18,3,4) = 7^4 + 11^4 + 13^4 + 14^4 = 84019$ because $7,11,13,14$ are the only integers less than $18$ with exactly 3 set bits, and the sum of their $4$'th powers is $84019$.

Likewise, $F(18,3,0) = 4$

I have found how to count such integers, i.e $F(n,k,0)$.

Let $b = \lfloor log_2n \rfloor$ (position of highest significant bit in $n$) and $F(n,k,0) = F(n,k)$, "&" is the bitwise AND operator, then:

$$F(n,k)=\begin {cases} 0&k\lt0\\ 1&k=0,n\geq0\\0&b \lt k - 1\\{b \choose k} + F(n \space \& \space (2^{b} - 1),k - 1)&otherwise \end {cases}$$

Which is understandable using some logic and combinatorics. Can it be generalized to sum such integers? their squares, cubes etc?

1

There are 1 best solutions below

0
On

Please check my arithmetic. This might help, not a full answer.

Special case of $p=1,k=2:$

There is a simple pattern to the positions of the set bits, see for example $$ 11000\\ 10100\\ 10010\\ 10001\\ ~\\ 01100\\ 01010\\ 01001\\ ~\\ 00110\\ 00101\\ ~\\ 00011 $$ and note that the position of the second set bit changes regularly in each group, giving

$$ f(n,2,1)=2^{t-1}+\sum_{k=1}^{t-2} 2^{t-1-k}+\\ \quad \quad \quad +2^{t-2}+\sum_{k=1}^{t-3} 2^{t-2-k}+ \\ \quad \quad \quad \vdots\\ \quad+2^2+2, $$

if $n=2^{t-1}+2^{t-2},$ or $$ f(n,2,1)=2^{t-1}+2^{t-1}-1+\\ \quad \quad \quad +2^{t-2}+2^{t-2}-1+ \\ \quad \quad \vdots\\ \quad +2+(2-1), $$ which becomes $$ f(n,2,1)=(2^t+2^{t-1}+\cdots+2^2)-(t-1)=2^{t+1}-4-(t-1)=2^{t+1}-t-3. $$

Then note that if you consider the position of the second highest set bit in $n$, the above expression can be adjusted by adjusting the first sum, by removing a few rows from the top of the first group.

This takes care of all $n$ for this restricted case.

For $p=1,k>2,$ a generalisation seems possible but I will not proceed further.