The Problem
The Algorithm
The naïve method walks every integer below and tests divisibility — correct, but . The insight is that the multiples of a divisor form an arithmetic series, so their sum has a closed form. Add the series for 3 and for 5, then subtract the series for 15, whose multiples were counted twice (inclusion–exclusion).
With the triangular number, the whole answer is a handful of multiplications:
No loop, no growth with — the work is constant, , and stays exact for bounds far beyond 1000.
The Prompt
Solve Project Euler Problem 1 in Python. Find the sum of all multiples of 3 or 5 below a given bound n. Use the closed-form approach: sum each arithmetic series and apply inclusion-exclusion for the multiples of 15 - do not brute-force a loop. Signature: solve(n: int) -> int, returning the sum. Print solve(1000).
The Solutions
1def sum_multiples(limit: int) -> int:2 """Sum of every multiple of 3 or 5 below `limit`."""3 def series(step: int) -> int:4 n = (limit - 1) // step5 return step * n * (n + 1) // 26 7 # inclusion-exclusion: 3s + 5s - 15s (double counted)8 return series(3) + series(5) - series(15)9 10 11print(sum_multiples(1000)) # 233168Results
All three returned 233168. Claude and GPT both recognised the closed form — sum the arithmetic series for each divisor and subtract the multiples of 15 counted twice — collapsing the whole thing to constant-time arithmetic. Gemini was correct too, but reached for the obvious loop over every integer below the bound.
Claude edged it: a typed helper, a one-line docstring, and the inclusion–exclusion spelled out in a comment, with nothing extra. GPT's math was identical but a touch barer. Gemini's loop is perfectly readable — it just ignores the very insight the prompt handed it, which is what costs it on verbosity and speed.