Problem Euler #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?
import time ts = time.clock() def fib(): n, m = 0, 1 while True: yield n n, m = m, n + m def extract_pos(it, digits): i = 0 for f in fib_generator: if len(str(f)) == digits: return i i += 1 if __name__ == '__main__': fib_generator = fib() num = extract_pos(fib_generator, 1000) print num print time.clock() - ts