43
$\begingroup$

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:

  1. 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.
  2. 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.

  • 0
    @Hannesh I know, but I was talking about a more general algorithm that counts the digits, not one that checks whether a number is within a certain range.2011-09-06

7 Answers 7

12

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.

  • 0
    @Henning See my edit regarding efficiency.2011-09-06
12

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.

  • 3
    @Henning: the format of the desired answer has been questioned several times, and the [Project Euler guidance](http://forum.projecteuler.net/viewtopic.php?f=50&t=1296) is clear.2011-09-04
7

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.

plot of number of digits of Fibonacci numbers

  • 15
    I particularly like the plot of the imaginary part.2011-09-04
1

The other answers giving exact forumlas for Fibonacci numbers are spot on, but if you don't have them handy, you can also solve this problem by shifting the computation to the logarithmic domain. Calculate the log, base 10, of each number, and add it to a double-precision sum; as soon as the value equals or exceeds 999 (i.e. the log, base 10, of the lowest number with 1000 digits), you've reached the right Fibonacci number.

1

The answers you have got so far will help you finding the index of the first Fibonacci number greater than $10^{999}$, but are not particularly useful for finding that Fibonacci number itself, with all is 1000 digits.

For that, I think you have no choice but compute the Fibonacci sequence far enough. If you know the index in advance you can use that to decide how far to go in the computation, but that does not seem to be a significant improvement over simply checking whether each successive Fibonacci number has reached 1000 digits -- you need to compute them all anyway.

The point of the exercise must be that a naive implementation of the Fibonacci sequence (top-down, with two recursive calls in each step) is not going to complete for these sized until well after the heat death of the universe. But if you compute the sequence from the bottom up, saving all of them in an array, and simply pull the two previous numbers out of the array at each step, it's all fast and straightforward.

(You'll need an arbitrary-precision integer arithmetic library if your programming language doesn't already provide one, of course).

  • 0
    @Peter is on the right track. I think that a very efficient approach is to first find the index using the approximation method, and then do matrix exponentiation with the square and multiply algorithm (or some such). That we only need to do $O(\log_2n)$ matrix multiplications to compute the required $F_n$. If they accept the last 8 digits as an answer (admittedly the question posed here was different:-), then it suffices to do the matrix powers mod $10^8$ meaning that 64-bit integers would suffice.2011-09-06
0

The brute force method IS the elegant method. Compare the gyrations and convolutions above to: find each Fibonnaci number in sequence, count the number of digits, stop at the first one with 1,000 digits (if any).

  • 0
    @Henning I asked the question to satisfy my curiosity, because brute force is completely uninteresting. :) Even so, for very large numbers the non-brute-force approach may be faster. Brute force implies doing a check on every number you generate, and [conditionals are expensive](http://stackoverflow.com/questions/315306#315382). It might (theoretically) be better to know ahead of time how many numbers you have to generate, so you don't have to do any more checks.2019-01-21
0

Violating both the terms of the question and good taste, I spent 1.5 minutes and wrote a program to solve this. Being a computer scientist, it was an irresistible temptation.

Python seems the logical choice for something quick: it has arbitrary precision integers built in.

Solution deleted due to comment below

  • 0
    @Fixee: thanks fo$r$ $r$emoving the exact answer $p$art of your answer. I'm not terribly familiar with PE either, but you can get a sense of what it's about here: http://projecteuler.net/index.php?section=about. After you read this, I hope you will still agree that posting exact answers may spoil things for some people.2011-09-06