Sum of numbers under 10,000 that are multiples of 3, 5 or 7 in Java

Question

I know how to get the program to add up the sums of the multiple for each of 3, 5 and 7, but I'm not sure how I'd get the program to only use each number once. For example, I can get the program to find out all of the numbers and add them up for 3 and then do the same for 5, but then the number 15 would be in the final number twice. I'm not sure exactly how I'd get it to only take the number once. Thanks for any help.

Answer 1

While the generate-and-test approach is simple to understand, it is also not very efficient if you want to run this on larger numbers. Instead, we can use the inclusion-exclusion principle.

The idea is to first sum up too many numbers by looking at the multiples of 3, 5 and 7 separately. Then we subtract the ones we counted twice, i.e. multiples of 3*5, 3*7 and 5*7. But now we subtracted too much and need to add back the multiples of 3*5*7 again.

We start by finding the sum of all integers 1..n which are multiples of k. First, we find out how many there are, m = n / k, rounded down thanks to integer division. Now we just need to sum up the sequence k + 2*k + 3*k + ... + m*k. We factor out the k and get k * (1 + 2 + ... + m).

This is a well-known arithmetic series, which we know sums to k * m * (m + 1)/2 (See triangle number).

private long n = 9999;
private long multiples(long k) {
    long m = n / k;
    return k * m * (m + 1) / 2:
}

Now we just use inclusion-exclusion to get the final sum:

long sum = multiples(3) + multiples(5) + multiples(7)
         - multiples(3*5) - multiples(3*7) - multiples(5*7)
         + multiples(3*5*7);

This will scale much better to larger n than just looping over all the values, but beware of overflow and change to BigIntegers if necessary.