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 .
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 increases. In fact, it has 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 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 are exactly where is the largest integer such that . The sum of these is . Similarly, the sum of all multiples of 5 less than is where is the largest integer such that .
As it turns out, there is a well-known formula for the sum , and it can be verified quite easily by induction.
Admittedly, I pulled the formula 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 and the sum of all multiples of 5 less than . All that's left now is to combine the two. It's tempting to just add
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 . The following theorem proves this fact.
Now we can combine these two theorems to show that the sum of all multiples of 3 and 5 is where is the largest integer such that . Now we have our answer! The sum of all multiples of 3 or 5 less than is
Plugging in , we have , and , and we have
The following code implements our solution for an arbitrary input . Note that it has time complexity !
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)