princeofsudan

Project Euler#25 1000-digit Fibonacci number

Mar 10th, 2013
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.74 KB | None | 0 0
  1. #The Fibonacci sequence is defined by the recurrence relation:
  2.  
  3. #    Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.
  4.  
  5. #Hence the first 12 terms will be:
  6.  
  7. #    F1 = 1
  8. #    F2 = 1
  9. #    F3 = 2
  10. #    F4 = 3
  11. #    F5 = 5
  12. #    F6 = 8
  13. #    F7 = 13
  14. #    F8 = 21
  15. #    F9 = 34
  16. #    F10 = 55
  17. #    F11 = 89
  18. #    F12 = 144
  19.  
  20. #The 12th term, F12, is the first term to contain three digits.
  21.  
  22. #What is the first term in the Fibonacci sequence to contain 1000 digits?
  23.  
  24. def fib(n):
  25.     """assumes x an int >= 0
  26.      returns Fibonacci of x"""
  27.     a, b = 0, 1
  28.     for i in range(n):
  29.         a, b = b, a + b
  30.     return a
  31.  
  32. i = 1
  33. while True:
  34.         temp = str(fib(i))
  35.         if len(temp) >= 1000:
  36.                 break
  37.         i += 1
  38. print i
Advertisement
Add Comment
Please, Sign In to add comment