Does the Hamming weight of $n \to \infty$ diverge or converge?

Question

The Hamming weight (or population count) of an integer $n$, which we denote by $w_H(n)$, is the number of $1$'s in the binary expansion of $n$. For example, let $n = 25_{10} = 11001_2$; counting the number of ones, we obtain $w_H(25) = 3$.

We can easily convert to binary (or represent $n_{10}$ as $n_2$) by summing powers of $2$, as follows

$$\cdots + 1(2^4) + 1(2^3) + 0(2^3) + 0(2^1) + 1(2^0) = 2^4 + 2^3 + 2^0 = 16 + 8 + 1 = 25$$

Let's say that $n \to \infty$, and we want to find out if the Hamming weight of $n$ converges or diverges. I.e., when $n \to \infty$, does $w_H(n)$ converge or diverge? If it converges, to what real number does it converge to?

My initial guess is that $n$ does diverge though, but I dont know how to prove it. I did a simple computer experiment and found out that when $n \to 59999$ it does seem to diverge, but very slowly. The average hamming weight at that end-point is $9.428114$. The more the binary length is increasing the more one bits are available. However, in a binary string there are equal amounts of zeros. But that is not enough proof. One last question, is it possible to find out by Cauchy that it converges, or what tools are available?

Thanks.

Answer 1

Obviously it diverges. Because there are arbitrarily large integers with weight $1$ (for example $2^k$) and arbitrarily large integers with weight $2$ (for example $3\cdot 2^k$.)

Edit: Now it seems the OP is really more interested in the average weight. That diverges as well.

Say $0\le n<2^k$. The binary expansion of $n$, if we pad on the left with zeroes, which don't affect the weight, is a sequence of $k$ zeroes and ones. And every sequence of $k$ zeroes and ones appears on the list. Half of the values on $n$ have a one in the first place, half have a one in the second place, etc. So $$2^{-k}\sum_{n=0}^{2^k-1}w_H(n)=k/2.$$(Because there are $2^{k-1}$ ones in each column and there are $k$ columns. For example with $k=3$:

000
001
010
011
100
101
110
111

Sure enough, four ones in each column.)

Note it follows that $\frac 1N\sum_{n=0}^{N-1}w_H(n)\to\infty$. Say $2^k\le N<2^{k+1}$. Then $$\frac 1N\sum_{n=0}^{N-1}w_h(n) \ge\frac 1N\sum_{n=0}^{2^k-1}w_H(n)=\frac {2^k}N(k/2)\ge k/4.$$

Answer 2

We can clearly show it diverges. Consider (2^n) - 1. any number of this form will have a hamming weight of n. Now since I can make n arbitrarily large in (2^n) - 1, whose hamming weight is n, then I can make the hamming weight arbitrarily large. So as I go to Infinity it makes sense that the hamming weight will diverge. This can be confusing due to the fractal nature of the hamming weight graph, and due to the fact that it grows logarithmically but it does indeed diverge.