# Project Euler problem 25 solution

February 25, 2017 by Bibek tags: mathWhat is the index of the first term in the Fibonacci sequence to contain 1000 digits?

The question actually asks to find the first fibonacci term, whose number of digits crosses 1000.

An obvious way to solve it is to brute force all the way to find Fn
(nth Fibonacci number) such that *l**o**g*_{10}(*F*_{n}) is 1000.
The solution becomes too easy if we use the Golden ratio *ϕ* = 1.61803398875

After some research on Golden ratio and Fibonacci numbers, we can find out an important fact that

ϕ^{n − 2}≤F_{n}

Now, if a number N has n digits in it then, *l**o**g*_{10}*N* = *n* − 1
. For example, *l**o**g*_{10}100 = 2 and *l**o**g*_{10}999 = 2.999.
So, for 1000 digits, its logarithm is 999
because both 100 and 999 have 3 digits.

Using this fact in the above inequality(greater than sign is omitted as we are concerned with the first number to have 1000 digits),

*l**o**g*(*ϕ*^{n − 2}) = 999

*o**r*, (*n* − 2) ∗ *l**o**g*(*ϕ*) = 999

*o**r*, (*n* − 2) ∗ 0.2089 = 999

which gives *n* = 4782, our answer.
Cheers!!