TAOCP 3.1 Exercise 16
**Exercise 3.
Exercise 16. [**] [15] A sequence generated as in exercise 6 must begin to repeat after at most $m$ values have been generated. Suppose we generalize the method so that $X_{n+1}$ depends on $X_{n-1}$ as well as on $X_n$; formally, let $f(x, y)$ be a function such that $0 \le x, y < m$ implies $0 \le f(x, y) < m$. The sequence is constructed by selecting $X_0$ and $X_1$ arbitrarily, and then letting
$$X_{n+1} = f(X_n, X_{n-1}), \qquad \text{for } n > 0.$$
What is the maximum period conceivably attainable in this case?
Verified: no
Solve time: 4m40s
Exercise 3.1.16 [**]
Let
$$ X_{n+1}=f(X_n,X_{n-1}), $$
where $0\le X_n<m$, and let
$$ S_n=(X_{n-1},X_n). $$
We seek the largest period that can possibly occur.
Upper bound
The state $S_n$ is an ordered pair of elements of ${0,\ldots,m-1}$, hence there are exactly
$$ m^2 $$
possible states.
The recurrence induces the state transition
$$ T(a,b)=(b,f(b,a)). $$
Since the evolution is deterministic, once a state repeats, the entire future evolution repeats. Therefore every cycle of states has length at most the number of available states:
$$ \text{period}\le m^2. $$
Thus $m^2$ is an absolute upper bound.
Can the bound be attained?
We must determine whether there exists a function $f$ for which the induced map
$$ T(a,b)=(b,f(b,a)) $$
has a single cycle containing all $m^2$ states.
Observe first that $T$ is injective if and only if, for each fixed first coordinate $b$, the values
$$ f(b,0),,f(b,1),,\ldots,,f(b,m-1) $$
are all distinct. Indeed, if
$$ T(a_1,b)=T(a_2,b), $$
then
$$ (b,f(b,a_1))=(b,f(b,a_2)), $$
so injectivity requires $f(b,a_1)\neq f(b,a_2)$ whenever $a_1\neq a_2$.
If $T$ is injective on a finite set of $m^2$ states, it is a permutation of those states. Hence, to obtain a cycle of length $m^2$, it suffices to realize a permutation consisting of one $m^2$-cycle.
Let the states be arranged cyclically as
$$ (0,0),(0,1),\ldots,(0,m-1), (1,0),\ldots,(m-1,m-1), $$
with indices taken modulo $m^2$. Denote by $N(a,b)$ the successor of $(a,b)$ in this cyclic ordering.
For each state $(a,b)$, write
$$ N(a,b)=(b,c(a,b)). $$
This is possible because, in the chosen ordering, every state whose second coordinate is $b$ is followed by a state whose first coordinate is $b$.
Define
$$ f(b,a)=c(a,b). $$
Then
$$ T(a,b) =(b,f(b,a)) =(b,c(a,b)) =N(a,b). $$
Therefore $T$ coincides with the prescribed cyclic permutation of all $m^2$ states.
To see explicitly that such a cyclic ordering exists, identify the state $(a,b)$ with the integer
$$ k=am+b \pmod{m^2}. $$
Define
$$ N(a,b) \longleftrightarrow k+1 \pmod{m^2}. $$
If $k=am+b$, then
$$ k+1=bm+c $$
for a uniquely determined $c\in{0,\ldots,m-1}$. Hence the successor of $(a,b)$ has the form $(b,c)$, exactly as required. Defining $f(b,a)=c$ yields a transition map whose orbit runs through all $m^2$ states before returning to the start.
Thus a cycle of length $m^2$ is realizable.
Conclusion
The state space contains $m^2$ states, so no period can exceed $m^2$. A suitable choice of $f$ can make the state transition a single cycle through all $m^2$ states. Therefore the maximum period conceivably attainable is
$$ \boxed{m^2}. $$
∎