Problem 25 : 1000-Digit Fibonacci Number

1000-digit Fibonacci number

Problem 25

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n−1 + F_n−2, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.
What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

                                                                                                       (https://projecteuler.net/problem=25)
Okie, guys. We are going to explore Fibonacci Sequence.

If we say

                                                                       F₀=0, F₁=1,

then

F_n = F_n-1 + F_n-2
So the Recursive Definition of Fibonacci Sequence would be our focus.

And here is a formula for finding the nth term of Fibonacci sequence:

                                                         a_n = [ Phiⁿ - (phi)ⁿ ]/Sqrt[5]                                                           

where Phi = (1+Sqrt[5])/2 is golden ratio (1.61803398875), and phi = (1-Sqrt[5])/2 is an associated golden number.

(phi also equals to -1/Phi)

Yes, Fibonacci number is related to the golden number. It is as beautiful as that ratio in nature.

(Yet there are lots of disputes on the existence of "golden ratio" and its aesthetic impact. You can google them later.)

Anyway this problem requires the number TOO LARGE to use int data type. We are going to use BigInteger instead.

Set the limit first:

private static final int DIGIT = 1000;
private static final BigInteger LIMIT = BigInteger.TEN.pow(DIGIT-1);

Then initialize the starting terms of the recursive function:

int index = 2; // f1 and f2
BigInteger f1 = BigInteger.ONE, f2 = BigInteger.ONE;

Finally, implement the recursion:

while (f2.compareTo(LIMIT) < 0)
{
    BigInteger temp = f1.add(f2);
    f1 = f2;
    f2 = temp;
    index++;
}
System.out.println(index);

Answer is 4782
Execution time is 5.803691 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem025.java