Project Nayuki


Iterated popcount results in 0 or 1

Theorem

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 ≥ 1\), there exists \(k ≥ 0\) such that \(\text{popcount}^{(k)}(n) = 1\).

Proof

(A highly abridged proof for busy, seasoned mathematicians: \(1 ≤ \text{popcount}(n) < n\) for all \(n ≥ 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 ≥ 4\), \(n\) is greater than the number of binary digits \(n\) has. More formally: \(\forall n ∈ \mathbb{N}, \: (n ≥ 4 \: ⇒ \: 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 ≥ 2\), we can show that \(1 ≤ \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 ≥ 1\), we have \(1 ≤ \text{popcount}(n) ≤ \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 ≥ 4\), combining the above inequality and lemma alpha implies \(1 ≤ \text{popcount}(n) ≤ \left\lfloor \log_2 n \right\rfloor + 1 < n\) as wanted.

Lemma gamma

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

Formally speaking, \(\forall n ∈ \mathbb{N}^+, \: 1 ∈ \{\text{popcount}^{(k)}(n) \: | \: k ∈ \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) ∈ 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 ∈ \mathbb{N}\) such that \(\text{popcount}^{(k)}(n) = 1\).

Demonstration

Program demo screenshot

Notes