Evaluating $\sum\limits_{i=1}^N i \cdot (\text{# of 1 binary bits of } i)$?

Question

Given a value $N$, I need to find $\sum_{i=1}^N i X_i$ where $X_i$ is the number of 1 bits in the binary representation of $i$. I tried finding the values up till a particular power of 2 and summing it up. For example, the binary representation of $N=6$ is $110$. We can store value till 4, and value till 2 as well, and use some manipulation over these 2 values to obtain answer for 6. But, somehow I am unable to get the relation.

Answer 1

Here is a start for getting the sum up to $2^n$.

Let $s(N) = \sum_{i=1}^N i X_i $ and $t(N) = \sum_{i=1}^N X_i $.

I will get recurrences for $t(2^n)$ and $s(2^n)$ from which you can get formulas for them.

I will leave it at this because I am lazy.

$\begin{array}\\ t(2^{n+1}) &= \sum_{i=1}^{2^{n+1}} X_i\\ &= \sum_{i=1}^{2^{n}} X_i+\sum_{i=2^n+1}^{2^{n+1}} X_i\\ &= t(2^n)+\sum_{i=1}^{2^{n}} X_{2^n+i}\\ &= t(2^n)+\sum_{i=1}^{2^{n}} (1+X_{i})\\ &= t(2^n)+\sum_{i=1}^{2^{n}} 1+\sum_{i=1}^{2^{n}} X_{i}\\ &= 2t(2^n)+2^n\\ \end{array} $

Letting $t(2^n) = T(n)$, this becomes $T(n+1) =2T(n)+2^n $. Dividing by $2^{n+1}$, $\dfrac{T(n+1)}{2^{n+1}} =\dfrac{T(n)}{2^n}+\dfrac12 $.

$\begin{array}\\ s(2^{n+1}) &= \sum_{i=1}^{2^{n+1}} i X_i\\ &= \sum_{i=1}^{2^{n}} i X_i+\sum_{i=2^n+1}^{2^{n+1}} i X_i\\ &= \sum_{i=1}^{2^{n}} i X_i+\sum_{i=1}^{2^{n}} (2^n+i) X_{2^n+i}\\ &= \sum_{i=1}^{2^{n}} i X_i+\sum_{i=1}^{2^{n}} (2^n+i) (1+X_{i})\\ &= \sum_{i=1}^{2^{n}} i X_i+\sum_{i=1}^{2^{n}} (2^n+i) +\sum_{i=1}^{2^{n}} (2^n+i) X_{i}\\ &= 2\sum_{i=1}^{2^{n}} i X_i+\sum_{i=1}^{2^{n}} (2^n+i) +2^n\sum_{i=1}^{2^{n}} X_{i}\\ &= 2s(2^n)+2^{n+1}+2^n(2^n+1)/2+2^nt(2^n)\\ &= 2s(2^n)+2^{n+1}+2^{n-1}+2^{2n-1}+2^nt(2^n)\\ &= 2s(2^n)+2^{n-1}(2^n+5)+2^nt(2^n)\\ \end{array} $

Letting $s(2^n)=S(n)$, this becomes $S(n+1) =2S(n)+\frac12 2^n(2^n+5)+2^nT(n) $. Dividing by $2^{n+1}$, this becomes $\dfrac{S(n+1)}{2^{n+1}} =\dfrac{S(n)}{2^n}+\frac14 (2^n+5)+\frac12 T(n) $.