TAOCP 3.2.1 Exercise 1

Take, for example, $m=10$, $a=2$, $c=0$, and $X_0=1$.

Section 3.2.1: The Linear Congruential Method

Exercise 1. [10] Example (3) shows a situation in which $X_4 = X_0$, so the sequence begins again from the beginning. Give an example of a linear congruential sequence with $m = 10$ for which $X_0$ never appears again in the sequence.

Verified: yes
Solve time: 55s


Take, for example, $m=10$, $a=2$, $c=0$, and $X_0=1$. Then

$X_{n+1}=2X_n \pmod{10},$

and the sequence is

$1,\ 2,\ 4,\ 8,\ 6,\ 2,\ 4,\ 8,\ 6,\ldots$

After the first term, the values repeat with period $4$ among ${2,4,8,6}$. Since $1$ does not occur in this cycle, $X_0=1$ never appears again.

Thus a linear congruential sequence with

$m=10,\qquad a=2,\qquad c=0,\qquad X_0=1$

has the required property. Therefore

$\boxed{X_0\text{ never reappears in the sequence.}}$