Tag Archives: intelligent solution

Multiples of 3 or 5 below 1000 [Project Euler Problem 1]

This is the first Project Euler 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.

Pretty simple, right? The dumb brute-force method would be:

public class M35 {
    public static void main(String[] args) {
        long time = System.nanoTime();

        int val = 0;
        for (int i = 0; i < 1000; i++){
            if(i%3==0 || i%5 == 0){val+=i;}
        }
        time = System.nanoTime() - time;

        System.out.println(time/1.0e9);
    }
}

It returns:

233168
2.6782E-5

Less than 0.0002 seconds? Neat, right? But what about an intelligent solution?
Try and recall how Gauss stumped his teacher in primary school when asked to sum the range 1 to 100 mentally. He understood that the range 1 to 100 consists of:
(1+100) + (2+99) + (3+98) … + (50+51) = 50 x 101 = 5050.

Now, in our case, we need the sum of all multiples of either three or five – but what about 15? 30? They’ll get counted twice, right?

In our case, what we need to do is,

(sum of multiples of 3) + (sum of multiples of 5) – (sum of multiples of 15)

=> (3 + 6 + 9 + … +999) + (5 + 10 + 15 + … + 995) – (15 + 30 + 45 + … + 990)

=> 3 x (1 + 2 + 3 + … + 333) + 5 x (1 + 2 + 3 + … + 199 ) – 15 x (1 + 2 + 3 + … + 66)

I’ll leave you to find out how these series can be summed.

After all, Project Euler tells us not to give out spoilers :D

PS. Hint, hint, arithmetic progression sums.

Advertisements