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

• An Introduction to Functional Programming for .NET Developers
• Sequences
• Core.Printf Module

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]