1000-digit Fibonacci number
The Fibonacci sequence is defined by the recurrence relation:
What is the index of the first term in the Fibonacci sequence to contain 1000 digits?
Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.Hence the first 12 terms will be:
F1 = 1The 12th term, F12, is the first term to contain three digits.
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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 |
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🙂.