Project Euler in F# - Problem 1

  • Article

A while ago I found a wonderful website called Project Euler, which provides a steady stream of interesting mathematical/algorithmic problems to solve. If you are sufficently clever you can potentially solve most problems symbolically with pen and paper. I, however, have been sticking to C# :)

With the latest news about baking F# into Visual Studio I figured re-solving the problems from Project Euler would be a great way to learn F# and hopefully come up with cleaner solutions. This post will go over my solution for problem 1 in F#. Since I am still learning, this might not be the best way to solve it; so if you can think of a better way let me know.

Problem 1 is defined as follows:

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.

Solution in F#

#light
 

let problem1 =

    let Mod35 x =

        if x % 3 = 0 then true

        else if x % 5 = 0 then true

        else false

    let numbers = [1 .. 999]

    numbers |> Seq.fold

        (fun acc x -> if Mod35(x) then

                          acc + x

                      else

                          acc) 0
 

printfn "Problem 1 = %d" problem1

This may look strange to some of you, but the code is actually straightfoward. Let's walk through it line by line.

First, we start by defining a function 'problem1'. Within that function, we define a new function 'Mod25' which takes a parameter x. Mod35 simple returns whether or not the parameter modulus three of five retuns zero. So far so good.

Next, I create a list of integers from one to 999.

Finally I use the 'Seq.fold' operation. I'll probably devote an entire blog post to cool things you can do with Seq.fold later, but for now think of it is summerizing a list. It performs some computation over every element in a list and keeps track of a variable. In the code I am looping through all integers 1 to 999 and if they are divisible by three of five then I add it to the 'acc' accumulator variable, otherwise I just pass the current accumulator variable onward. That trailing 0 simply initializes acc.

Notice the lack of a 'return' statement. The last computation preformed is the Seq.fold operation, which summed up the list of integers divisible by three or five. So on the last line we print whatever number is returned by function 'problem1'.

If after reading this F# still doesn't make sense don't worry! I'll be posting more problems / solutions in the future to give you some more examples; but in the mean time I would strongly encourage you to download the latest build and start playing with it.

Again, thanks to the folks at Project Euler. Once the easy less-challenging problems are out of the way I'll be sure to tweak the problems slightly.

Edit: Added '#light' declaration at top of code
Edit2: Please check out the 'comments' for this post if you haven't already, Robert Pickering posted two much more elegant alternatives to my solution. I don't feel too bad, since everything I know about F# I read in his book Foundations of F#.

Comments

  • Anonymous
    October 24, 2007
    Good idea.  However, it didn't work, using the latest F# compiler, without adding a couple of in's for the two latter let's.

  • Anonymous
    October 24, 2007
    Thanks for the note!  Yes, you can either add the 'in' keyword or declare #light at the top of the file. Don Syme has more information at: http://blogs.msdn.com/dsyme/archive/2006/08/24/715626.aspx I've updated my post.

  • Anonymous
    October 24, 2007
    My bad, first time using F# and the Euler relation intrigued me.  Although, I could swear the script that F# generated had #light somewhere at the top.  However, I'll try

  • Anonymous
    October 25, 2007
    Hi Chris, Nice effort, here are a couple of alterantive implmentations, which are a little shorter, first you could use a filter instead of adding the Mod35 predicated to your fold function:    let problem1 =        [1 .. 999]        |> Seq.filter (fun x -> x % 3 = 0 || x % 5 = 0)        |> Seq.fold (+) 0          printfn "Problem 1 = %d" problem1 Alternatively you can use step feature list comprehensions to remove any need to for filtering:    let problem1 =        [1 .. 3 .. 999] @ [1 .. 5 .. 999]        |> Seq.fold (+) 0          printfn "Problem 1 = %d" problem1

  • Anonymous
    November 12, 2007
    try this: Seq.fold1 (+) {for i in 1..999 when i%3*i%5=0 -> i}

  • Anonymous
    November 20, 2007
    I'm please to announce that starting Monday I'll be joining the F# team as (currently) the only full-time tester. I'm super-excited about this for many reasons, but the biggest is knowing what an impact I'll have. Without a doubt F# will change the .Net

  • Anonymous
    February 05, 2008
    Week 2: My adventures with Euler #2

  • Anonymous
    December 24, 2008
    Note that the second solution that Robert Pickering gives above is incorrect.

  • Anonymous
    February 02, 2009
    @ Michael de la Maza The second solution Pickering has provided should begin the list comprehension from 0 rather than 1.

  • Anonymous
    February 02, 2009
    @ Michael de la Maza Starting from 0 rather than 1 is more right, but only half way right.   Appending the two lists [1 .. 3 .. 999] @ [1 .. 5 .. 999] also includes duplicate numbers that are divisable by both 3 and 5. val it : int list = [15; 30; 45; 60; 75; 90; 105; 120; 135; 150; 165; 180; 195; 210; 225; 240;   255; 270; 285; 300; 315; 330; 345; 360; 375; 390; 405; 420; 435; 450; 465;   480; 495; 510; 525; 540; 555; 570; 585; 600; 615; 630; 645; 660; 675; 690;   705; 720; 735; 750; 765; 780; 795; 810; 825; 840; 855; 870; 885; 900; 915;   930; 945; 960; 975; 990]