Project Euler 104

Pandigital Fibonacci ends


It’s easy to get the last nine digits(just mod 10^9) and we can get the first nine digits using general fomula of Fibonacci numbers: $ f_n = \frac{(\frac{\sqrt{5} + 1}{2})^n + (\frac{\sqrt{5}-1}{2})^n}{\sqrt{5}} $. It is evident that the term $\frac{\sqrt{5} - 1}{2}$ is smaller than 1.0 (more exactly, 0.6xxxxx) and it can be ignored when n is large enough(e.g. n = 10^5). Then we compute $\log_{10}^{f_n}$ and discard it’s integeral part. Now you need figure out the dramatic mothod of calculating the first nine(or eight, any number you want) digits of $f_n$ yourself.