Project Euler, Problem 25: 1,000-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 index of the first term in the Fibonacci sequence to contain 1000 digits?

Because numbers with so many digits are hard to represent in Javascript, I used arrays of numbers instead.

I made a function to add arrays of numbers together from left to right then I kept count of how many Fibonacci numbers I had cycled through. I also used the formula $0.209 \times n \approx digits$ where $n$ is the $n^{th}$ Fibonacci number to act as a checksum and give me a rough idea of what index I should be at.

138,843