Geeks With Blogs
Mark Pearl

 

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


Comments on this post: F# Project Euler Problem 1

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

Your comment:
 (will show your gravatar)


Copyright © MarkPearl | Powered by: GeeksWithBlogs.net