Every now and then I give project Euler a quick browse. Since I have been playing with F# I have found it a great way to learn the basics of the language. Today I thought I would give problem 1 an attempt…

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.

My F# Solution

I broke this problem into two functions… 1) be able to generate a collection of numbers that are multiples of a number but but are smaller than another number.

let GenerateMultiplesOfXbelowY X Y =
X |> Seq.unfold (fun i -> if (i<Y) then Some(i, i+X) else None)

I then needed something that generated collections for multiples of 3 & 5 and then removed any duplicates. Once this was done I would need to sum these all together to get a result. I found the Seq object to be extremely useful to achieve this…

let Multiples =
Seq.append (GenerateMultiplesOfXbelowY 3 1000) (GenerateMultiplesOfXbelowY 5 1000)
|> Seq.distinct
|> Seq.fold(fun acc a -> acc + a) 0
|> Console.WriteLine
|> Console.ReadLine

My complete solution was …

open System
let GenerateMultiplesOfXbelowY X Y =
X |> Seq.unfold (fun i -> if (i<Y) then Some(i, i+X) else None)
let Multiples =
Seq.append (GenerateMultiplesOfXbelowY 3 1000) (GenerateMultiplesOfXbelowY 5 1000)
|> Seq.distinct
|> Seq.fold(fun acc a -> acc + a) 0
|> Console.WriteLine
|> Console.ReadLine

Which seemed to generate the correct result in a relatively short period of time although I am sure I will get some comments from the experts who know of some intrinsic method to achieve all of this in one method call.

Posted on Thursday, June 17, 2010 9:56 PM
F#
| Back to top

Related Posts on Geeks With Blogs
Matching Categories

I was thinking about this problem while reading about sequence comprehensions, and it occured to me that there's a way solve this problem by "tricking" the compiler into doing most of the work for you:

let euler1 d0 d1 n = (seq {0..d0..n} |> Seq.sum) + (seq {0..d1..n} |> Seq.sum) - (seq {0..d0*d1..n} |> Seq.sum)

I also wanted to find a way to solve this without using branching (explicitly) and trying to be more declarative. I just started learning F# a couple of days ago. I'm pretty jazzed about finding the ||> operator which passes two arguments (effectively) to a curried function.

I could have said " set1 |> ( set2 |> Set.union) " but that's ugly I think. I could have also said: let ... = set1 |> Set.union set2 |> ....

but I didn't like that either... kind of inconsistent, eh ? The spirit of pipelining is natural readability. a applied to (f applied to b) feels awkward.

seq { 1 .. 999 }

|> Seq.filter (fun i -> i%5 = 0 || i%3 = 0)

|> Seq.sum

let euler1 d0 d1 n =

(seq {0..d0..n} |> Seq.sum) +

(seq {0..d1..n} |> Seq.sum) -

(seq {0..d0*d1..n} |> Seq.sum)

let x = euler1 3 5 999

-Neil

let euler1000 =

(set { 0 .. 3 .. 1000 }, set { 0 .. 5 .. 1000 })

||> Set.union

|> Set.toSeq

|> Seq.sum

I could have said " set1 |> ( set2 |> Set.union) " but that's ugly I think.

I could have also said:

let ... =

set1

|> Set.union set2

|> ....

but I didn't like that either... kind of inconsistent, eh ? The spirit of pipelining is natural readability. a applied to (f applied to b) feels awkward.

Danny

let problem1 =

seq { 0..999 }

|> Seq.sumBy (fun x -> if x % 3 = 0 || x % 5 = 0 then x else 0)