Solution: Huge Fibonacci Number

Solution

In this problem, $n$ might be so huge that an algorithm looping for $n$ iterations will be too slow. Therefore, we need to avoid such a loop. To get an idea of how to solve this problem without going through all Fibonacci numbers $F_i$ for $i$ from $0$ to $n$, take a look at the table below:

Stop and think: Do you see any interesting properties of the last two rows in the table above?

Both these sequences are periodic! For $m = 2$ ...