Project Euler — Problem 1 Solution

Introduction

Hav­ing spent a bit of time learn­ing the basics of F# I decid­ed to try my hands on actu­al­ly writ­ing some code and get a bet­ter feel of the lan­guage and get more used to writ­ing func­tion code in gen­er­al. And for that pur­pose, Project Euler pro­vides a great source for small, iso­lat­ed prob­lems well suit­ed for a func­tion­al lan­guage like F#.

As of today there are a total of 300 ques­tions, ordered in such a way that they’re pro­gres­sive­ly more dif­fi­cult to solve, and whilst I’ll be post­ing my own answers writ­ten in F# you could just as eas­i­ly solve these prob­lems in a vari­ety of lan­guages.

Problem

So back to the first prob­lem, here’s the brief:

If we list all the nat­ur­al num­bers below 10 that are mul­ti­ples of 3 or 5, we get 3, 5, 6 and 9. The sum of these mul­ti­ples is 23.

Find the sum of all the mul­ti­ples of 3 or 5 below 1000.

Solution

Here’s a one lin­er solu­tion in F#:

let total = [1..999] |> List.map (fun i -> if i % 5 = 0 || i % 3 = 0 then i else 0) |> List.sum

Let me break down the solu­tion a lit­tle, and go through it step by step.

I start­ed off with [1..999] which is one of many ways you can cre­ate and ini­tial­ize a new list in F#, doing this gives me a list with the val­ues 1, 2, 3, … 998, 999, i.e. all the nat­ur­al num­bers below 1000.

|> is known as the for­ward pipe oper­a­tor, it allows you to pass the result of the left side of the oper­a­tor to the func­tion on the right side. For a C# devel­op­er it is per­haps eas­i­er to sim­ply think of it as chain­ing a cou­ple of meth­ods in a Linq query, e.g.

var total = Enumerable.Range(1, 999).Select(x => x % 3 == 0 || x % 5 == 0 ? x : 0).Sum();

The List.map func­tion lets you apply a func­tion to each ele­ment of a list and put all the results into a new list, as you’ve seen from the above C# code, it pro­vides the same pro­jec­tion capa­bil­i­ty you get with the Enumerable.Select method in Linq.

In this par­tic­u­lar case, I’m sim­ply say­ing “for each ele­ment in the list, return the ele­ment if it’s a mul­ti­ple of 3 or 5, oth­er­wise return 0”, whilst this does not fil­ter out the ele­ments that are not mul­ti­ples of 3 or 5 the final List.sum will sim­ply ignore the zeros returned from the pre­vi­ous func­tion.

You could equal­ly use a pred­i­cate to fil­ter out the ele­ments which are not mul­ti­ples of 3 or 5:

let total = [1..999] |> List.filter (fun i -> i % 5 = 0 || i % 3 = 0) |> List.sum

Notice that the List.filter works sim­i­lar to the Enumerable.Where method in Linq.