Browsing through Nate Hoellein's blog recently led me to Project Euler. This is a problem - I have a horrendous feeling I'm about to get addicted to it, to the cost of just about everything else that normally occupies my free time. Ack.

Still, at least it provides some blogging material. I'm going to start working my way through the list, and try to create idiomatic solutions in a number of languages. I won't always look for the most efficient solution, since I'm also interested in expressiveness (see here and here for previous posts on the subject).

To start with, here's some code and thoughts for problems 1 and 2.

Add all the natural numbers below 1000 that are multiples of 3 or 5.

This is generally regarded as the easiest Euler problem, so shouldn't present too many problems. Mainstream software development is still dominated by imperative languages and styles, so the most recognisable solution to this would be a straightforward for-loop. Here is an imperative C# solution:

```
int result = 0;
for (int i = 0; i < 1000; ++i)
{
if (i % 3 == 0 || i % 5 == 0)
result += i;
}
```

Simple enough, but as with all for-loops the guts are a little too visible. I have to explicitly declare and increment an accumulator variable as well as the loop counter. A functional style (Haskell in this case) allows a more declarative solution:

```
sum $ filter (\n -> n `mod` 3 == 0 || n `mod` 5 == 0) $ [1..999]
```

Or, with list comprehensions:

```
sum [n | n <- [1..999], n `mod` 3 == 0 || n `mod` 5 == 0]
```

In both cases, the loop is replaced by a list generated from Haskell's range operator. [1..999] creates a list containing every integer between 1 and 999 inclusive. The modulo test is basically the same, though Haskell lacks a modulo operator (% in most C-family languages) so the mod function is used instead.

Just for fun, here's an F# solution too:

```
let sum = List.fold_left (+) 0let mod35 = fun x -> x % 3 = 0 || x % 5 = 0List.filter mod35 [1..999] |> sum
```

This could be compressed into a one-liner like the Haskell solutions, but it would be a bit long for my taste. Also note F# is slightly hamstrung by the lack of a built-in sum function, so I have to define my own using fold. Another F# solution is here, but I prefer mine. There's a very nice snippet in the comments of that page, though, which I like even more:

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

Interestingly, C# is gaining some fairly powerful functional techniques lately, in particular LINQ. I can use the new Enumerable class to mimic range syntax and filter functionality from other languages, and lambdas to keep the code concise.

```
Enumerable.Range(1, 999).Where(f => f % 3 == 0 || f % 5 == 0).Sum();
```

Note the similarity between F#/Haskell's lambda syntax and that of C#. It's very cool that a mainstream C-derivative language is getting this sort of syntax added to it.

Alternatively, I could use LINQ query expressions for a different approach:

```
var nums = from n in Enumerable.Range(1, 999)
where n % 3 == 0 || n % 5 == 0
select n;
nums.Sum();
```

Fun!

It should be noted that all the Project Euler problems I've seen so far have mathematical solutions, meaning if you are able to classify the problem correctly it is straightforward to work out the answer with pen and paper. In this case, the problem is based around an arithmetic progression, and there are powerful formulae for reasoning about those. If you're interested, check out the forum for problem 1.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Ooh, Fibonacci. I've been here before. Using the Haskell code from that post makes problem 2 a snip:

```
fib = 0 : 1 : zipWith (+) fib (tail fib)
sum $ filter even $ takeWhile (<4000000) fib
```

Given the lazy Fibonacci generator in the first line, this just uses standard Haskell functions from the Prelude to do all the work - reading right to left, takeWhile pulls data from the fib sequence until the test fails (i.e. we've reached 4,000,000), filter even does exactly what it says on the tin, and sum does the business on the result.

C# could solve problem 1 very neatly - can it keep up the pace in problem 2? Actually, yes it can, after a fashion. The lazy Fibonacci generator can be implemented using the yield statement added in C# 2.0. This is much more efficient than the naive recursive solution I looked at in my previous post about Fibonacci sequences. Once I have the generator, the LINQ statement is very concise and quite similar to the Haskell code - C# 3.0 even has TakeWhile!

```
IEnumerable<long> Fibs()
{
long a = 0, b = 1;
while (true)
{
yield return b;
b = a + b;
a = b - a;
}
}
Fibs().TakeWhile(f => f < 4000000).Where(f => f % 2 == 0).Sum();
```

The more I use C# 3.0, the more I like it - there's quite a bit of power in there.

As with problem 1, there are some fascinating mathematical tricks that can be utilised when solving problem 2, and I recommend you check out the forum. It's particularly cool to see how the Golden Ratio can be brought into play when working with Fibonacci sequences - I had no idea these techniques existed. So much to learn!

I quote "C# could solve problem 1 very neatly - can it keep up the pace in problem 2? Actually, yes it can, after a fashion."

While efficient writing is one thing, what happens when the code hits the silicon? Do they compile efficiently? Does the processor run faster with one snippet over another?

Many get spoiled by GHz machines with GB of RAM, but those of us in the embedded market still worry about code size and execution speed...

J

J: The DotNet Framework's compiler works extremely well. I would expect that the newer structures are supported with optimizations that one could otherwise only achieve writing IL by hand.

Actually, someone throw Ackermann at it and see what it does...

Problem 1 seems to be quite efficiently solved in the standard UNIX bc program. O(1) (ignoring the fact that bc uses arbitrary precision numbers).

s(n) is the sum of the integers 1 to n, inclusive. t(n,m) is the sum of all the integers that are multiples of m between 1 and n, inclusive. The problem answer is the (sum of multiples of three) + (sum of multiples of five) - (sum of multiples of 15 since they would have been counted twice).

Your C# program would choke if you changed 1000 to a googol. The BC program says:

I haven't checked if that is correct. but it has about the right number of digits.

[...] not) brings me to Project Euler and the title of this post. I had heard of Project Euler before, butthis post enticed me to visit the site. One look and I was [...]

I finished the saga of Project Euler problem one, and found that the functional approach led me to the fastest solution in an unexpected way ( http://joelneely.wordpress.com/2008/04/09/the-burden-of-fp-part-3/ ). Thanks for the encouragement, and for keeping your series going.

-jn-: Functional programming didn't lead you to the fastest solution since you didn't get to the fastest solution. Yours has a loop (recursion). My bc solution (above) has none. It also happens to be side-effect free and hence functional.

My version takes a little bit of mathematical reasoning to come up with, or a memory of the tale of Gauss summing the integers 1 to 50 too quickly for his teacher http://www.americanscientist.org/template/AssetDetail/assetid/50686?&print;=yes

ProjectEuler Problem 1...I have been learning Haskell, since couple of weeks. I am following the online book, Real World Haskell. For fun and learning, I decided to solve some problems from ProjectEuler. My solution for the first problem went through 3 stages, as I learnt more...

[...] was going to solve the problem in VB the standard brute force iteration way until I came across the following blog entry. Again, I take no credit for the following code. It has been scoffed from another [...]

My solution for Problem 1 using Python (2.6.1):

The first problem can be calculated a lot quicker:

Hi,

Today i was introduced to the Euler project. Since im learning ruby now, decided to use this to practice ruby...it is concise.

ssmm987,

You miss-understood the problem. It is not the sum of multiples of 15. It's the sum of multiples of 3 or 5. You need to sum:

Brilliant work. I will recommend your site

I like it in python:

or with a generator instead