Claudio Cherubino's blog Life of a Googler

19Sep/083

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.

Comments (3) Trackbacks (0)
  1. A nicer way to check if a number has 1000 digits is:

    let has1000Digits n =
       let oneThousandDigits = (BigInt.pow 10I 999I)
       n >= oneThousandDigits
    

    with this change it runs considerably faster.

  2. 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:

    #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
    
  3. You have to delete the second line, it was only required before the September CTP release.


Leave a comment

(required)

No trackbacks yet.