Project Euler #1: Multiples of 3 and 5

Problem

Find the sum of all multiples of 3 or 5 below 1000.

The Brute Force (and Why We Don’t Stop There)

A simple loop works, of course:

print(sum(x for x in range(1000) if x % 3 == 0 or x % 5 == 0))

But the point of Project Euler isn’t the answer — it’s finding the clean mathematical structure underneath.

The Inclusion-Exclusion Approach

Let $S(k, n)$ denote the sum of all multiples of $k$ strictly below $n$. Then:

$$S(k, n) = k \cdot \sum_{i=1}^{\lfloor (n-1)/k \rfloor} i = k \cdot \frac{m(m+1)}{2}$$

where $m = \lfloor (n-1)/k \rfloor$.

By inclusion-exclusion, the sum of multiples of 3 or 5 is:

$$S(3, 1000) + S(5, 1000) - S(15, 1000)$$

We subtract $S(15, 1000)$ because multiples of 15 are counted twice.

Computing It

$$S(3, 1000) = 3 \cdot \frac{333 \cdot 334}{2} = 166833$$$$S(5, 1000) = 5 \cdot \frac{199 \cdot 200}{2} = 99500$$$$S(15, 1000) = 15 \cdot \frac{66 \cdot 67}{2} = 33165$$$$\text{Answer} = 166833 + 99500 - 33165 = \boxed{233168}$$

A Clean Python Implementation

def sum_multiples(k: int, n: int) -> int:
    """Sum of multiples of k strictly below n."""
    m = (n - 1) // k
    return k * m * (m + 1) // 2

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

This runs in $O(1)$ time regardless of $n$, compared to $O(n)$ for the naive loop.