## Project Euler in F# – Problem 25

After a long break, let's try to resume with a regular publication scheme, starting with **Project Euler's problem 25**, an easy one, which says:

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn1 + Fn2, where F1 = 1 and F2 = 1.

...

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?

The problem definition also contains the algorithm to solve it, I told you it was easy.

Actually, we just have to write a function to compute the Fibonacci sequence and stop when a term contains a thousand digits.

Since we don't know when we are done evaluating the terms of the sequence we have to generate an **infinite sequence** and check every new item to see if we can stop.

Let's give a look at the **F#** code:

#light open Microsoft.FSharp.Math.BigInt let has1000Digits (n : Microsoft.FSharp.Math.BigInt) = n.ToString().Length = 1000 let euler25 = ((1I,1I) |> Seq.unfold (fun (n0, n1) -> (if has1000Digits n0 then None else Some(n0, (n1, n0 + n1)))) |> Seq.length) + 1

The *Seq.unfold* function is used to generate the infinite sequence, returning *Some* when we want to continue and *None* when we are done searching (i.e. the term has 1000 digits).

In the latter case, the length of the sequence represents the number of elements generated before the one with a thousand digits, so we have to sum 1 to get the desired answer.

GavinSeptember 20th, 2008 - 03:10

A nicer way to check if a number has 1000 digits is:

with this change it runs considerably faster.

MaxwellOctober 3rd, 2008 - 19:15

When I try to paste any of your programs into Visual Studio 2008 with the September CTP of F# (1.9.6.2), I get the following error for line 2:

Error 1

The namespace ‘BigInt’ is not defined.

C:\Users\Owner\Documents\Visual Studio 2008\Projects\FSharp1\FSharp1\Program.fs

2

28

FSharp1Program.cs:

claudioOctober 3rd, 2008 - 22:38

You have to delete the second line, it was only required before the September CTP release.