# Project Euler

### A Taste of Number Theory

#### Problem 25: 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?

#### 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);
}
}
```