Project Euler is a site with 900+ problems that mix math and code. Problem 1 is the classic starting point — small enough to brute-force in seconds, but rich enough to teach a lesson every engineer needs: check if there's a formula before you write a loop.
The Problem
Add up every number below 1000 that is a multiple of 3 or 5.
A multiple of 3 is any number you get by multiplying 3 by a whole number (3, 6, 9, 12...). Divisibility just means the division has no remainder — in Python, number % 3 == 0 checks exactly that.
Brute Force Solution
pythondef sum_of_multiples(limit):
total = 0
for number in range(1, limit):
if number % 3 == 0 or number % 5 == 0:
total += number
return total
print(sum_of_multiples(1000))
This loops through every number, checks divisibility with %, and adds qualifying numbers to total. Simple — but it's O(n): double the limit, double the work. For 1000 that's fine. For a billion, it's a billion unnecessary checks.
The Smarter Way: Use a Formula
Multiples of 3 form an arithmetic progression: 3, 6, 9, 12... Gauss showed that the sum of the first n whole numbers is:
Sum = n(n + 1) / 2
So the sum of multiples of 3 is just 3 × [n(n+1)/2], where n is how many multiples exist below the limit.
The catch: 15 is a multiple of both 3 and 5. If you add sum(multiples of 3) + sum(multiples of 5), you count 15, 30, 45... twice. This is the inclusion-exclusion principle — fix it by subtracting the overlap:
Answer = sum(3) + sum(5) - sum(15)
Optimized Code
pythondef sum_of_multiples(x, limit):
n = (limit - 1) // x
return x * n * (n + 1) // 2
def project_euler_1(limit=1000):
return (
sum_of_multiples(3, limit)
+ sum_of_multiples(5, limit)
- sum_of_multiples(15, limit)
)
print(project_euler_1(1000))
// is integer division — it rounds down, giving whole-number counts, which is exactly what we need when counting multiples.
Why It Matters: O(n) vs O(1)
LimitBrute force opsFormula ops1,000~1,000~101,000,000~1,000,000~101,000,000,000~1,000,000,000~10
The loop's cost grows with input size (O(n)). The formula's cost stays flat (O(1)) — it never "counts," it just calculates. This same idea shows up in database indexing, crypto (modular arithmetic), vectorized ML operations, and billing systems that can't afford to iterate over every transaction.
Takeaways
Pattern recognition beats brute force once you see the structure.
Arithmetic series + inclusion-exclusion turn a loop into a formula.
Reusable functions (sum_of_multiples) keep code DRY.
Always ask: "Do I need to check every case, or can I calculate the answer?"
That question is worth more than any single algorithm — it's the mindset behind fast, scalable software.
Top comments (0)