Problem 025

Project Euler

1000-digit Fibonacci number

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?

This big integer problem uses similar array of integer (or char) addition strategy found previously. Not able to see any quick mathematical solution, an iterative calculation of each Fibonacci number is used to find the solution. Remember problem 2 where a discussion of Fibonacci number and the golden ratio:

F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}

where \varphi = \frac{1+\sqrt{5}}{2} and \psi = \frac{1-\sqrt{5}}{2} .

Maybe a quicker solution could come from guess and check different value of n to see which n will produce the answer.


Leave a Reply

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

You are commenting using your 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