Tribonacci sequence modulo X The Tribonacci sequence satisfies
$$T(n) = T(n-1) + T(n-2) + T(n-3)$$
with $T(0)=0$, $T(1)=1$, $T(2)=1$. I need to calculate $T(y) \mod 10000$ for $y > 2^{40}$.
How can I make this faster? I know that this is periodic in $(\mathbb{Z}/10000\mathbb{Z})^3$, but I can't find the period.
Any suggestions? My program needs a lot of time to calculate such $T(y)$.
 A: Call $U(n) = (T(n),T(n+1),T(n+2))$.
The recurrence relation means that for all n, $U(n+1) = f(U(n))$ where $f$ is the linear transformation that sends $(a,b,c)$ to $(b,c,a+b+c)$.
Thus, in order to compute $T(n)$, instead of computing every $T(i)$ for every i, you can simply compute the linear transformation $f^n$, apply it to $U(0) = (0,1,1)$ to get $U(n) = (T(n),T(n+1),T(n+2))$.
To compute $f^{2^{40}}$ modulo 10000, write $f$ as a matrix with coefficients in $\mathbb{Z}/10000\mathbb{Z}$, and square it 40 times.  
A: You're right that the sequence is periodic, and its period is less than $(10^4)^3$.
The following pseudocode will calculate the periodicity. The argument $m$ is the number that you are taking the modulus with respect to.
def TribonacciPeriod(m):
    a = 1; b = 1; c = 2 // manually do one iteration
    n = 1
    while (a != 0 or b != 1 or c != 1):
        tmp = (a + b + c) mod m
        a = b; b = c; c = tmp
        n += 1
    return n

This is guaranteed to terminate and return a value less than $m^3$.
