Pisano period upper-bound for Tribonacci (3 step Fibonacci)

Question

For the Pisano Period of a 2-step Fibonacci at modulo $n$ a common and simple upper bound, according to this list of open problems, is $n^2-1$. Is there a similar upper bound for the Pisano Period of the Tribonacci (3-step Fibonacci) at modulo $n$?

Answer 1

Yes, $n^3-1$.

Consider any constant-coefficient linear recursion of order $m$. The values mod $n$ are determined by any $m$-tuple of consecutive values mod $n$. There are $n^m$ possible $m$-tuples mod $n$, but if $(0,\ldots, 0)$ occurs the other terms would have to be all $0$. Thus if the sequence is nontrivial there are at most $n^m-1$ distinct possible $m$-tuples, and so the period will have to be at most $n^m-1$.