Pretty cool Fibonacci

Computer Science Level 5

Let ${ F }_{ n }$ be the $n$ th Fibonacci number. Find the first four digits of the number of digits of ${ F }_{ p }$ , where $p={ 10 }^{ 12 }$ .

Details: ${ F }_{ n }={ F }_{ n-1 }+{ F }_{ n-2 }$ and ${ F }_{ 0 }=0$ and ${ F }_{ 1 }=1$ .

1 solution

First Last
Dec 7, 2016

In general the number of digits of a number in base 10 is $\log_{10}{\text{number}}$

Using Binet's Formula for $F_n = \displaystyle\frac{\big( \frac{1+\sqrt{5}}{2}\big)^n-\big( \frac{1-\sqrt{5}}{2}\big)^n}{\sqrt{5}}$

and the fact that $\displaystyle\big( \frac{1-\sqrt{5}}{2}\big)^n$ is essentially 0 at $n = 10^{12}$

Then the number of digits is $\displaystyle 10^{12}\log_{10}{\frac{1+\sqrt{5}}{2}} \mod 10^{8} = \boxed{2089}$

Almost any calculator can evaluate $\displaystyle\log_{10}{\frac{1+\sqrt{5}}{2}}$ and you take the first 4 digits after the decimal.