10. Sums of multiples

One obvious approach for finding multiples of three and five is to loop through the numbers between 3 and the maximum value, check each number to see if it is a multiple of 3 or 5, and add the multiples to get a running total. The following method takes this approach into account:

private long Method1(long max)
{
    long total = 0;
    checked
    {
        for (long i = 3; i <= max; i++)
            if ((i % 3 == 0) || (i % 5 == 0))
                total += i;
    }
    return total;
}

This is straightforward but not very efficient. If the max parameter is large, this method can take a while.

A better approach is to use a variable to keep track of the next multiple of five and then loop through the multiples of 3. If a multiple of 3 is greater than the next multiple of 5, add that multiple to the total and move it to the next multiple of 5. The following method uses this approach:

private long Method2(long max)
{
    long total = 0;
    checked
    {
        int next5 = 5;
        for (long i = 3; i <= max; i += 3)
        {
            total += i;
            if (i == next5)
            {
                next5 += 5;
            }
            else if (i > next5)
            {
                total += next5;
                next5 += 5;
            }
        }

        // Check the final few entries.
        for (long i = max; i > max - 3; i--)
        {
            if (i % 3 == 0) break;
            if (i % 5 == 0)
            {
                total += i;
                break;
            }
        }
    }
    return total;
}

This method is much faster than the first version for two reasons. First, it only considers values that are multiples of three or five. Second, it uses addition to increase the i and next5 values, so it always knows that those values are multiples of three or five, respectively. That means that it doesn't need to use the relatively slow modulus operator % to see if a value is a multiple.

This method is effective, but it's rather complicated. That means it will be harder to understand, debug, and maintain. You can make a simpler version if you think a bit more about the problem.

You could use two loops—one to add up multiples of three and a second one to add up multiples of 5. If you did that, however, multiples of both 3 and 5 such as 15 and 30 would be counted twice. You could then fix the total by using another loop to subtract those duplicated multiples of 15 so they are counted only once.

One of the lessons from Solution 9. Least common multiples, was that the evaluation order can sometimes cause integer overflow and that same lesson applies here. It is possible that adding up the multiples of 3 and then the multiples of 5 could cause an integer overflow. We can avoid that if we subtract the multiples of 15 after adding the multiples of three and before adding the multiples of five, as shown in the following code:

private long Method3(long max)
{
    checked
    {
        long total = 0;
        for (long i = 3; i <= max; i += 3) total += i;
        for (long i = 15; i <= max; i += 15) total -= i;
        for (long i = 5; i <= max; i += 5) total += i;
        return total;
    }
}

This version is about as fast as the preceding version and won't cause integer overflow unless the final total is too big to fit in a long integer, in which case we're stuck anyway. However, we can do even better!

Once again, we need to think about the problem in a new way. The preceding solution adds up the numbers 3 + 6 + 9 + ... That sum equals 3 times the slightly simpler sum 1 + 2 + 3 + ... You can use the following equation to calculate the simpler sum without adding up the numbers individually:

Now, you can use that formula to directly calculate the sums of the multiples of 3, 5, and 15 instead of using loops. The following code demonstrates this method:

private long Method4(long max)
{
    checked
    {
        long num3s = max / 3;
        long threes = num3s * (num3s + 1) / 2 * 3;
        long num5s = max / 5;
        long fives = num5s * (num5s + 1) / 2 * 5;
        long num15s = max / 15;
        long fifteens = num15s * (num15s + 1) / 2 * 15;
        return threes - fifteens + fives;
    }
}

This code first calculates max / 3 to get the largest multiple of three less than or equal to max. For example, if max is 25, then max / 3 = 8. (Keep in mind that this is integer division, so the fractional part is discarded.) The code uses the formula to calculate 1 + 2 + ... + 8 and multiplies the result by 3 to get the total 3 + 6 + ... + 24.

The method repeats those steps to calculate the sums of the multiples of 5 and 15 and combines them to get the final result.

This version of the method performs only a few calculations instead of using long loops, so it is much faster than any of the previous solutions.

The following screenshot shows the example solution adding multiples between 0 and 100 million: 

The first solution took around 2 seconds. The second and third approaches took around 0.38 and 0.25 seconds, respectively. Those times are reasonably comparable. The final solution took so little time that it is virtually instantaneous. Unlike the other solutions, the final approach does not depend on the maximum value, so it takes no longer to add up a few values or millions of values.

One lesson to be learned here is that you should (as usual) use the checked keyword to look for integer overflow. You should also look at a problem from multiple directions to see if you can restate the problem in a simpler form. In this case, we converted a long, slow loop into a series of faster loops, and then we converted those loops into some simple calculations.

Download the SumsOfMultiples example solution to see additional details.