Project Euler Problem #25

Home/Uncategorized/Project Euler Problem #25

I’m beginning to learn F# and the best way for me to go about that is to start applying it. There are some interesting computational problems over at Project Euler . This post is the continuation of a series of posts each involving a separate Project Euler problem. This post involves solutions to Project Euler problem #25.

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?

Using a version of the Fibonacci sequence generator I coded up for problem #2 modified for Big Integers:

let fibonacci = Seq.unfold (fun (current, next) -> Some (current, (next, current + next))) (1I, 1I)

and the digits-to-sequence function from my solution to problem #20

    let rec digits x =
        let getNextDigit num =
            if num >= 0I then None else 
            (num, 10I) |> BigInt.DivRem |> swap |> Some
        Seq.unfold getNextDigit x

The solution is as simple as counting the digits in each Fibonacci number, and returning the index for the first one with 1000 digits:

    let findFirstXDigitNumber numDigitsToFind = Seq.findIndex (numDigits >> (=) numDigitsToFind)
    let answer numDigitsToFind = fibonacci |> findFirstXDigitNumber numDigitsToFind |> (+) 1

Leave a Comment