Problem 25 Project Euler Solution With python

1000-digit Fibonacci number

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n−1 + F_n−2, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.
What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

I know that if you have learned programming(Whatever may be the source) you should have come across this sequence called as Fibonacci sequence named after Fibonacci. Even if you have not come across this sequence at any time in your life, not a problem then to. Fibonacci is a very simple sequence. we start with 0,1, the next number will be 1(0+1), next number will be 2(1+1), next number will be 3(2+1) and so on. Briefly present number in the sequence is the sum of the previous two terms in the sequence.

Now to solve this problem we have used dynamic programming/memorization concept which we have used to solve many of the problems at project Euler in past.

As the value of the present Fibonacci number depends on the previous value, we store the value in some list and for every iteration we use the value back again instead of starting from the scratch. This will save a lot of time as we will not use any extra for loops or extra while loops.

I don't think that there is no more explanation needed for the algorithm because the program itself looks like an algorithm as we have written it in python.

First read the question carefully and then read the program you will understand it easily. Try to take some iteration as an example and insert the values in the program. This will help you understand the program very easily.

Program

File: pep25.py ------------------------- #http://radiusofcircle.blogspot.com #time module for execution time import time #time at the start of program start = time.time() #list to store the fibonacci numbers # added first two numbers of the #fibonacci sequence fib = [0,1] #iterator i = 2 #An infinite loop, breaks #when the number is 1000 digits long while True: #using the function given in question fib_new = fib[i-1]+fib[i-2] #Appending the new fibonacci to the list fib.append(fib_new) #condition to check for 1000 digits if fib_new>10**999: print i break i = i+1 #time at the end of execution end = time.time() #printing the total time for execution print end-start

The code is well commented and I am assuming that you will be able to understand the code easily.

You can download the source code from Github Gist pep25.py

Output

Summary

This problem was pretty easy as we have solved the previous problems. May be we can say that our experience helped us solving this problem. Other than that I don't have any comments on this question. I just want to thank Python.

If you have any doubt or didn't understand anything comment in the comment box below and I will be glad to help you. Please don't hesitate to comment if you have a better code/different code/ if you have any suggestions.

You can also contact me. I will mostly reply to each and every mail ASAP.

Thank you. Have a nice day🙂.

RADIUS OF CIRCLE

Search This Blog