Project Euler, Problem #25

Solution 1:

The sequence $n \mapsto F_n$ grows exponentially. In fact, I suggest you look at this part of the wikipedia article on Fibonacci numbers, which gives exact and nearly exact formulas for $F_n$ as exponential functions. This should be very helpful in determining the smallest $n$ such that $F_n$ has $1000$ digits.

Solution 2:

The $n$-th Fibonacci number is given by the following formula: $$F_n = \left\lfloor \frac{\phi^n}{\sqrt 5} + \frac12 \right\rfloor,$$ where $\displaystyle\varphi = \frac{1+\sqrt 5}{2}$. Equivalently, $F_n$ is the integer closest to $\displaystyle\frac{\varphi^n}{\sqrt 5}$. Thus, $\log_{10}F_n$ is very, very close to $\displaystyle n \log_{10}\varphi - \frac12 \log_{10}5$. Since the number of digits in the integer $m$ is $\lceil\log_{10}m \rceil$, so $-$ ignoring that very small discrepancy, which shouldn’t matter with numbers of this size $-$ you want the smallest $n$ such that $$\displaystyle n \log_{10}\varphi - \frac12 \log_{10}5 > 999.5.$$

Added: I guessed wrong about the effect of the discrepancy. By actual calculation it turns out that the value estimated from the inequality above is a little too small.

Solution 3:

Here is a useful fact, for any positive number n, the number of digits of n in base 10 is given by:

$$\lfloor\log_{10}(n)\rfloor + 1$$

The number of digits of the Fibonacci sequence grows linearly, as can be shown in the graph.