Project Euler – Problem 1

A while back one of my coworkers sent out a link to Scott Hanselman’s ‘Am I really a developer or just a good googler?’. As you can probably imagine from reading the title, the article proposes an interesting philosophical question that I’m sure a good many of us have considered. Am I actually a (good) developer, or am I just unnaturally talented at using Google, Stack Exchange and reading other people’s blogs.

In the article, there are a few thoughts proposed to help you have confidence in yourself and I recommend reading the it. It’s really short. I also recommend reading his article I’m a phony. Are you?. They’re both rather interesting.

With that said, one of the suggestions in the first article is to work through some problems on Project Euler. For a description of what Project Euler is, I think nothing does better than their home page:

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.

At the time when I started working through some of their problems, I was working exclusively in Objective-C, and I wanted to prove to myself that I know Objective-C, and not just iOS app development. I think it would also be interesting to write some of the solutions in a non-C based language like Ruby, but for right now I’ll stick with the answers I’ve already derived.

Problem 1 is particularly easy, and straight forward:

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.

In order to do this we only need to know a few basic things. Given basic math skills we already know that 6 is a multiple of 3 because there exists some value x for which x*3 = 6. Or, 6/x = 3, or once again as 6/3 = x' where x' is a whole number (an integer with no floating point)

As with all problems, there is more than one possible solution to this problem.

One possible solution is to take advantage of the modulo operation. For an in depth look at the modulo operation, see wikipedia. But in brief, if you don’t know the modulo operation is basically devision where you throw out the whole number, and keep only the remainder. For example 5 mod 2 = 1 because 5 / 2 = 2 remainder 1 likewise 9 mod 3 = 3 remainder 0

So all we have to do is loop through all values x where x < 1000, and check the divisibility with the modulo operation.

That’s all there is to this solution. There is also another solutions that I find interesting. If you notice, the solution proposed above works entirely, but it does so by looking at every possible number 0 < i < 1000 to check if it is evenly divisible by 3 or 5. This is going to waste a lot of time looking at numbers like 2, 4, 7, 8, 9 etc. What if instead of taking a number and checking it’s divisibility, we instead get all of the multiples of 3 and 5 and add them together.

To simplify things, we need to look at a simple pattern. All we’re doing here is counting by 3’s

You’ll notice that every 5th value is divisible by 5. This is important because when we’ll want to skip these to ensure there’s no double counting going on.

In this solution, rather than looking at all numbers and determining if it’s a multiple of 3 or 5, we simply gather numbers that we already know are multiples of 3 or 5 and add them together. Both answers seem rather straight forward, with the latter being slightly more efficient (doesn’t really matter for such a small set of numbers, but think big)