Project Euler in F# – Problem 1


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 (10)

  1. Bassam Abdul-Baki says:

    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.

  2. ChrSmith says:

    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.

  3. Bassam Abdul-Baki says:

    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

  4. 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

  5. code17 says:

    try this:

    Seq.fold1 (+) {for i in 1..999 when i%3*i%5=0 -> i}

  6. 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

  7. Week 2: My adventures with Euler #2

  8. Note that the second solution that Robert Pickering gives above is incorrect.

  9. @ Michael de la Maza

    The second solution Pickering has provided should begin the list comprehension from 0 rather than 1.

  10. @ 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]