Problem Archive

← Prev Next →
Problem 1

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$.

Solution

The straightforward solution is to loop through every number below 1000 and check if it’s divisible by 3 or 5.

def solve():
    return sum(n for n in range(1000) if n % 3 == 0 or n % 5 == 0)

print(solve())  # 233168

This works perfectly fine for 1000. But what if the limit were 1,000,000,000? Looping would take forever.

We can do much better by using a clever math trick—no looping at all.

Step 1: The Magic Formula for Adding Consecutive Numbers

Let’s start small. Suppose we want to add:

1 + 2 + 3 + ... + 20

Instead of adding left to right, let’s pair numbers from the ends:

1 + 20 = 21
2 + 19 = 21
3 + 18 = 21
4 + 17 = 21
5 + 16 = 21
6 + 15 = 21
7 + 14 = 21
8 + 13 = 21
9 + 12 = 21
10 + 11 = 21

We have 20 / 2 = 10 pairs.
Every pair sums to 21.

So the total is:

10 × 21 = 210

Which is the same as:

20 × 21 / 2 = 210

Now, what if n is odd? Let’s try 1 + 2 + ... + 17.

Pair them up:

1 + 17 = 18
2 + 16 = 18
3 + 15 = 18
4 + 14 = 18
5 + 13 = 18
6 + 12 = 18
7 + 11 = 18
8 + 10 = 18

That’s (17 - 1) / 2 = 8 pairs, each summing to 18.

But wait—we have one number left in the middle: 9.

So the total is:

8 × 18 + 9 = 144 + 9 = 153

Notice that 17 × 18 / 2 also equals 153!

So, whether n is even or odd, the sum of the first n natural numbers is always:

1 + 2 + 3 + ... + n = n × (n + 1) / 2

That’s our first powerful tool.

Step 2: Adding Numbers That Skip (Arithmetic Series)

Now, what if we don’t want every number, but only multiples of something?

For example, let’s add all multiples of 5 below 1000:

5, 10, 15, 20, ..., 995

Look closely—this is just:

5 × (1, 2, 3, 4, ..., 199)

Because:

5 × 1 = 5
5 × 2 = 10
5 × 3 = 15
...
5 × 199 = 995

So, instead of adding the multiples directly, we can:

  1. Figure out how many multiples there are (that’s 199 in this case).
  2. Use our formula to add 1 + 2 + ... + 199.
  3. Multiply the result by 5.

How do we find the count?

We want the largest number k such that:

5 × k < 1000

That means:

k < 1000 / 5
k < 200

So the largest whole number k is 199.

We can get this easily with integer division:

count = (1000 - 1) // 5   # 999 // 5 = 199

We use 999 because we want numbers strictly below 1000.

General rule:

For any step (like 3, 5, or 15) and any limit (like 1000):

count = (limit - 1) // step

And the sum of all multiples of step below limit is:

step × (1 + 2 + ... + count)
= step × count × (count + 1) / 2

Let’s write that as a neat Python function:

def sum_multiples(step, limit):
    count = (limit - 1) // step
    return step * count * (count + 1) // 2

Let’s test it quickly:

print(sum_multiples(5, 1000))  # 5 + 10 + ... + 995 = 99500

It works instantly, with no loop!

Step 3: Solving Our Problem (Watch Out for Double-Counting!)

We need the sum of all multiples of 3 OR 5 below 1000.

A natural first attempt is:

sum_multiples(3, 1000) + sum_multiples(5, 1000)

But there’s a catch.

Think about the number 15.
It is a multiple of 3, so it gets added in the first sum.
It is also a multiple of 5, so it gets added again in the second sum.

The same happens for 30, 45, 60, and every other multiple of 15.

We accidentally counted these numbers twice, but we should only count them once.

Step 4: Fix It with the Inclusion–Exclusion Principle

The fix is simple:

So the final formula is:

answer = sum_multiples(3, 1000) + sum_multiples(5, 1000) - sum_multiples(15, 1000)

Step 5: The Final, Super-Fast Solution

Here’s the complete code:

def sum_multiples(step, limit):
    count = (limit - 1) // step
    return step * count * (count + 1) // 2

def solve():
    return (
        sum_multiples(3, 1000)
        + sum_multiples(5, 1000)
        - sum_multiples(15, 1000)
    )

print(solve())  # 233168
Problems sourced from Project Euler · Non-commercial & educational use only · CC BY-NC-SA 4.0