Problem Analysis
The task is to sum every natural number below a limit N that is a multiple of 3 or of 5.
The naive reading — "test each number" — hides the structure that makes the problem tractable. The
multiples of 3 below N form an
arithmetic progression
(3, 6, 9, …), as do the multiples of 5. Their union is not a disjoint set: a multiple of 15 is a
multiple of both, so summing the two progressions independently double-counts those terms. Correcting
for the overlap is the
inclusion–exclusion principle:
S = S(3) + S(5) − S(15), subtracting the multiples of 15 once to undo the double count.
Each of those three sums is itself an
arithmetic progression
that admits a
closed-form expression:
the sum of the first n multiples of d below N is
d · n(n+1)/2, where n = ⌊(N−1)/d⌋. The factor n(n+1)/2 is the
n-th
triangular number,
the same identity Gauss is said to have found as a schoolboy. This collapses the whole computation to a
handful of multiplications: O(1) in
time complexity.
The alternative — iterating over candidate terms — is O(N), which only matters once
N is large (here the largest case uses N = 10⁹). For that case the answer,
233 333 333 166 666 668, exceeds a 32-bit range but fits comfortably in a signed 64-bit integer
(max ≈ 9.2 × 10¹⁸), a detail that shapes the C translations.
Solution Approach
I wrote five solutions that share one answer but span the spectrum from an O(1) formula to
an O(N) scan, each in both Python and C. Comparing them is the whole point: it shows how the
same mathematics, expressed differently, costs wildly different amounts of time.
Index 0 — Closed-form inclusion–exclusion (O(1))
The fastest approach applies the
closed-form expression
directly. A helper sum_arithmetic_series(d, N) computes d · n(n+1)/2 with
n = ⌊(N−1)/d⌋, and solve combines the three calls by
inclusion–exclusion:
sum(3) + sum(5) − sum(15). No loop touches the input size, so the runtime is constant
regardless of N — measured at 9.3 × 10⁻⁶ s in C and 6.9 × 10⁻⁶ s in Python on the
N = 10⁹ case, the two within measurement noise of each other since at this scale the timing
is dominated by fixed process overhead rather than the handful of arithmetic operations. The C version
mirrors the Python line for line, casting one operand of the
n(n+1) product to long long so the intermediate never overflows 32 bits.
Index 1 — Brute-force scan (O(N))
The most direct reading of the problem: walk every integer from 0 up to N and add it when
it is divisible by 3 or 5 (term % 3 == 0 or term % 5 == 0). This is the reference against
which the smarter solutions are judged — correct by construction, but linear in N. At
N = 10⁹ it is the slowest of all: 40.6 s in Python and 0.85 s in C. The roughly 50× gap between the
two languages here is the cost of CPython's per-iteration interpreter overhead on a tight loop, which
the compiled C avoids entirely.
Index 2 — Summing range slices (O(N))
Rather than scan every integer, this approach iterates only the terms that matter: it sums each
arithmetic progression
separately via sum(range(0, N, d)) for d ∈ {3, 5, 15} and combines them by
inclusion–exclusion.
It is still O(N) — sum over a range object visits every element —
but it touches roughly a third as many numbers as the brute-force scan and skips the divisibility test,
making it the fastest of the linear Python variants at 4.8 s. The C translation is a faithful port:
sum_range(start, stop, step) accumulates by iteration (a for loop), deliberately
not the closed-form formula, since that constant-time shortcut is index 0's distinct approach.
Keeping the C iterative is what makes its 0.18 s timing honestly reflect the same O(N) work
its Python sibling does.
Index 3 — Generator over range (O(N))
The same linear idea expressed as a
generator
function: generate_arithmetic_series_range yields each term of range(0, N, d),
and solve sums three such streams with
inclusion–exclusion.
Functionally identical to index 2, but routing each value through a Python-level
generator
frame costs far more per element than letting sum consume a native range: 12.8 s
versus index 2's 4.8 s in Python. The C port collapses the
generator
to a plain accumulating for loop (C has no equivalent abstraction here), landing at 0.17 s —
indistinguishable from index 2's C, as it should be.
Index 4 — Generator with explicit while (O(N))
A variant of index 3 that drives the
generator
with a hand-written while loop (term += d) instead of delegating to
range. This exposes the cost of doing arithmetic in Python on every step: at 16.5 s it is the
slowest of the linear Python variants, because each iteration now performs an explicit add and comparison
in the interpreter rather than inside range's optimised C internals. The C port is again a
straight while-loop accumulator at 0.18 s, on par with indices 2 and 3.