Problem 1: Multiples of 3 and 5

Project Euler Problem 1 Solution

EulerSolve provides an optimized solution for Project Euler Problem 1, Multiples of 3 and 5, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary For an exclusive upper bound $N$, we want the sum of all positive integers $n \lt N$ such that $3 \mid n$ or $5 \mid n$. The only subtlety is overlap: numbers divisible by both 3 and 5 must be counted once, not twice. The implementations do not scan every integer below $N$. They exploit two concrete facts specific to this problem: multiples of a fixed divisor form an arithmetic progression, and the common multiples of 3 and 5 are exactly the multiples of 15. Mathematical Approach For each positive divisor $m$, define $$A_m(N)=\{x\in\mathbb{N}: x \lt N,\; m \mid x\}.$$ Then the target sum is $$\sum_{x \in A_3(N)\cup A_5(N)} x.$$ The sets that matter The two relevant sets are $A_3(N)$ and $A_5(N)$. Their intersection is not mysterious: a number belongs to both exactly when it is divisible by $\operatorname{lcm}(3,5)=15$. Hence $$A_3(N)\cap A_5(N)=A_{15}(N).$$ This is the core invariant behind the whole solution. Everything reduces to summing three structured sets: multiples of 3, multiples of 5, and the overlap at 15. Counting how many multiples survive the strict bound Fix a divisor $m$. The admissible multiples below $N$ are $$m,\,2m,\,3m,\,\dots,\,q_m m,$$ where $$q_m=\left\lfloor \frac{N-1}{m}\right\rfloor.$$ The use of $N-1$ is important because the bound is strict....

Detailed mathematical approach

Problem Summary

For an exclusive upper bound $N$, we want the sum of all positive integers $n \lt N$ such that $3 \mid n$ or $5 \mid n$. The only subtlety is overlap: numbers divisible by both 3 and 5 must be counted once, not twice.

The implementations do not scan every integer below $N$. They exploit two concrete facts specific to this problem: multiples of a fixed divisor form an arithmetic progression, and the common multiples of 3 and 5 are exactly the multiples of 15.

Mathematical Approach

For each positive divisor $m$, define

$$A_m(N)=\{x\in\mathbb{N}: x \lt N,\; m \mid x\}.$$

Then the target sum is

$$\sum_{x \in A_3(N)\cup A_5(N)} x.$$

The sets that matter

The two relevant sets are $A_3(N)$ and $A_5(N)$. Their intersection is not mysterious: a number belongs to both exactly when it is divisible by $\operatorname{lcm}(3,5)=15$. Hence

$$A_3(N)\cap A_5(N)=A_{15}(N).$$

This is the core invariant behind the whole solution. Everything reduces to summing three structured sets: multiples of 3, multiples of 5, and the overlap at 15.

Counting how many multiples survive the strict bound

Fix a divisor $m$. The admissible multiples below $N$ are

$$m,\,2m,\,3m,\,\dots,\,q_m m,$$

where

$$q_m=\left\lfloor \frac{N-1}{m}\right\rfloor.$$

The use of $N-1$ is important because the bound is strict. Equivalently, $q_m$ is the unique integer satisfying

$$q_m m \lt N \le (q_m+1)m.$$

So the implementations never need to test each candidate individually; they only need the count $q_m$.

Collapsing each arithmetic progression

Once $q_m$ is known, the corresponding sum is

$$S_m(N)=\sum_{x\in A_m(N)} x = m(1+2+\cdots+q_m).$$

Using the triangular-number identity

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

we obtain the closed form

$$S_m(N)=m\cdot \frac{q_m(q_m+1)}{2}.$$

For this problem there is no recurrence to maintain and no dynamic state to update. The arithmetic progression collapses directly into a constant-time formula.

Correcting the overlap by inclusion-exclusion

If we add $S_3(N)$ and $S_5(N)$, every multiple of 15 appears twice. Inclusion-exclusion removes exactly that extra copy:

$$\sum_{x \in A_3(N)\cup A_5(N)} x = S_3(N)+S_5(N)-S_{15}(N).$$

Substituting the closed forms gives

$$\boxed{\sum_{x \in A_3(N)\cup A_5(N)} x= 3\cdot\frac{q_3(q_3+1)}{2} +5\cdot\frac{q_5(q_5+1)}{2} -15\cdot\frac{q_{15}(q_{15}+1)}{2}},$$

with

$$q_3=\left\lfloor\frac{N-1}{3}\right\rfloor,\qquad q_5=\left\lfloor\frac{N-1}{5}\right\rfloor,\qquad q_{15}=\left\lfloor\frac{N-1}{15}\right\rfloor.$$

