$2520$ is the smallest number that can be divided by each of the numbers from $1$ to $10$ without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from $1$ to $20$?
We want to basically find the lowest common multiple (LCM) of 1, 2, ..., 20. Since $\operatorname{lcm}(a, b) = \operatorname{lcm}(b, a)$ and $\operatorname{lcm}(a, b, c) = \operatorname{lcm}(a, \operatorname{lcm}(b, c))$ we can iteratively compute the LCM using
function smallest_multiple(n)
result = 1
for i in 2:n
result = lcm(result, i)
end
return result
end
where the Julia lcm function computes the LCM using
and where $\operatorname{gcd}(a, b)$ is the greatest common divisor (GCD) of $a$ and $b$. Julia's gcd function computes the GCD using the binary GCD algorithm.
Computing smallest_multiple(20) is then done very quickly in just 190.313 ns.
The result grows very quickly with smallest_multiple(42) being the largest that does not overflow Int64, returning 219060189739591200 in 712.629 ns.
smallest_multiple(88) is the largest that does not overflow Int128, returning 8076030954443701744994070304101969600 in 7.670 μs.
We can keep going past 88 using BigInt. Going all the way to smallest_multiple(BigInt(100000)) returns a 43452-digit number in 475.060 ms.