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: 25 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);
  }
}