#### Problem 25: 1000-digit Fibonacci Number

The Fibonacci sequence is defined by the recurrence relation:
F_{n} = F_{n - 1} + F_{n - 2}, where F_{1} = 1 and F_{2} = 1. Hence the first 12 terms will be:

F_{1} = 1

F_{2} = 1

F_{3} = 2

F_{4} = 3

F_{5} = 5

F_{6} = 8

F_{7} = 13

F_{8} = 21

F_{9} = 34

F_{10} = 55

F_{11} = 89

F_{12} = 144

The 12th term, F_{12}, is the first term to contain three digits. What is the first term in the Fibonacci sequence to contain 1000 digits?

#### The Catch

How to efficiently generate 1,000-digit Fibonacci sequence.

#### The Light

Of course we can use Java's BigInteger class and iteratively generate the Fibonacci sequence until the first instance of a 1,000-digit term appears. However, such an approach might take a few hundred milliseconds.

The article on Fibonacci Number from Wolfram Alpha offers the Binet's Fibonacci Formula, which offers a closed form formula for generating the Fibonacci sequence:
Thus, finding n would give the index of the first Fibonacci number that has 1,000 digits.

#### The Code

public class Problem25 { public static void main(String[] args) { System.out.println(Math.log10(10) * 999.0 + Math.log10(5)/2)/Math.log10(1.61803398875); } }