Project Nayuki

Iterated popcount results in 0 or 1


By repeatedly applying the popcount function to any positive integer, the result will eventually be 1 and stay that way.

More formally: For each integer \(n \ge 1\), there exists \(k \ge 0\) such that \(\text{popcount}^{(k)}(n) = 1\).


(A highly abridged proof for busy, seasoned mathematicians: \(1 \le \text{popcount}(n) < n\) for all \(n \ge 2\). By well-ordering, iterating \(\text{popcount}\) will eventually produce \(1\).)

Definition: The popcount function, also known as Hamming weight, is the number of 1’s in the binary representation of a non-negative integer. For example, \(\text{popcount}(13) = \text{popcount}(1101_2) = 3\).

By inspection, 0 and 1 are fixed points of this function – namely, \(\text{popcount}(0) = 0\) and \(\text{popcount}(1) = 1\). This means whenever \(\text{popcount}(n) = 1\), we know that \(\text{popcount}(\text{popcount}(n)) = 1\). So once the iteration process reaches \(1\), it keeps producing \(1\) identically.

Lemma alpha

Whenever \(n \ge 4\), \(n\) is greater than the number of binary digits \(n\) has. More formally: \(\forall n \in \mathbb{N}, \: (n \ge 4 \: \Rightarrow \: n > \!\! \left\lfloor \log_2 n \right\rfloor + 1)\).

Intuitively speaking, this is true because the number of bits is a non-decreasing function that increases by merely 1 every time its input doubles. At 4, the function value is 3; at 8 the function value is 4; at 16 the function value is 5. The function value always grows more slowly than the input value. A proof by strong induction will be omitted.

Lemma beta

For \(n \ge 2\), we can show that \(1 \le \text{popcount}(n) < n\).

By definition, \(\text{popcount}(n)\) is no more than the number of binary digits in \(n\). We also know that each positive integer must have at least one bit set to 1. Hence for \(n \ge 1\), we have \(1 \le \text{popcount}(n) \le \!\! \left\lfloor \log_2 n \right\rfloor + 1\).

For the cases of \(n = 2, 3\), we can compute that \(\text{popcount}(2) = 1 < 2\) and \(\text{popcount}(3) = 2 < 3\).

For the case of \(n \ge 4\), combining the above inequality and lemma alpha implies \(1 \le \text{popcount}(n) \le \! \left\lfloor \log_2 n \right\rfloor + 1 < n\) as wanted.

Lemma gamma

For each \(n \ge 1\), the set of all values from iterating \(\text{popcount}\) on \(n\) contains the value \(1\).

Formally speaking, \(\forall n \in \mathbb{N}^+, \: 1 \in \{\text{popcount}^{(k)}(n) \: | \: k \in \mathbb{N} \}\).

Call this set as \(S\), which we know is a subset of the natural numbers. We know that the set is non-empty because it contains \(n\) when \(k = 0\). By the well-ordering of natural numbers, \(S\) must have a minimal element \(m\).

If \(m\) is at least \(2\), then this cannot happen because by lemma beta, \(\text{popcount}(m) < m\) but \(\text{popcount}(m) \in S\). \(m\) also is not \(0\) because the \(\text{popcount}\) of a positive integer is positive. So the minimal element must be \(1\), thus \(1\) is in \(S\).

Therefore by the definition of \(S\), there must exist some \(k \in \mathbb{N}\) such that \(\text{popcount}^{(k)}(n) = 1\).


Program demo screenshot