TAOCP 3.1 Exercise 17
In the generalized scheme, each term is determined by the preceding $k$ values: X_{n+1}=f(X_n,X_{n-1},\ldots,X_{n-k+1}), where $0\le X_i<m$.
Exercise 17. [**] [10] Generalize the situation in the previous exercise so that $X_{n+1}$ depends on the preceding $k$ values of the sequence.
Verified: yes
Solve time: 1m22s
In the generalized scheme, each term is determined by the preceding $k$ values:
$$ X_{n+1}=f(X_n,X_{n-1},\ldots,X_{n-k+1}), $$
where $0\le X_i<m$. The state of the process at any time is therefore completely specified by the ordered $k$-tuple
$$ (X_n,X_{n-1},\ldots,X_{n-k+1}). $$
There are exactly $m^k$ possible states. Since the transition from one state to the next is deterministic, a sequence of states cannot pass through more than $m^k$ distinct states before a repetition occurs. Hence the period of any cycle is at most $m^k$.
This bound is attainable. Choose $f$ so that the induced transformation on the set of all $m^k$ states is a single cycle containing every state exactly once. Then, starting from any state, the sequence passes through all $m^k$ states before repeating. Therefore the maximum period conceivably attainable is
$$ \boxed{m^k}. $$