Krdytkyu

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?

$F(0) = 0.$

If $2^k le n lt 2^{k+1}$, then $F(n) = F(n - 2^k) + F(2^k - 1) + n - 2^k + 1$.

Since $F(2^k -1) = k,2^{k-1}$, we have $F(n) = F(n-2^k) + k,2^{k-1} + n - 2^k + 1$.

The recursion works because the numbers between $2^k$ and $n$ all have their highest bit set (those bits give the $n - 2^k + 1$ part of the sum), and the sum of the other bits of those numbers is $F(n - 2^k)$, and the remaining numbers are taken care of by the $F(2^k-1)$ term.

The formula for $F(2^k-1)$ works because each of the $k$ bits of the numbers in ${0, 1,dots, 2^k - 1}$ is $1$ exactly half of the time.

Edit: Based on Ross Millikan's comment, it is possible to express this as a sum over the bits which are $1$ in $n$, if they are ordered correctly. If ${a_1, a_2,dots,a_m}$ are the exponents corresponding to the bits which are $1$ in $n$, ordered in increasing order, then $$F(n) = sum_{i=1}^m a_i,2^{a_i-1}-i,2^{a_i}+n+1 = m(n+1) + sum_{i=1}^m a_i,2^{a_i-1}-i,2^{a_i}$$

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) = lfloorlog_2{(n/(2k-1))}rfloor$$
The following identity has been used:

$$nu_2(n) = nu_2left(frac{n!}{(n-1)!}right) = nu_2(n!)-nu_2((n-1)!) = n-s_2(n)-n+1+s_2(n-1) = s_2(n-1)+1-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)$.