1000-digit Fibonacci number
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:
where and .
Maybe a quicker solution could come from guess and check different value of n to see which n will produce the answer.