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.