Project Euler Problem #25:

Problem #25 is yet another problem where having a background in math makes the problem much easier. It is also another question that concerns the Fibonacci sequence. The question reads:

Project Euler Problem 25: 1000-digit Fibonacci number
The Fibonacci sequence is defined by the recurrence relation:

F_n = F_(n-1)+F_(n-2), 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 = 144

The 12th term, F_12, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

There is a specific formula which makes this problem much easier. Using it, we get the following solution:

Solution #1: Logarithmic Approach

Binet’s Formula tells us that the nth Fibonacci number is equal to:

(Credits to Art of Problem Solving for the LaTeX) We can notice that as n gets really big, the second term ((1-sqrt(5))/2)^n gets really small, to the point where it hardly affects the value of the number. Thus, we can safely say that for large values of n, F_n is approximately (((1+sqrt(5))/2)^n)/sqrt(5). If we set this expression equal to the smallest 1000-digit number, 10^999 and solve for n, we can round up to get the index of the first 1000-digit Fibonacci number. Note that because this relies on an approximation, this method will not work for all numbers and will be off by one for some numbers.

At this point, the question essentially revolves around finding ceiling(log_((1+sqrt(5))/2) (sqrt(5)*10^999)). We can easily find this with the following Python 2.7 script:

 '''
 Author: Walker Kroubalkian
 Logarithmic Approach to Project Euler Problem #25
 '''

 import time
 import math

 def projectEulerProblemTwentyFive(n):
     golden = (1+math.sqrt(5))/2
     return int(math.ceil(math.log(math.sqrt(5),golden)+(n-1)*math.log(10, golden)))

 start = time.time()
 print projectEulerProblemTwentyFive(1000)
 print ("--- %s seconds ---" % (time.time() - start))

 '''
 Prints

 4782
 --- 2.121925354e-05 seconds ---

 for input of n = 1000
 '''

And with that, we’re done. As it turns out, Python 2.7 cannot store values greater than 10^999, so I had to use some properties of logarithms to make the solution more efficient.

And with that, we have solved 25 questions, less than 1/26th of all of the problems on Project Euler. I got the achievements “The Journey Begins” and “Easy Prey” for reaching Level 1 by solving 25 problems and solving 25 of the 50 easiest problems, respectively after solving this problem. Here’s a screenshot of me reaching Level 1:

Thanks for reading! I’ll see you tomorrow.