Project Euler Problem 1

Project Euler Problem 1

Solution

We need the sum of all natural numbers below $1000$ that are divisible by $3$ or $5$.

Mathematical approach

Use inclusion–exclusion:

• Sum of multiples of $3$ below $1000$
• Sum of multiples of $5$ below $1000$
• Subtract sum of multiples of $15$ (counted twice)

The sum of multiples of $k$ below $1000$ is:

$$k(1 + 2 + \cdots + n)$$

where $n = \left\lfloor \frac{999}{k} \right\rfloor$, and

$$1 + 2 + \cdots + n = \frac{n(n+1)}{2}$$

• Multiples of $3$: $n = 333$

$$3 \cdot \frac{333 \cdot 334}{2} = 166833$$

• Multiples of $5$: $n = 199$

$$5 \cdot \frac{199 \cdot 200}{2} = 99500$$

• Multiples of $15$: $n = 66$

$$15 \cdot \frac{66 \cdot 67}{2} = 33165$$

So:

$$166833 + 99500 - 33165 = 233168$$

Clean Python code

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

print(sum_of_multiples(1000))

This evaluates to:

233168

Mental trace/check:

• Small example below 10 gives $3 + 5 + 6 + 9 = 23$, matching the problem statement.
• Inclusion–exclusion avoids double-counting multiples of $15$.
• Final computed total is consistent.

Answer: 233168