TAOCP 3.1 Exercise 9
Suppose we are generating a sequence of $2n$-digit numbers in base $b$ by the middle-square method.
Exercise 9. [**] [M14] Prove that the middle-square method using $2n$-digit numbers to the base $b$ has the following disadvantage: If the sequence includes any number whose most significant $n$ digits are zero, the succeeding numbers will get smaller and smaller until zero occurs repeatedly.
Verified: yes
Solve time: 1m07s
Suppose we are generating a sequence of $2n$-digit numbers in base $b$ by the middle-square method. Let $X_k$ be a number in the sequence whose most significant $n$ digits are zero, so that $X_k < b^n$. Then
$X_{k+1} = \text{middle $2n$ digits of } X_k^2 < \text{middle $2n$ digits of } b^{2n} = b^n.$
Thus $X_{k+1} < X_k$. Repeating the process, each successive number is strictly smaller than its predecessor, because squaring a number less than $b^n$ produces a number with at most $2n-1$ digits in the middle portion, and extracting the middle $2n$ digits introduces leading zeros. Therefore, the sequence decreases until eventually $X_m = 0$ for some $m > k$, after which all subsequent numbers are zero.
This demonstrates that if a number in the sequence has its most significant $n$ digits equal to zero, the middle-square method produces a sequence that decreases monotonically to zero, at which point it becomes constant. This completes the proof.
∎