Project Euler – Problem # 25 – Solved with Python

It doesn’t take long for the Fibonacci sequence to get really large. This program asks for a stopping number, then loops through those numbers until it gets one of length 1000 digits or more. At only 4782 the Fibonacci number problem is solved.

Problem:

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn1 + Fn2, 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?

One Possible Solution:

def find_fibonacci(n):
    """Find fibonacci"""
    a, b = 0, 1
    for i in range(0, n):
        x = str(a)
        if len(x) == 1000:
            print a
            print "F(n) = ", i
            break
        a, b, = b, a + b

def main():
    """Main program"""
    n = input("\nHow many numbers of the sequence would you like? ")
    find_fibonacci(n)
    
if __name__ == '__main__':
    main()

Project Euler

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s