## About Project Euler

I’ve wanted to take a crack at Project Euler for some time now. If you’re not familiar, it’s basically a list of mathematical problems. From the site:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

And they keep score! In addition, I’ve also been looking for an excuse to learn F#. In truth, I’ve wanted to get down and dirty with some functional language, to learn the principles and hopefully become a better programmer. I chose F# because it’s part of Visual Studio (starting with 2010), and I’m already handy with .NET, so in theory that will lower the barrier to entry just a little bit. At the very least, it allows me to dodge the hassle of installing another interpreter or environment on my system.

## Blogging It

As I continue though Project Euler, I’ll be posting my solutions here on my site under http://factormystic.net/projects/code, and you can also check my progress by looking at my Project Euler profile and I look forward to your mocking laughter gentle guidance as I fumble around in F#.

## On to 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.

Straightforward enough, and easy to form a mental model around the problem. But how to implement this in F#? For a quick language primer, I skimmed An Introduction to Functional Programming for .NET Developers and noticed a few things I might need:

- An add function

let add x y = x + y

- Sequence syntax and list comprehension

let numbers = {0..10}

- Modulo and ternary operators

string result = x % 2 == 0 ? “yes” : “no”;

## The Thinking

The thinking is this: sequences could be used to build a list of integers 1 to 1000; I could use modulo to get multiples of 3 and 5 (think FizzBuzz), and somehow use that add function to get the sum. Reading the documentation for sequence expressions turned out to be quite rewarding (!), as you can embed a filter on a sequence when you declare it:

[sourcecode]let multiples = seq { for i in 1 .. 1000 do if i % 3 = 0 || i % 5 = 0 then yield i }[/sourcecode]

Yield is already a familiar concept from C#, from using Enumerables. In fact, from the documentation:

Sequences are represented by the seq<‘T> type, which is an alias for IEnumerable<T>. Therefore, any .NET Framework type that implements System.IEnumerable can be used as a sequence. The Seq module provides support for manipulations involving sequences.

Thus our F# is roughly analogous to something like

[sourcecode]public static IEnumerable GiveMults()

{

foreach (int i in Enumerable.Range(1, 1000))

if (i % 3 == 0 || i % 5 == 0)

yield return i;

}[/sourcecode]

Now that we have our sequence of natural numbers, let’s figure out how to sum them up. I have the add function I grabbed from the article, and while poking around with the Seq module, I noticed a reduce function, which can apply an accumulator. That would give us

[sourcecode]

let multiples = seq { for i in 1 .. 1000 do if i % 3 = 0 || i % 5 = 0 then yield i }

let add x y = x + y

let result= Seq.reduce add multiples

printfn “%A” result

[/sourcecode]

(Side note: printfn is how we can write to stdout, much like Console.Writeline. The “%A” stuff works like string.Format parameters- %A indicates “Formats any value, printed with the default layout settings.” In the case of a sequence, that means printing the first few values)

…and that code does indeed sum the multiples, as you would expect. But there is a better way. After all, we should expect something as simple as adding up a list to be built in already, and we do have our Seq module functions available.

Indeed, there is a Seq.sum function that does exactly what we’re seeking to do, sum a sequence. Rewritten, we have:

[sourcecode]

let result = seq { for i in 1 .. 1000 do if i % 3 = 0 || i % 5 = 0 then yield i }

let total = Seq.sum result

printfn “%A” total

[/sourcecode]

And this prints an answer, but that answer is WRONG. See the bug? The original problem stated that we’re to “sum of all the multiples of 3 or 5 **below** 1000″, but the list comprehension syntax (1..1000) is **inclusive**. Thus, our answer includes 1000, which is evenly divisible by 5, and is summed into the final total. The fix is simple, just write 1..999:

## My Solution

[sourcecode]

let multiples = seq { for i in 1 .. 999 do if i % 3 = 0 || i % 5 = 0 then yield i }

let result = Seq.sum multiples

printfn “%A” result

[/sourcecode]

Bingo.

Project Euler Problem 1: **Answered**

## Further Reading

## A Post Script

For the code golf crew:

[sourcecode]printfn “%A” (Seq.sum (seq { for i in 1 .. 999 do if i % 3 = 0 || i % 5 = 0 then yield i }))[/sourcecode]

Pingback: Project Euler in F#: Problem 2 « Factor Mystic

Jace RheaVery nice. I came up with a similar solution.

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