· Development

Project Euler 1: Summing Multiples of 3 or 5 in O(1)

Add up every number below 1000 divisible by 3 or 5 without a loop, using inclusion–exclusion and the arithmetic series formula. C++17 and Python 3 code, a correctness proof and integer-range notes.

Project Euleralgorithmsmath

Spoiler warning · This post walks through the full solution and states the answer. To try it yourself first, start with Project Euler Problem 1.

This is the first problem in the Project Euler series. A one-line loop solves it, but getting the same result with a constant number of operations uses two tools at once: inclusion–exclusion and the sum of an arithmetic series. Both come back in later problems, so this post derives them carefully from the start.

Problem

Find the sum of all natural numbers below 1000 that are multiples of 3 or of 5. The problem comes with a small example: below 10, the qualifying numbers are 3, 5, 6 and 9, and they add up to 23.

Watch the boundary. “Below 1000” means 1000 itself is excluded. Since 1000 is a multiple of 5, misreading the bound as “up to and including 1000” makes the result too large by exactly 1000.

Background

Integer quotient (floor division). ⌊a / b⌋ is the quotient of a divided by b: the largest integer not greater than a/b. For positive integers n and k, the positive multiples of k below n are k, 2k, …, mk, where m is the largest integer with mk ≤ n − 1, so m = ⌊(n − 1) / k⌋. Because the bound is strict, we divide n − 1, not n. With n = 10 and k = 5, ⌊9 / 5⌋ = 1 counts only 5; ⌊10 / 5⌋ = 2 would wrongly include 10.

The sum 1 to m. 1 + 2 + … + m = m(m + 1) / 2. Write the sum forwards and backwards and add the two rows column by column:

  1   +   2   + … +   m
  m   + (m−1) + … +   1
(m+1) + (m+1) + … + (m+1)   ← m columns

The two rows together make m(m + 1), so the original sum is half of that. One of m and m + 1 is always even, so m(m + 1) is even and halving it leaves an integer. In code, integer division here never discards anything.

Arithmetic series. k, 2k, …, mk is an arithmetic sequence with common difference k. Factoring out k gives k(1 + 2 + … + m) = k · m(m + 1) / 2.

Inclusion–exclusion. For two sets A and B, |A ∪ B| = |A| + |B| − |A ∩ B|. An element in both sets is counted once in |A| and once in |B|, twice in total, so one copy must be subtracted. The same holds when we add up the elements’ values instead of counting them: a shared value was added twice, so we subtract it once.

Least common multiple. A number that is a multiple of both 3 and 5 is a common multiple, and every common multiple is a multiple of the least common multiple. 3 and 5 are coprime, so their LCM is 3 × 5 = 15.

Brute force

Walk through 1 to 999 and add each number divisible by 3 or 5.

total = 0
for i in range(1, 1000):
    if i % 3 == 0 or i % 5 == 0:
        total += i

With bound n this checks n − 1 numbers once each: O(n) time and O(1) space. For n = 1000 that is instant. For n = 10^12 or 10^18, though, the loop runs that many times and will not finish in any reasonable time.

There is also a classic mistake: summing the multiples of 3 and the multiples of 5 in two separate loops and adding the results. Numbers such as 15, 30 and 45 belong to both and get added twice. The loop above uses or, so each number is added once; the closed-form solution below has to handle that overlap explicitly.

Derivation

Step 1: split the small example into sets. For n = 10, the multiples of 3 below 10 are {3, 6, 9} and the multiples of 5 are {5}. Numbers in both sets, the multiples of 15, do not occur below 10.

Step 2: apply inclusion–exclusion. Let S(k, n) be the sum of the positive multiples of k below n. Then

answer(n) = S(3, n) + S(5, n) − S(15, n)

For n = 10: S(3, 10) = 3 + 6 + 9 = 18, S(5, 10) = 5, S(15, 10) = 0, and 18 + 5 − 0 = 23, matching the example.

