Problem 1

Okay, so to start of I'd thought I'd go from the beginning and try my luck with problem 1:


What is the sum of all the multiples of 3 or 5 below 1000.


This one seems pretty easy and coming up with a solution didn't take me too long at all, my first attempt was simply to do this:

sum = 0
for every number between 1 and 1000
    if the number is a multiple of 5 or 3
        sum += number


This definitely works as the answer it spews out was enough for me to get my first tick on the Project Euler site. Exciting. I went to bed happy.


I began to think over the next day that the point of the challenge was not to simply solve the problem but to really think about it and come up with the 'best' solution. I became convinced on my train ride home that what I had didn't cut the mustard and I had a plan to help me improve. I would time the execution of my solution and then try to best my time.


One small problem was that the solution takes 0.0 milliseconds when timed with System.currentTimeMillis() (I'm a Java guy). Rather than play around with using smaller and smaller units I decided to up the range of the problem until the 'old' solution took a decent chunk of time. So I rephrased the question to be:


What is the sum of all the multiples of 3 or 5 below Integer.MAX_VALUE (2 147 483 647)


Solving this took ~9.5 seconds and gave the answer -787410670 (*giggle*, integer overflow). Now I just had to improve the solution.


The most striking problem is that I run a maximum of 3 comparisons for every integer (one for the for loop and two for the multiplicity checks) and that the comparisons aren't trivial (modulo arithmetic FTW). This problem has a decent solution in that I can generate the required numbers rather than check every number to see if it matches:


fivemultiple = 5
threemultiple = 3
sum = 0
while fivemultiple < MAX
    sum += fivemultiple
    fivemultiple += 5
while threemultiple < MAX
    repeat 4 times
        sum += threemultiple
        threemultiple += 3
    threemultiple += 3


The repeat 4 times hassle at the end is to counter the fact that I now generate numbers that are multiples of both 3 and 5 twice.


Solution two solves the new problem in a modest ~0.95 seconds, a tenth of the original.


I had a facepalm moment when I realised that I could shave off more time by generating the three multiples first then the fives (now I only repeat the fiddly bit twice).


Solution three solves the new problem in ~0.39 seconds that's less than one twentieth of the original solution's time.


I'm going to read the forums soon to see how I could improve on this. For the second evening in a row though, I'm going to bed happy.