Worked example: $N=16$

The relevant numbers are $3,5,6,9,10,12,15$, whose direct sum is 60. The formula reaches the same result without listing them one by one:

$$q_3=\left\lfloor\frac{15}{3}\right\rfloor=5,\qquad S_3=3\cdot\frac{5\cdot6}{2}=45,$$

$$q_5=\left\lfloor\frac{15}{5}\right\rfloor=3,\qquad S_5=5\cdot\frac{3\cdot4}{2}=30,$$

$$q_{15}=\left\lfloor\frac{15}{15}\right\rfloor=1,\qquad S_{15}=15\cdot\frac{1\cdot2}{2}=15.$$

Therefore

$$45+30-15=60.$$

The subtraction of $S_{15}$ is exactly what prevents the value 15 from being counted twice.

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical pipeline. First they treat the zero limit as a degenerate case before forming the expression $N-1$; this keeps the counting step well-defined even when there are no positive integers below the bound.

Next they evaluate the count of admissible multiples for 3, 5, and 15 using integer division. For each of those three divisors, the implementation applies the closed form $m\cdot q_m(q_m+1)/2$, so the sum is computed entirely with integer arithmetic and without any loop over $1,2,\dots,N-1$.

Finally, the implementation combines the three partial sums as $S_3+S_5-S_{15}$. All three versions also verify the standard checkpoint $N=10 \mapsto 23$, and the standard Project Euler instance uses $N=1000$.

Complexity Analysis

The running time is $O(1)$: the algorithm performs a fixed number of integer divisions, multiplications, additions, and one subtraction. The memory usage is also $O(1)$.

A naive approach would inspect every integer below $N$ and test divisibility by 3 or 5, which costs $O(N)$ time. The closed form removes that dependence on the size of the bound.

Footnotes and References

Problem page: Project Euler 1
Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle
Arithmetic progression: Wikipedia - Arithmetic progression
Triangular number: Wikipedia - Triangular number
Least common multiple: Wikipedia - Least common multiple
Floor function: Wikipedia - Floor and ceiling functions

Problem 1 source code

C++

#include <cstdint>
#include <iostream>
#include <limits>
#include <string>

namespace {

using u64 = std::uint64_t;

struct Options {
    u64 limit = 1000ULL;
    bool run_checkpoints = true;
};

bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    u64 parsed = 0ULL;
    for (const char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        const u64 digit = static_cast<u64>(c - '0');
        if (parsed > (std::numeric_limits<u64>::max() - digit) / 10ULL) {
            return false;
        }
        parsed = parsed * 10ULL + digit;
    }

    value = parsed;
    return true;
}

bool parse_arguments(const int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_u64_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return true;
}

u64 sum_of_multiples_below(const u64 limit, const u64 divisor) {
    const u64 n = (limit - 1ULL) / divisor;
    return divisor * n * (n + 1ULL) / 2ULL;
}

u64 solve(const u64 limit) {
    if (limit == 0ULL) {
        return 0ULL;
    }
    return sum_of_multiples_below(limit, 3ULL) + sum_of_multiples_below(limit, 5ULL) -
           sum_of_multiples_below(limit, 15ULL);
}

bool run_checkpoints() {
    if (solve(10ULL) != 23ULL) {
        std::cerr << "Checkpoint failed for limit=10" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }

    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.limit) << '\n';
    return 0;
}

Python

def sum_of_multiples_below(limit, divisor):
    n = (limit - 1) // divisor
    return divisor * n * (n + 1) // 2

def solve(limit=1000):
    if limit == 0:
        return 0
    return (sum_of_multiples_below(limit, 3)
            + sum_of_multiples_below(limit, 5)
            - sum_of_multiples_below(limit, 15))

if __name__ == "__main__":
    assert solve(10) == 23, "Checkpoint failed for limit=10"
    print(solve())

Java

public class Euler1 {
    static long sumOfMultiplesBelow(long limit, long divisor) {
        long n = (limit - 1) / divisor;
        return divisor * n * (n + 1) / 2;
    }

    static long solve(long limit) {
        if (limit == 0) return 0;
        return sumOfMultiplesBelow(limit, 3)
             + sumOfMultiplesBelow(limit, 5)
             - sumOfMultiplesBelow(limit, 15);
    }

    public static void main(String[] args) {
        assert solve(10) == 23 : "Checkpoint failed for limit=10";
        System.out.println(solve(1000));
    }
}