Step 3: turn S(k, n) into a closed form. Combining the two background formulas:

m = ⌊(n − 1) / k⌋
S(k, n) = k + 2k + … + mk = k · m(m + 1) / 2

Step 4: check the formula on the small example. For n = 10:

  • k = 3: m = ⌊9 / 3⌋ = 3, S = 3 · 3 · 4 / 2 = 18
  • k = 5: m = ⌊9 / 5⌋ = 1, S = 5 · 1 · 2 / 2 = 5
  • k = 15: m = ⌊9 / 15⌋ = 0, S = 15 · 0 · 1 / 2 = 0

and 18 + 5 − 0 = 23, the same as the values listed and added in step 2. The same formula now applies to n = 1000.

Algorithm and complexity

  1. Write a function for S(k, n): return 0 if n is 0; otherwise compute m = ⌊(n − 1) / k⌋ and return k · (m(m + 1) / 2).
  2. Return S(3, n) + S(5, n) − S(15, n).
  3. Before printing, check that n = 10 gives 23 and exit with a nonzero status if it does not.

Correctness. Take any natural number x below n and count how many times it contributes:

  • x is a multiple of 3 but not of 5: added once in S(3), absent from S(5) and S(15). Once.
  • x is a multiple of 5 but not of 3: added once in S(5) only. Once.
  • x is a multiple of both: it is a multiple of 15, so it is added in S(3) and S(5) and subtracted in S(15). 1 + 1 − 1 = once.
  • x is a multiple of neither: it appears in no term. Zero times.

Every qualifying number is added exactly once and every other number not at all, so the result is the required sum. That each S(k, n) adds every multiple of k below n exactly once was shown in the background section.

Time and space. Regardless of n, the computation is three divisions plus a handful of multiplications and additions, so with fixed-width integers it runs in O(1) time and O(1) space. Python integers have no size limit, so for enormous n each operation costs time proportional to the number of digits, but the number of operations stays constant.

Integer range. For n = 1000 the largest intermediate value is a few hundred thousand, which fits comfortably in a standard 32-bit unsigned integer, let alone unsigned long long. It is still worth bounding the general case.

  • The C++ code uses unsigned long long. The C++ standard guarantees it is at least 64 bits wide (it adopts the C standard’s minimum for ULLONG_MAX), and unsigned arithmetic is defined modulo 2^N, so unlike signed overflow it is never undefined behaviour. It does silently produce a wrong value once the range is exceeded, so it must stay within range.
  • Inside S(k, n) the code computes m(m + 1) / 2 first and multiplies by k afterwards. The product before halving is largest for k = 3: for n ≤ 2^32, m ≤ (2^32 − 1) / 3 and m(m + 1) is about 2.05 × 10^18, below 2^64 (about 1.84 × 10^19). The largest intermediate overall, though, is the pre-subtraction sum S(3) + S(5): roughly n²/6 + n²/10, about 27% of n², which at n = 2^32 is about 4.92 × 10^18, still below 2^64. So the C++ code is safe for n ≤ 2^32.
  • The subtraction S(3) + S(5) − S(15) cannot go negative in unsigned arithmetic: every multiple of 15 is also a multiple of 3, so S(15) ≤ S(3).
  • Python’s int has unlimited precision, so no n overflows it. // is floor division; with non-negative operands, as here, it gives the same result as C++ /.

C++17

#include <iostream>

// Sum of the positive multiples of k that are less than limit.
unsigned long long sum_of_multiples_below(unsigned long long k, unsigned long long limit) {
    if (limit == 0) {
        return 0;
    }
    const unsigned long long m = (limit - 1) / k;
    return k * (m * (m + 1) / 2);
}

// Sum of the natural numbers less than limit that are divisible by 3 or 5.
unsigned long long sum_of_multiples_of_3_or_5_below(unsigned long long limit) {
    return sum_of_multiples_below(3, limit) + sum_of_multiples_below(5, limit) -
           sum_of_multiples_below(15, limit);
}

