Project Euler Problem 1 and 2 in F#

2 minute read

In my journey to learn F#, I have recently discovered the Project Euler site, which is a wonderful collection of small algorithmic problems which you can solve in your favorite programming language.

This is the kind of excercise I needed to get my feet wet with F# after reading about it. So I started with the first two problems listed on the site.

They both deal with sequence of numbers. Having a procedural/object-oriented mindset, I have scratched my head a few times in order to find a declarative solution true to the spirit of a functional program. Everything has become clearer after I've dug some more into the F# Sequences.

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

This is my solution to it:

# light 
let test = 1     
    |> Seq.unfold (fun x -> Some(x, x+1))
    |> Seq.takeWhile (fun x -> x < 1000)           
    |> Seq.filter ( fun x -> x % 3 = 0 || x % 5 = 0)
    |> Seq.sum;;

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Here follows my solution:

let fibonacci_sequence = Seq.unfold (fun (a, b) -> Some(a, (b, a+b))) (0,1)
    |> Seq.takeWhile(fun x -> x <= 4000000) 
    |> Seq.filter(fun x -> x % 2 = 0)
    |> Seq.sum

A few comments:

  • Here I am using the filter method defined on sequences to stop
    the sequence itself at 4 million, therefore I can get by with plain integers. Normally you would want to use BigIntegers for sequences where you'd expect to need handling large numbers.
  • One of my first attempts to this problem did not have the Seq.filter part. I only had the takeWhile like the following:
  • Seq.takeWhile(fun x -> x % 2 = 0 &amp;&amp; x <= 4000000) 

    Unfortunately, this does not work since the takeWhile will interrupt the sequence as soon as it satisfies the first condition (x % 2 = 0); in other words, it yields a sequence consisting only of the value 0, which looked somehow counterintuitive to me at first.

If you are also taking your first steps with F#, you might want to have a look to the best resources to learn it.

Updated:

Leave a Comment