TAOCP 3.1 Exercise 8
Let f(x)=\left\lfloor \frac{x^{2}}{10}\right\rfloor \bmod 100, so that $f(x)$ is the middle two digits of the four-digit representation of $x^{2}$.
Exercise 8. [**] [23] Make a complete examination of the middle-square method in the case of two-digit decimal numbers.
a) We might start the process out with any of the 100 possible values 00, 01, …, 99. How many of these values lead ultimately to the repeating cycle 00, 00, …? [Example: Starting with 43, we obtain the sequence 43, 84, 05, 02, 00, 00, 00, …] b) How many possible final cycles are there? How long is the longest cycle? c) What starting values or values will give the largest number of distinct elements before the sequence repeats?
Verified: no
Solve time: 5m47s
Let
$$ f(x)=\left\lfloor \frac{x^{2}}{10}\right\rfloor \bmod 100, $$
so that $f(x)$ is the middle two digits of the four-digit representation of $x^{2}$. We must study the directed graph on the vertices
$$ {00,01,\ldots,99}, $$
with an edge $x\to f(x)$.
Since every vertex has out-degree $1$, every trajectory eventually enters a cycle. A complete examination is therefore obtained by determining all cycles and the vertices that flow into them.
An exhaustive computation of the $100$ values of $f(x)$ yields exactly the following cycles:
$$ 00\to 00, $$
$$ 10\to 10, $$
$$ 50\to 50, $$
$$ 60\to 60, $$
and
$$ 24\to 57\to 24. $$
Verification:
$$ 10^2=0100\mapsto 10, \qquad 50^2=2500\mapsto 50, \qquad 60^2=3600\mapsto 60, $$
$$ 24^2=0576\mapsto 57, \qquad 57^2=3249\mapsto 24. $$
No other cycles occur.
(a) How many starting values ultimately lead to $00,00,\ldots$?
We determine the basin of attraction of the fixed point $00$.
Tracing every vertex through the directed graph shows that the following $62$ starting values eventually reach $00$:
$$ \begin{aligned} &00,01,02,03,04,05,06,07,08,09,\ &11,12,13,14,16,17,18,19,21,25,27,28,29,31,32,33,36,37,38,\ &41,42,43,44,45,46,54,55,56,58,61,62,63,64,68,69,71,72,73,\ &75,76,77,78,81,82,84,87,89,91,92,93,95,96 . \end{aligned} $$
For example,
$$ 43\to84\to05\to02\to00. $$
Hence
$$ \boxed{62} $$
starting values ultimately lead to the repeating cycle $00,00,\ldots$.
(b) How many possible final cycles are there? How long is the longest cycle?
From the complete graph analysis above, the final cycles are
$$ (00), \qquad (10), \qquad (50), \qquad (60), \qquad (24,57). $$
Thus there are
$$ \boxed{5} $$
distinct final cycles.
Their lengths are
$$ 1,1,1,1,2. $$
Therefore the longest cycle is
$$ 24\leftrightarrow57, $$
which has length
$$ \boxed{2}. $$
(c) What starting values give the largest number of distinct elements before the sequence repeats?
For a starting value $x$, let $L(x)$ be the number of distinct values encountered before the first repetition.
Computing $L(x)$ for all $100$ starting values, the maximum value is attained for
$$ x=42 \quad\text{and}\quad x=69. $$
Indeed,
$$ 42\to76\to77\to92\to46\to11\to12\to14\to19\to36\to29\to84\to05\to02\to00\to00, $$
and
$$ 69\to76\to77\to92\to46\to11\to12\to14\to19\to36\to29\to84\to05\to02\to00\to00. $$
Before the first repetition occurs, these sequences contain
$$ 15 $$
distinct values:
$$ 42,76,77,92,46,11,12,14,19,36,29,84,05,02,00, $$
and similarly for $69$.
Thus the largest possible number of distinct elements before repetition is
$$ \boxed{15}, $$
and it is achieved precisely by the starting values
$$ \boxed{42 \text{ and } 69}. $$
(Equivalently, the longest tail before entering a cycle has length $14$, since the repeated cycle is the fixed point $00$.)
$$ \boxed{ \begin{array}{l} \text{(a) }62\text{ starting values eventually reach }00.\[2mm] \text{(b) The final cycles are }(00),(10),(50),(60),(24,57);\ \qquad\text{there are }5\text{ cycles, and the longest has length }2.\[2mm] \text{(c) The maximum number of distinct values before repetition is }15,\ \qquad\text{attained by the starting values }42\text{ and }69. \end{array} } $$