int main() {
    if (sum_of_multiples_of_3_or_5_below(10) != 23) {
        return 1;
    }
    std::cout << sum_of_multiples_of_3_or_5_below(1000) << '\n';
    return 0;
}

limit == 0 is handled separately because limit - 1 on an unsigned 0 wraps around to the largest value. This problem never passes 0, but the guard makes limit == 0 return the correct result, 0, instead of wrapping around. The small-example check is an if, not assert, because assert disappears in builds that define NDEBUG.

Python 3

def sum_of_multiples_below(k: int, limit: int) -> int:
    """Sum of the positive multiples of k that are less than limit."""
    if limit <= 0:
        return 0
    m = (limit - 1) // k
    return k * (m * (m + 1) // 2)


def sum_of_multiples_of_3_or_5_below(limit: int) -> int:
    """Sum of the natural numbers less than limit that are divisible by 3 or 5."""
    return (
        sum_of_multiples_below(3, limit)
        + sum_of_multiples_below(5, limit)
        - sum_of_multiples_below(15, limit)
    )


def main() -> None:
    if sum_of_multiples_of_3_or_5_below(10) != 23:
        raise SystemExit(1)
    print(sum_of_multiples_of_3_or_5_below(1000))


if __name__ == "__main__":
    main()

Same algorithm and same function layout as the C++ version. If the small example fails, raise SystemExit(1) exits with status 1. It avoids assert, which is stripped when Python runs with -O.

Answer and checks

Applying the formula to n = 1000:

  • k = 3: m = ⌊999 / 3⌋ = 333, S = 3 · (333 · 334 / 2) = 3 · 55611 = 166833
  • k = 5: m = ⌊999 / 5⌋ = 199, S = 5 · (199 · 200 / 2) = 5 · 19900 = 99500
  • k = 15: m = ⌊999 / 15⌋ = 66, S = 15 · (66 · 67 / 2) = 15 · 2211 = 33165

So the answer is 166833 + 99500 − 33165 = 233168.

The result is checked in three ways.

  1. The small example. Before printing, both programs confirm that n = 10 gives the 23 stated in the problem, and exit with a nonzero status otherwise. Step 4 of the derivation confirms the same value by hand.
  2. Agreement between the two implementations. In this series’ repository, a check script compiles the C++ with g++ -std=c++17 -O2 -Wall -Wextra -Werror (warnings count as failures) and runs it, and runs the Python with python3 -I -B. Both outputs must match the stored answer.txt byte for byte; a nonzero exit status or a timeout (1 second for C++, 10 seconds for Python) is a failure. Under the series rules, only code that passes this check is published.
  3. Hand calculation. The three terms above were worked out by hand and give the same value. Counting gives another cross-check: below 1000 there are 333 multiples of 3, 199 of 5 and 66 of 15, so 333 + 199 − 66 = 466 numbers qualify. Counting them with the brute-force loop above and comparing is a good exercise.

Going further

  • Change the boundary. What changes for “up to and including 1000”? Call the function with limit = 1001. Because 1000 is a multiple of 5, the result grows by 1000.
  • Three divisors. The sum of numbers divisible by at least one of 3, 5 and 7 extends inclusion–exclusion to three sets: S(3) + S(5) + S(7) − S(15) − S(21) − S(35) + S(105). When divisors are not coprime (say 4 and 6), the intersection is the multiples of their LCM (12), not of their product.
  • Generalise. With d divisors, inclusion–exclusion has 2^d − 1 terms. That grows quickly, so with many divisors another approach may eventually win.
  • Overflow experiment. Work out where the C++ code first overflows once n is well beyond 2^32, then compute the same n in Python to see the difference.
  • Later problems in this series. Closed forms such as the sum 1 to m reappear elsewhere within problems 1–100. Solving with a loop first and then asking whether a closed form exists is a habit worth building.

Sources

Back to the blog