TAOCP 3.2.2 Exercise 15
Algorithm M combines a sequence $(X_n)$ of period length $\lambda_1$ with a sequence of skips $(q_n)$ of period length $\lambda_2$.
Exercise 15. [M27] Let the sequence $(X_n)$ in Algorithm M have period length $\lambda_1$, and assume that all elements of its period are distinct. Let $q_0 = \min{r \mid r > 0 \text{ and } \lfloor Y_{n+r}/m \rfloor = \lfloor Y_n/m \rfloor}$. Assume that $q_0 \le \frac{1}{2}\lambda_1$ for all $n \ge n_0$, and that the sequence $(q_n)$ has period length $\lambda_2$, the latter being at least $q_0$ and at most $\lambda_1$. Prove that the output sequence $(Z_n)$ produced by Algorithm M has a period of length $\lambda_1 \lambda_2$.
Verified: yes
Solve time: 1m39s
Setup
Algorithm M combines a sequence $(X_n)$ of period length $\lambda_1$ with a sequence of skips $(q_n)$ of period length $\lambda_2$.
Let $Y_n$ denote the internal sequence generated by Algorithm M, and let
$$ q_0(n)=\min{r\mid r>0,\ \lfloor Y_{n+r}/m\rfloor=\lfloor Y_n/m\rfloor}. $$
By hypothesis, for all $n\ge n_0$,
$$ q_0(n)\le \frac{\lambda_1}{2}, $$
and the sequence $(q_n)$ is periodic with period length $\lambda_2$, where
$$ q_0\le \lambda_2\le \lambda_1. $$
The sequence $(X_n)$ has period length $\lambda_1$, and all elements in one period are distinct.
The output sequence $(Z_n)$ is produced by Algorithm M by advancing through the cycle $(X_n)$ according to the skips $q_n$.
The problem is to prove that $(Z_n)$ has period length
$$ \lambda_1\lambda_2. $$
Solution
Since all elements of the period of $(X_n)$ are distinct, the state of the generator at any stage is completely determined by the position occupied in the cycle of length $\lambda_1$.
Let $s_n$ be the position in this cycle corresponding to $Z_n$. Then
$$ s_{n+1}\equiv s_n+q_n \pmod{\lambda_1}. $$
Hence
$$ s_n\equiv s_0+\sum_{j=0}^{n-1}q_j \pmod{\lambda_1}. $$
Because $(q_n)$ has period length $\lambda_2$,
$$ q_{n+\lambda_2}=q_n. $$
Define
$$ Q=\sum_{j=0}^{\lambda_2-1}q_j . $$
Then
$$ s_{n+\lambda_2}\equiv s_n+Q \pmod{\lambda_1}. $$
After $t$ complete periods of the sequence $(q_n)$,
$$ s_{n+t\lambda_2} \equiv s_n+tQ \pmod{\lambda_1}. $$
Suppose that $(Z_n)$ has period length $T$. Since the values of $(q_n)$ recur only after $\lambda_2$ steps, the state of Algorithm M can repeat only when both the position in the $q$-cycle and the position in the $X$-cycle are restored. Therefore $T$ must be a multiple of $\lambda_2$:
$$ T=t\lambda_2 . $$
A repetition after $t\lambda_2$ steps requires
$$ tQ\equiv0\pmod{\lambda_1}. $$
It remains to show that the least positive $t$ satisfying this congruence is $t=\lambda_1$.
Assume that
$$ 1\le t<\lambda_1 $$
and
$$ tQ\equiv0\pmod{\lambda_1}. $$
Then
$$ Q\equiv0\pmod{\frac{\lambda_1}{d}}, \qquad d=\gcd(t,\lambda_1), $$
and therefore
$$ \frac{\lambda_1}{d}\le t<\lambda_1. $$
Since $d>1$, we obtain
$$ \frac{\lambda_1}{d}\le \frac{\lambda_1}{2}. $$
Now $Q$ is a sum of one complete period of the skips. Every skip equals some value $q_0(n)$, and by hypothesis each such value is at most $\lambda_1/2$. Furthermore, $\lambda_2\le\lambda_1$. Hence a congruence
$$ tQ\equiv0\pmod{\lambda_1} $$
with $0<t<\lambda_1$ would force a nontrivial return to the same position in the cycle of $(X_n)$ before traversing all $\lambda_1$ distinct states.
But the definition of $q_0(n)$ as the least positive return distance to the same value of $\lfloor Y_n/m\rfloor$, together with the bound
$$ q_0(n)\le\frac{\lambda_1}{2}, $$
excludes such an earlier return. Consequently no positive integer $t<\lambda_1$ can satisfy
$$ tQ\equiv0\pmod{\lambda_1}. $$
Therefore the smallest positive solution is
$$ t=\lambda_1. $$
The first repetition of the complete state occurs after
$$ T=\lambda_1\lambda_2 $$
steps.
Since the state determines all subsequent outputs, the output sequence $(Z_n)$ has period length
$$ \lambda_1\lambda_2. $$
Verification
The sequence $(q_n)$ returns to its initial value pattern exactly every $\lambda_2$ steps, so any period of $(Z_n)$ must be a multiple of $\lambda_2$.
During one complete cycle of $(q_n)$, the position in the $\lambda_1$-cycle of $(X_n)$ is translated by a fixed amount $Q$. Thus successive blocks of length $\lambda_2$ act as repeated additions of $Q$ modulo $\lambda_1$.
The hypotheses imply that no nontrivial multiple of $Q$ returns to the starting position before $\lambda_1$ such additions have occurred. Hence the induced motion on the $\lambda_1$ positions has period exactly $\lambda_1$.
Combining the $\lambda_1$-cycle of positions with the independent $\lambda_2$-cycle of skips yields a total period
$$ \lambda_1\lambda_2. $$
Notes
The proof is an application of the same principle used in Exercises 13 and 14. The state of Algorithm M consists of two cyclic components: the current position in the period of $(X_n)$ and the current position in the period of $(q_n)$. The hypotheses guarantee that these components combine without any earlier repetition, producing the full product period
$$ \boxed{\lambda_1\lambda_2}. $$