Sum of set bits in every element for a natural numbers I was thinking of a mathematical puzzle with binary representation of numbers, but could not find a convincing answer myself. 
Here is the puzzle: Say for some number N, I want to find the sum of the set bits of every number from 1 to N.
For example, for 5
The answer would be: 7 by the following procedure
1 - 1 set bit
2 - 1 set bit
3 - 2 set bits
4 - 1 set bit
5 - 2 set bits

So answer is 1 + 1 + 2 + 1 + 2 = 7

I found that it's easy to just go one by one and add, like I did. I also found that for a number having x bits, they form the pascal triangle with set ones, if number of occurances are counted with same number of set bits, irrespective of value. For example, 
when x = 1, we have {1} - 1 set bit occurs once, hence 1.
when x = 2, we have {10, 11} - 1 set bit occurs once, 2 set bits occurs once, hence 1 1
when x = 3, we have {100, 101, 110, 111} - 1 set bit occurs once, 2 set bits occur twice, and 3 set bits occur once, hence 1 2 1

This series is continued. However, summing these up will give me a range, inside of which the answer lies. (Example ans is in [8, 15])
My first solution is the naive approach. Second one is a little mathematical, but not very fruitful.
I was wondering if we could derive a formula any N?

Not a clean formula, but using Legendre's formula (see Alternate form) and this it can be shown that:
$$F(n) = \frac{(n+1)n}{2}+\sum_{k=1}^{\lfloor{n/2}\rfloor}\{(2k-1)[(g(n, k)-1)2^{g(n, k)+1}+2]-(n+1)\frac{(g(n, k)+1)g(n, k)}{2}\}$$
where:
$$g(n, k) = \lfloor\log_2{(n/(2k-1))}\rfloor$$
The following identity has been used:
$$\nu_2(n!) = n-s_2(n)$$
where $\nu_2(n!)$ is the 2-adic valuation of $n!$ and $s_2(n)$ is the sum of ones in the binary representation of $n$.
From there one can write:
$$s_2(n)=n-\sum_{k=2}^n{\nu_2(k)}$$
$$\sum_{k=1}^n{s_2(k)}=\frac{n(n+1)}{2}-\sum_{k=2}^{n}{(n-k+1)\nu_2(k)}=\frac{n(n+1)}{2}-(n-2+1)-(n-4+1)2-(n-8+1)3+\ldots-(n-2^{\lfloor{log_2n}\rfloor}+1)\lfloor{log_2n}\rfloor+\ldots=\frac{n(n+1)}{2}-(n+1)\frac{\lfloor{log_2n}\rfloor(\lfloor{log_2n}\rfloor+1)}{2}+\sum_{k=1}^{\lfloor{log_2n}\rfloor}k2^k+\ldots$$
and go on from there doing what has been done for $n$ to $n/(2m-1)$.
