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:

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}= 144The 12th term, F

_{12}, 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 |