Evaluating $\sum\limits_{i=1}^N i \cdot (\text{# of 1 binary bits of } i)$? 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.
 A: 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)
$.
