makispaiktis

Project Euler 25 - 1000digit Fibonacci number

Sep 24th, 2020
1,004
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. '''
  2. The Fibonacci sequence is defined by the recurrence relation:
  3. Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.
  4. Hence the first 12 terms will be:
  5. F1 = 1
  6. F2 = 1
  7. F3 = 2
  8. F4 = 3
  9. F5 = 5
  10. F6 = 8
  11. F7 = 13
  12. F8 = 21
  13. F9 = 34
  14. F10 = 55
  15. F11 = 89
  16. F12 = 144
  17. The 12th term, F12, is the first term to contain three digits.
  18. What is the index of the first term in the Fibonacci sequence to contain 1000 digits?
  19. '''
  20.  
  21. fibo = list()
  22. target = 1000
  23. targetNumber = 0
  24. targetIndex = 2
  25. fibo.append(1)
  26. fibo.append(1)
  27.  
  28. while len(str(fibo[len(fibo)-1])) < target:
  29.     fibo.append(fibo[len(fibo)-1] + fibo[len(fibo)-2])
  30.     targetNumber = fibo[len(fibo)-1]
  31.     targetIndex += 1
  32.  
  33. # MAIN FUNCTION
  34. print()
  35. print("The first number that contains exactly " + str(target) + " digits is in index = " + str(targetIndex) + " ----> " + str(targetNumber))
RAW Paste Data