6
$\begingroup$

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)$.

  • 0
    On repeated squaring of the shift matrix see also [here](http://math.stackexchange.com/questions/11477/showing-that-an-equation-holds-true-with-a-fibonacci-sequence-f-nm-f-n-1/11482#11482) and [here](http://math.stackexchange.com/questions/28157/exponential-equation/28201#28201) (for Fib's, but the analogy for Trib's or any constant coef linear recursion is clear).2011-06-16

2 Answers 2

1

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$.

  • 0
    Yes, that is correct.2011-06-16
3

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.

  • 1
    He actually wants $T(y)$ for some y > 2^{40} (not just $y = 2^{40}$), but otherwise this answer is fine. To compute $f^y$ we use exponentiation by squaring, as Qiaochu said.2011-06-16