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