10689 - Yet another Number Sequence
Solution Description : Fibonacci ( Pisano period) number problem The last digit of Fibonacco number repeats with a period of 60. The last two digits repeat with a period of 300, the last three with a period of 1500 and the last four digits have a period of 15000. (For more information you can search in google about Pisano period). f(0) = 1*a + 0*b f(1) = 0*a + 1*b f(2) = 1*a + 1*b f(3) = 1*a + 2*b f(4) = 2*a + 3*b f(5) = 3*a + 5*b f(6) = 5*a + 8*b f(7) = 8*a + 13*b so, f(n) = Fibonacci_number[n-1]*a + Fibonacci_number[n]*b You can find Fibonacci_number using the rule of Pisano period. If m=4 you need to calculate fist 15000 Fibonacci number (you need to store last 4 digit). If m=3 you need to calculate fist 1500 Fibonacci number (you need to store last 3 digit). and so on. I think now the problem very easy. |
||||||||||