The Problem

The problem is stated as follows:

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 n=1000n=1000.

My Solution

The obvious way to tackle this problem would be to simply loop through all numbers from 1 to 1000, check if the number is a multiple of 3 or 5, and, if so, add it to a running total. But what fun would that be? Plus, that solution would slow down as nn increases. In fact, it has O(n)O(n) time complexity. I think we can do better.

Instead of looping through every number, we can do a bit of math to figure out an explicit formula for the solution. And, of course, an explicit formula always has O(1)O(1) time complexity, which is a major improvement!

We ultimately want the sum of multiples of 3 or 5, but to make it simple let's just do multiples of 3 first. We can incorporate multiples of 5 later. The first thing to notice is that all multiples of 3 below nn are exactly 3,3(2),3(3),...,3(a)3, 3(2), 3(3), ..., 3(a) where aa is the largest integer such that 3a<n3a \lt n. The sum of these is 3k=1ak3\sum_{k=1}^a{k}. Similarly, the sum of all multiples of 5 less than nn is 5k=1bk5\sum_{k=1}^b{k} where bb is the largest integer such that 5b<n5b \lt n.

As it turns out, there is a well-known formula for the sum k=1ak\sum_{k=1}^a{k}, and it can be verified quite easily by induction.

Theorem k=1nk=n(n+1)2\sum_{k=1}^n{k} = \frac{n(n+1)}{2} for all n1n \geq 1.

Proof. The equation clearly holds when n=1n=1 and n=2n=2. Now suppose the equation holds when n=m2n = m \geq 2. Then

k=1m+1k=k=1mk+m+1=m(m+1)2+2(m+1)2=(m+1)(m+2)2\sum_{k=1}^{m+1}{k} = \sum_{k=1}^m{k} + m + 1 = \frac{m(m+1)}{2} + \frac{2(m + 1)}{2} = \frac{(m+1)(m+2)}{2}

Thus the equation holds for n=m+1n = m + 1, so by the principle of induction it holds for all n1n \geq 1.

Admittedly, I pulled the formula n(n+1)2\frac{n(n+1)}{2} out of thin air, and you might be wondering where that comes from. It's easy to verify that it's the correct formula, but figuring out what the formula is in the first place isn't as simple. There's a pretty neat way to figure it out using discrete calculus, and I'd like to cover that in a future post. For now, let's just go with it.

Okay, so now we have a formula to calculate the sum of all multiples of 3 less than nn and the sum of all multiples of 5 less than nn. All that's left now is to combine the two. It's tempting to just add

3a(a+1)2+5b(b+1)2\frac{3a(a+1)}{2} + \frac{5b(b+1)}{2}

but that wouldn't be correct because we're counting the common multiples of 3 and 5 twice!

3 + 6 + 9 + 12 + 15 + ...

5 + 10 + 15 + 20 + 25 + ...

We need to subtract the sum of all common multiples of 3 and 5. How do we find all the multiples of 3 and 5? Well, the first one is 15. The next one is 30. After that, 45. It seems like a multiple of 3 and 5 is also a multiple of 15=lcm(3,5)15 = \text{lcm}(3,5). The following theorem proves this fact.

Theorem Let a,b,cZa, b, c \in \Z. Then bab \mid a and cac \mid a if and only if lcm(b,c)a\text{lcm}(b, c) \mid a. In other words, an integer is a multiple bb and cc if and only if it is a multiple of lcm(b,c)\text{lcm}(b,c).

Proof. Set n=lcm(b,c)n = \text{lcm}(b, c), and suppose bab \mid a and cac \mid a. By the division algorithm, a=pn+ra = pn + r for some p,rZp,r \in \Z, where 0r<n0 \leq r < n. Thus, since bab \mid a and bnb \mid n, we have brb \mid r. By the same reasoning, we also have crc \mid r. Since rr is a common multiple of bb and cc and r<nr < n, rr must be 00. Thus a=pna = pn, that is, nan \mid a. Conversely, let k,jZk, j \in \Z such that n=kbn = kb and n=jcn = jc. Then if nan \mid a, we have, for some mZm \in \Z, a=mn=(mk)b=(mj)ca = mn = (mk)b = (mj)c, and thus cac \mid a and bab \mid a.

Now we can combine these two theorems to show that the sum of all multiples of 3 and 5 is 15k=1ck15\sum_{k=1}^c{k} where cc is the largest integer such that 15c<n15c \lt n. Now we have our answer! The sum of all multiples of 3 or 5 less than nn is

3a(a+1)2+5b(b+1)215c(c+1)2\frac{3a(a+1)}{2} + \frac{5b(b+1)}{2} - \frac{15c(c+1)}{2}

Plugging in n=1000n=1000, we have a=333a=333, b=199b=199 and c=66c=66, and we have

3(333)(333+1)2+5(199)(199+1)215(66)(66+1)2=233168\frac{3(333)(333+1)}{2} + \frac{5(199)(199+1)}{2} - \frac{15(66)(66+1)}{2} = 233168

The following code implements our solution for an arbitrary input nn. Note that it has time complexity O(1)O(1)!

import math

n_minus_1 = int(input("n=")) - 1

a = math.floor(n_minus_1/3)
b = math.floor(n_minus_1/15)
c = math.floor(n_minus_1/15)

solution = int((3*a*(a+1) + 5*b*(b+1) - 15*c*(c+1))/2)

print("Solution:", solution)
Solution: 233168