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:

F

_{n}= F_{n1}+ F_{n2}, where F_{1}= 1 and F_{2}= 1.Hence the first 12 terms will be:

F

_{1}= 1

F_{2}= 1

F_{3}= 2

F_{4}= 3

F_{5}= 5

F_{6}= 8

F_{7}= 13

F_{8}= 21

F_{9}= 34

F_{10}= 55

F_{11}= 89

F_{12}= 144The 12th term, F

_{12}, 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.

Reblogged this on Sutoprise Avenue, A SutoCom Source.

sort of brute force scalable solution. Just have an array of 1000 digits and pretend it is the number. Individually, add the numbers and keep track of the carry. When the 1000th digit is not 0, the first time that happens, stop the counter. I get 4782 with this code.

int main() {

int i,sum,carry,counter;

counter =2;// starting at 2 because intialising a1 and a2 to 1 which means we are counting the third fibo number

int a1[1000],a2[1000],a3[1000];

for( i =0;i<1000;i++)

{ a1[i]=0;

a2[i]=0;

a3[i]=0;

}

a1[0]=1;

a2[0]=1;

while(1) {

carry = 0;

for( i =0;i<1000;i++)

{ sum = carry + a1[i]+ a2[i];

a3[i] = sum % 10;

carry = sum /10;

}

for(i =0;i0)

break;

}

printf(“counter is %d”,counter);

}

Dear Abishek:

Thank you for the solution. In what language did you implement your solution?

I implemented it in C. The code keeps getting cut off when i paste it here. Not sure what is happening.

this is the rest of the code,

a3[i] = sum % 10;

carry = sum /10;

}

for(i =0;i0)

break;

}

printf(“counter is %d”,counter);

}

code got cut off for some reason.

int i,sum,carry,counter;

counter =2;// starting at 2 because intialising a1 and a2 to 1 which means we are counting the third fibo number

int a1[1000],a2[1000],a3[1000];

for( i =0;i<1000;i++)

{ a1[i]=0;

a2[i]=0;

a3[i]=0;

}

a1[0]=1;

a2[0]=1;

while(1) {

carry = 0;

for( i =0;i<1000;i++)

{ sum = carry + a1[i]+ a2[i];

a3[i] = sum % 10;

carry = sum /10;

}

for(i =0;i0)

break;

}

printf(“counter is %d”,counter);

}