Project Euler problem 25:
The Fibonacci sequence is defined by the recurrence relation:
Fn = Fn−1 + Fn−2, 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?
I made a brute force solution in Python but it takes forever. Can anyone suggest a non brute force solution?
def Fibonacci(NthTerm):if NthTerm == 1 or NthTerm == 2:return 1 # Challenge defines 1st and 2nd term as == 1else: # recursive definition of Fib termreturn Fibonacci(NthTerm-1) + Fibonacci(NthTerm-2)FirstTerm = 0 # For scope to include Term in scope of print on line 13
for Term in range(1, 1000): # Arbitrary rangeFibValue = str(Fibonacci(Term)) # Convert integer to string for len()if len(FibValue) == 1000:FirstTerm = Termbreak # Stop thereelse:continue # Go to next number
print "The first term in the\nFibonacci sequence to\ncontain 1000 digits\nis the", FirstTerm, "term."