Fibonacci? No, It is Tribonacci!

After a first glance at the problem,I assumed that answer could be acquired with a simple variation of the DP Algorithm for finding the $nth$ Fibonacci number.The best know Time Complexity of that algorithm is $O(n)$ .

But after a second look at the large input of the problem,I realized that my naive approach would never work.Even though it was $O(n)$ , it would amount to $10^{12}$ computations. I figured there must be some sort of pattern that would cut the run-time so I searched for a cycle in the last three digits of the Tribonacci sequence and lo and behold! I found that the last three digits of the Tribonacci sequence repeated on a cycle of length $12400$ .

That reduced the number of computations necessary to $10^{12}$ mod $12400$ . Hence the answer was just a matter of finding the last three digits of $f(10^{12} \mod 12400)=f(3600)=516$ .

The code for finding $f(n)$

def f(n): #Returns f(n)
    Fn = 3
    F= [ 3 , 2 , 1 ]
    while Fn < n:
        F = [F[1],F[2],sum(F)%1000]
        Fn += 1
    return F[-1]

This finds the length of the cycle

Fn  = 3
F = [ 3 , 2 , 1 ] 
while True:
    F = [ F[1] , F[2], sum( F ) % 1000]
    Fn += 1
    if F == [ 3 , 2 , 1]:
        Cycle = Fn - 3   
        print 'The length of the cycle is',Cycle     
        break

This prints out the final answer 516 using the above code

print f(pow(10,12) % Cycle)

The idea for calculating big fibonacci numbers is using the matrix formula. (As seen in http://mathworld.wolfram.com/FibonacciQ-Matrix.html)

So we are going to try that same argument. Basically you want some matrix $T$ so that $M_n*T=M_{n+1}$ where $M_{n-4}=\begin{pmatrix} f(n-2) & f(n-1) & f(n) \\ f(n-3) & f(n-2) & f(n-1)\\ f(n-4) & f(n-3) & f(n-2) \end{pmatrix}$

It is not hard to see that

$T=\begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 1\\ 0 & 1 & 1 \end{pmatrix}$

works. (It is like translating the second column to the first, the third to the second and the sum to the third).

By induction, $M_n=M_0\times T^{n}$ .

For convenience, define F(0) = -4, and compute F(4)=3+2+1=6 then

$M_0=\begin{pmatrix} 2 & 1 & 6 \\ 3 & 2 & 1\\ -4 & 3 & 2 \end{pmatrix}$

So we can compute $M_{10^{12}}=M_0\times T^{10^{12}}$ .Because we are only interested in the last 3 digits, we take the product always modulo 1000. (Or in $\mathbb{Z}/1000\mathbb{Z}$ if you are fancy). The nice thing is that linear functions are still linear modulo 1000, so the computation does not breaks.

And to actually calculate $M_0\times T^q$ with $q=10^{12}$ you use fast exponentiation (ie. recursively $T^{2n}=(T^n)^2$ and $T^{2n+1}=(T^n)^2*T$ , all in matrix multiplications). Then you multiply $M_0\times (T^q)$ and so in the lowerleft corner is $f(10^{12})$ .

At first, I tried the naive approach, by writing a program that calculated all the Tribonacci numbers (mod 1000) one by one. (I used Matlab.) However, I realized that this would take like 8-10 hours for my Lenovo intel Core i5--to be honest I actually tried it but decided to stop it when the program was 71% done because I knew there was a better way XD. So, instead, I calculated the first one million Tribonacci numbers, putting them into an array, then identified a number sequence with length four at random (I figured length four would be sufficient). However, I later realized that three is sufficient. Then I wrote a simple code which recorded all the appearances of this number sequence into an array. It was not to my surprise that these appearances were equally spaced as in the Fibonacci sequence (the same four numbers must occur twice in sequence by the pigeonhole principle, and the same pattern must follow each time because we are following the same rule). The spacing between each occurrence was 12400. So, all I needed to do next was to type 10^12 (mod 12400) into Matlab, which gave me an answer of 3600. So, the 10^12th term mod 1000 was the same as the 3600th term mod 1000. The value of the 3600th term mod 1000 was 516. Hence, the answer is 516.