Problem 5: Smallest Multiple

Mathematical Development

Definitions and Notation

Definition 1. For a prime $p$ and a positive integer $n$, the $p$-adic valuation $v_p(n)$ is the largest exponent $e \ge 0$ such that $p^e \mid n$. By convention, $v_p(0) = +\infty$.

Definition 2. The least common multiple of positive integers $a_1, \ldots, a_k$ is the smallest positive integer $m$ such that $a_i \mid m$ for all $1 \le i \le k$. Equivalently, $v_p(\operatorname{lcm}(a_1, \ldots, a_k)) = \max_i v_p(a_i)$ for every prime $p$.

Theorem 1 (Prime factorization of the LCM). For any positive integer $N$,

Proof. Let $L = \prod_{p \le N,\, p \text{ prime}} p^{\lfloor \log_p N \rfloor}$. We must show (i) $L$ is a common multiple of $\{1, \ldots, N\}$, and (ii) $L$ is minimal among all such common multiples.

(i) $L$ is a common multiple. Let $m$ be any integer with $1 \le m \le N$, and let $p$ be any prime dividing $m$. Then $p^{v_p(m)} \mid m \le N$, so $v_p(m) \le \log_p N$, whence $v_p(m) \le \lfloor \log_p N \rfloor = v_p(L)$. Since this holds for every prime $p$, we have $m \mid L$.

(ii) $L$ is minimal. Suppose $L'$ is a common multiple of $\{1, \ldots, N\}$ with $L' < L$. Then there exists a prime $p$ with $v_p(L') < \lfloor \log_p N \rfloor$. Consider the integer $q = p^{\lfloor \log_p N \rfloor}$. By definition, $\lfloor \log_p N \rfloor$ is the largest integer $e$ with $p^e \le N$, so $q \le N$. Since $L'$ is a common multiple of $\{1, \ldots, N\}$, we require $q \mid L'$, giving $v_p(L') \ge \lfloor \log_p N \rfloor$. This contradicts $v_p(L') < \lfloor \log_p N \rfloor$. $\square$

Lemma 1 (GCD-LCM identity). For positive integers $a$ and $b$,

Proof. For every prime $p$, write $\alpha = v_p(a)$ and $\beta = v_p(b)$. Then:

where the second equality uses the identity $x + y - \min(x,y) = \max(x,y)$, valid for all $x, y \in \mathbb{R}$. Since the $p$-adic valuations agree for every prime $p$, the two positive integers are equal. $\square$

Lemma 2 (Iterative reduction). Define $L_1 = 1$ and $L_k = \operatorname{lcm}(L_{k-1}, k)$ for $k = 2, 3, \ldots, N$. Then $L_N = \operatorname{lcm}(1, 2, \ldots, N)$.

Proof. By induction on $N$.

Base case: $L_1 = 1 = \operatorname{lcm}(1)$.

Inductive step: Assume $L_{k-1} = \operatorname{lcm}(1, \ldots, k-1)$. Then

Since the LCM operation is associative (which follows from the characterization $v_p(\operatorname{lcm}(a_1, \ldots, a_m)) = \max_i v_p(a_i)$), this equals $\operatorname{lcm}(1, \ldots, k)$. $\square$

Theorem 2 (Explicit computation for $N = 20$). We have $\operatorname{lcm}(1, 2, \ldots, 20) = 232{,}792{,}560$.

Proof. The primes up to 20 are $\{2, 3, 5, 7, 11, 13, 17, 19\}$. By Theorem 1,

We compute each prime power:

Therefore:

Step-by-step evaluation:

Editorial

We build the least common multiple incrementally. Starting from $L = 1$, we traverse $k = 2, 3, \ldots, N$, compute $g = \gcd(L, k)$, and update $L$ to $(L / g)k$, which equals $\operatorname{lcm}(L, k)$. This is sufficient because after each step the accumulator is the least common multiple of all integers seen so far, so the final value is $\operatorname{lcm}(1, 2, \ldots, N)$.

Remark. The division by $g = \gcd(L,k)$ is exact by Lemma 1, because

Computing L <- (L / g) * k is therefore mathematically sound and also reduces the risk of overflow in fixed-precision arithmetic.

Theorem 3 (Algorithm correctness). SmallestMultiple(N) returns $\operatorname{lcm}(1,2,\ldots,N)$.

Proof. Let $L_k$ denote the value stored in L after the iteration with index $k$. Initially $L_1 = 1$. At iteration $k \ge 2$, the update rule sets

by Lemma 1. By Lemma 2, this implies

for every $k$. In particular, after the final iteration,

Thus the algorithm is correct. $\square$

Pseudocode

Algorithm: Least Common Multiple of an Initial Segment
Require: An integer N ≥ 1.
Ensure: L = lcm(1, 2, ..., N).
1: Initialize L ← 1.
2: For each k in {2, 3, ..., N} do:
3:     Compute g ← gcd(L, k) and update L ← (L / g) · k.
4: Return L.

Complexity Analysis

Theorem 4 (Complexity). Assuming machine-word arithmetic is constant time for the values encountered, SmallestMultiple(N) runs in $O(N \log N)$ time and $O(1)$ space.

Proof. The loop executes exactly $N-1$ iterations. In the $k$-th iteration, the algorithm computes $\gcd(L_{k-1}, k)$. By the Euclidean algorithm, this requires $O(\log k)$ divisions because the running time depends on the smaller argument, namely $k$.

Therefore the total running time is

The algorithm stores only the variables L, g, and k, so the extra space is $O(1)$. For the present problem, $N = 20$ and the final value $232{,}792{,}560$ fits comfortably in a standard 64-bit integer. $\square$

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Iterative LCM via GCD-LCM identity: lcm(a,b) = a / gcd(a,b) * b
    long long L = 1;
    for (int k = 2; k <= 20; k++) {
        L = L / __gcd(L, (long long)k) * k;
    }
    cout << L << endl;
    return 0;
}

"""Project Euler Problem 5: Smallest Multiple"""

import math
from functools import reduce

def solve(n: int = 20) -> int:
    """Compute lcm(1, 2, ..., n) via iterative GCD-LCM identity."""
    return reduce(lambda a, b: a * b // math.gcd(a, b), range(1, n + 1))

answer = solve()
assert answer == 232792560
print(answer)