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

1. Problem page: Project Euler 1
2. Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle
3. Arithmetic progression: Wikipedia - Arithmetic progression
4. Triangular number: Wikipedia - Triangular number
5. Least common multiple: Wikipedia - Least common multiple
6. Floor function: Wikipedia - Floor and ceiling functions