Problem #25 from Project Euler asks:
What is the first term in the Fibonacci sequence to contain 1000 digits?
The brute force way of solving this is by simply telling the computer to generate Fibonacci numbers until it finds the first one that has 1000 digits. I wanted to look for a more mathematical solution that doesn't require that many computations.
Initially, I expected that by plotting the Fibonacci numbers (mapping the number itself to the number of digits) I would get a logarithmic graph. I only plotted the first few ones and the sequence looked more like it had linear progression (I hope that's the correct mathematical term; I mean similar to $y=x$ functions.)
I also noticed that, roughly, every five numbers the number of digits is increased by 1 — except the four digit numbers (there's only four of them) and the one digits numbers (if you count the first 1, there's six of them).
$$1, 1, 2, 3, 5, 8$$
$$13, 21, 34, 55, 89$$
$$144, 233, 377, 610, 987$$
$$1597, 2584, 4181, 6765$$
$$10946, …$$
Thus, the first number with seven digits would be $n = 5 \cdot (7 – 1)$, which turned out to be correct. However, starting with the tenth digit, the behavior of the sequence changes (or rather, it becomes clear that it's not linear). The first number with 10 digits is not $5 \cdot (10 -1)$, but $5 \cdot (10 – 1) – 1$.
Plotting the sequence for even larger numbers (again, numbers mapped to their digit count), you get a very slight logarithmic curve. For example, the first number with 1000 digits is $5 \cdot (1000 – 43)$ (WolframAlpha).
My question is,
How can the Fibonacci sequence's behavior be abstracted such that the problem can be solved more elegantly, as opposed to using the brute force algorithm.
Edit: Regarding efficiency
The question, I asked mainly to satisfy my curiosity. Doing this by brute-force is probably the best way in a real world application (computers can do it fast and the code is clearer). But (again, just for entertainment) the more efficient solution can still be to use a mathematical formula to find the index of the number you're looking for; here's why:
- Conditionals are expensive. Doing fewer of them is always good, and the brute-force approach requires you to do a check on every number you generate.
- Some languages (like C++ and D) allow you to do tricks like generating part of the Fibonacci sequence at compile-time (see meta-programming). This means less work at run-time, though admittedly, this could also apply to the brute-force approach.
Not doing checks on the numbers, as well as generating many of them at compile time, can significantly make the algorithm faster (but only in a theoretical sense; most computers nowadays are fast enough that no human will ever notice the difference unless you do the computations a couple of times a second).
Besides, the process of counting the digits of a numbers — required by the brute-force approach — is itself pretty expensive, whether you use the $\lceil\log_{10}n \rceil$ algorithm or the $n\mod10$ algorithm.
Best Answer
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.