Detailed mathematical approach

Problem Summary

The task is to find the smallest positive integer that is divisible by every number from \(1\) through \(n\). For the original Project Euler instance, \(n=20\), so the target is the common multiple shared by the entire interval \([1,20]\), but taken as small as possible.

This is not a search problem over many candidates. The answer is a single arithmetic object:

$L_n=\operatorname{lcm}(1,2,\ldots,n).$

Mathematical Approach

Once the problem is phrased as an lcm, the mathematics becomes very clean. The only questions are which prime powers must appear, and how to build that value efficiently without factoring every number from scratch.

Recasting the Question as an LCM

Any valid answer must be divisible by every \(k\) with \(1 \le k \le n\). By definition, the least common multiple of those numbers is the smallest integer with exactly that property. Therefore

$\boxed{L_n=\operatorname{lcm}(1,2,\ldots,n).}$

If a number is divisible by the whole range, then it is a common multiple, so it must be a multiple of \(L_n\). Conversely, \(L_n\) itself already divides by each member of the range. That proves minimality immediately.

Which Prime Powers Must Appear?

By the Fundamental Theorem of Arithmetic, every positive integer has a unique prime factorization. That means the lcm can be determined prime by prime. For each prime \(p \le n\), we ask for the largest exponent that occurs in some integer between \(1\) and \(n\).

Define

$e_p=\max\{e \ge 0 : p^e \le n\}.$

Then the exponent of \(p\) in \(L_n\) is exactly \(e_p\), so

$L_n=\prod_{p \le n} p^{e_p},$

where the product runs over primes only.

This explains why many numbers contribute nothing new. A composite number only matters when it contains a prime power that has not already appeared. For the original case \(n=20\), the decisive prime powers are

$2^4,\quad 3^2,\quad 5,\quad 7,\quad 11,\quad 13,\quad 17,\quad 19.$

Everything else in \(1,\ldots,20\) is already covered by these factors.

The Recurrence Used by the Implementations

The code does not explicitly enumerate primes. Instead it builds the same value incrementally. Let

$A_1=1,\qquad A_k=\operatorname{lcm}(A_{k-1},k)\quad (k\ge 2).$

The key invariant is

$A_k=\operatorname{lcm}(1,2,\ldots,k).$

The proof is a one-line induction. Assume \(A_{k-1}\) is already the least common multiple of \(1,\ldots,k-1\). Any integer divisible by \(1,\ldots,k\) must then be divisible by both \(A_{k-1}\) and \(k\), so the smallest such integer is exactly \(\operatorname{lcm}(A_{k-1},k)\). After the loop reaches \(k=n\), the accumulator equals \(L_n\).

This also clarifies what each step does: it inserts only the prime-power content of \(k\) that is still missing. If \(k\) brings no larger exponent for any prime, the accumulator stays unchanged.

Why the GCD Identity Is Enough

Each update is computed with the classical identity

$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$

The gcd measures the overlap between the prime factorizations of \(a\) and \(b\), so dividing by it removes the duplicated part before multiplying. The gcd itself is obtained by the Euclidean algorithm:

$\gcd(a,b)=\gcd(b,a\bmod b),\qquad \gcd(a,0)=a.$

So the whole solution is built from a very small chain of ideas: the answer is an lcm, pairwise lcm can be expressed through a gcd, and gcd is cheap to compute recursively.

Worked Example: \(n=10\)

The prime-power description gives

$L_{10}=2^3\cdot 3^2\cdot 5\cdot 7=2520,$

because the largest powers not exceeding \(10\) are \(8,9,5,\) and \(7\).

The iterative recurrence reaches the same answer through the sequence

$1\to 2\to 6\to 12\to 60\to 60\to 420\to 840\to 2520\to 2520.$

The repeated values are informative: \(6\) does not change the accumulator because its factors \(2\) and \(3\) are already present, and \(10\) does not change it because \(2\cdot 5\) is already covered after earlier steps. This is exactly the behavior exploited by the loop.

How the Code Works

The C++, Python, and Java implementations all keep one accumulator, start it at \(1\), and iterate upward from \(2\) to \(n\). After processing \(k\), the accumulator equals the least common multiple of the prefix \(1,\ldots,k\). That invariant is the entire algorithmic core.

The pairwise lcm step is expressed slightly differently in each language, but the mathematics is identical. The C++ implementation delegates the lcm computation to the standard library. The Python implementation builds the lcm from a standard-library gcd. The Java implementation writes the Euclidean loop explicitly and divides by the gcd before multiplying, which keeps the intermediate product smaller. All three versions include the checkpoint \(n=10 \mapsto 2520\). The C++ entry point can also accept another positive value of \(n\), while the Python and Java entry points print the standard \(n=20\) case when run directly.

Complexity Analysis

There are \(n-1\) loop iterations. In the usual arithmetic-step model, each iteration performs one gcd computation, and the Euclidean algorithm needs \(O(\log k)\) remainder steps when paired with \(k\). Summing over \(k=2\) through \(n\) gives \(O(n\log n)\) arithmetic work.

The extra memory usage is \(O(1)\): apart from the loop counter, the algorithm only maintains the current accumulator. If one studies very large \(n\) with full bit complexity, the cost of integer arithmetic grows because \(L_n\) itself grows quickly. For the original Project Euler input \(n=20\), however, the computation is tiny and comfortably fits standard integer types.

Footnotes and References

1. Project Euler Problem 5: Smallest multiple
2. Least common multiple: Wikipedia
3. Euclidean algorithm: Wikipedia
4. Fundamental theorem of arithmetic: Wikipedia
5. Sequence \(\operatorname{lcm}(1,2,\ldots,n)\): OEIS A003418