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