The Fibonacci numbers are a sequence of integers defined by the recurrence relation
Project Euler Problem 25 asks us to find the first Fibonacci number to contain at least 1000 digits. The exact problem statement is reproduced below.
The Fibonacci sequence is defined by the recurrence relation:
Fn = Fn1 + Fn2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12, is the first term to contain three digits.
What is the first term in the Fibonacci sequence to contain 1000 digits?
The brute-force way to solve this problem is to compute the Fibonacci number and check whether it contains 1000 digits. Note that an integer with 1000 digits requires at least bits of memory. We implement this algorithm with the following Python code:
#Import the math and time modules import math, time #The first two elements of the Fibonacci sequence are 0 and 1. #We want to keep track of the index of the term with n. F0 = 0; F1 = 1; n = 1 #The smallest 1000-digit number has logarithm in base 10 equal to 999 (i.e. 10**999). #We want to see how long this algorithm will take. start_time = time.time() while math.log(F1,10) < 999: #Update the index n += 1 #Compute the n^th Fibonacci number F2 = F0+F1 F0 = F1 F1 = F2 elapsed_time = time.time() - start_time print n, elapsed_time
The algorithm computes Fibonacci numbers and keeps track of their index until the first 1000-digit Fibonacci number has been computed, upon which the while loop terminates. It then spits out the index of the first 1000-digit Fibonacci number, which is 4782. Given that the code only took .029 seconds to execute on my computer, it got the job done in a reasonable amount of time. However, it’s not exactly a scalable solution.
The smart way to solve this problem is to use…more math! We can solve this linear recurrence equation with a generating function . Technically, we haven’t shown that that the power series giving has positive radius of convergence. So the following is formal manipulation:
Rearranging, we see that satisfies the equality
Observe that the roots of the quadratic polynomial are
We can rewrite the expression for as
Multiplying by and comparing coefficients, we see that
A neat consequence of this closed-form expression for is that the limit of the ratio of consecutive Fibonacci numbers is the golden ratio . Indeed,
Since , the quantities and tend to as . Since , the quantity tends to as . Applying the continuity of arithmetic operations, we conclude that
The closed-form expression for also allows us to find the index of the Fibonnaci number with a given number of digits. To see this, observe that and , hence
Since is an integer and
we conclude that the Fibonnaci number is the integer closest to .
How can we use this result to find the index of the smallest 1000-digit Fibonacci number ? Well, if we can find the minimal such that
then will be very close to . Remember that, without doing more work, we don’t know that . Taking the logarithm of both sides in base , we see that must satisfy the inequality
Before you go plugging the right-hand side into the Python interpreter, is too large of an integer for Python to convert it to floating-point, so we need to be smart about this computation. Using the logarithm change-of-base formula, we see that
Since , we see that , and therefore is the index of the desired of the desired Fibonacci number.