Geeks With Blogs

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

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

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.

Related Posts on Geeks With Blogs Matching Categories

Comments on this post: F# Project Euler Problem 1

# re: F# Project Euler Problem 1 Here's how I'd do it:

seq { 1 .. 999 }
|> Seq.filter (fun i -> i%5 = 0 || i%3 = 0)
|> Seq.sum
Left by Keith on Jun 18, 2010 12:46 AM

# re: F# Project Euler Problem 1 lol... I knew there would be a neater way of doing it... thanks Keith!
Left by Mark Pearl on Jun 18, 2010 3:49 PM

# re: F# Project Euler Problem 1 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)

let x = euler1 3 5 999

-Neil
Left by TechNeilogy on Jun 20, 2010 9:26 PM

# re: F# Project Euler Problem 1 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.

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
Left by Danny on Jun 21, 2010 10:47 AM

# re: F# Project Euler Problem 1 Here's a simple solution:

let problem1 =
seq { 0..999 }
|> Seq.sumBy (fun x -> if x % 3 = 0 || x % 5 = 0 then x else 0)
Left by Joel on Jun 25, 2010 9:04 PM