The Problem

Find the index of the first number in the Fibonacci sequence to contain 1000 digits.

The Solution

Once again, it's BigInteger to the rescue. It is very easy to generate the Fibonacci sequence.

let fibSeq =
    let rec fibSeq n1 n2 = 
        seq { let n0 = n1 + n2 
              yield n0
              yield! fibSeq n0 n1 }
    seq { yield 1I ; yield 1I ; yield! (fibSeq 1I 1I) }

We know the first two elements of the sequence are both 1, so we just yield those directly. For elements after that, we call the recursive fibSeq function, which uses yield to return the sum of the previous two terms, then uses yield! to return the next element in the sequence. This function generates numbers forever, but F#'s sequence magic will only generate the numbers that it needs.

With this in hand, finding the answer is easy.

let aThousandDigits = pown 10I 999

#time
fibSeq
|> Seq.findIndex (fun f -> f >= aThousandDigits)
#time

Other Posts in This Series