by

Project Euler, problem 1

Project Euler Problem 1.

I heard about Project Euler a little while ago, but didn’t really have a good reason to wade through the problems (personal betterment alone is typically not enough of a reason for me!). But I recently decided to learn a new language (Groovy) and I thought Project Euler would be a really good way of learning practically.

I will be working through the problems and blogging my solutions. Because this is an exercise in learning a language rather than improving my problem solving skills and algorithm efficiency, I will be placing much more emphasis on doing things the ‘groovy’ way than making my algorithms as fast as possible. Although, having had a little look at some of the problems, I don’t think I will be able to completely ignore efficiency or I might be waiting around for a very long time to get a solution if some of the things I have heard about the speed of groovy are to be believed.

So without further ado, I present the first problem:

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.

This problem is nice and simple, and I was able to come up with a solution in under five minutes. Using the groovy console really cut down the feedback time, and I can see that becoming much more important as I get to some of the more difficult problems. The first code is shown below,

Solution One

Now I know I said I wouldn’t be worrying too much about speed, but this problem was so simple that I couldn’t leave my algorithm at linear time, so I decided to do a tiny little bit of optimization. Rather than looping through all of the combinations, it would be much more sensible to reduce the candidate set and save a little computing time. So for the final solution I decided I would run two loops, one counting up the multiples of three but but not five, and the second counting up the remaining multiples of five.

I can’t be bothered to do all of the maths to work out the speedup, but if we look at the range [0..10], we have [3,5,6,9] as multiples of 3 or five, which is which is 0.4, I know there will be a slightly higher occurrence of the multiples as we get into larger numbers, so I can imagine we would be somewhere around Big O(n^slightlyLessThan0.5), which is a respectable speedup against linear time. Here is the slightly optimized code

Solution two

I know the majority of JVM programmers would stick with for loops instead of those whiles, but I’m not a massive fan of the for(;;) paradigm. I think it looks ugly in the code, and anyway, they compile into the same bytecode so it’s not a big issue really.

I’m not totally happy with this solution either, as I feel it’s not quite ‘groovy’ enough, it could just have easily been written in C++ without any significant changes. That is something I’m going to be working hard to change when I tackle the future problems.