Problem
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?
Answer
1 | 232792560 |
The critical insight of this problem is this:
$$divisibleto(x) = n \times divisibleto(x-1)$$
This means that when searching for the smallest number divisible to 20,
we can increment by the smallest number divisible to 19 each time (since the
smallest number divisible to 19 is inherently a factor of the smallest number
divisible to 20).
This insight is used in the python solution on line 14:
step = divisible_to(x-1)
This is a recursive solution to the problem, and yields incredible performance. It can calculate
the smallest number divisible to 500 in a fraction of a second.
Python1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22#!/usr/bin/env python
def is_divisible_to(number, x):
for i in reversed(list(range(1, x+1))):
if number % i != 0:
return False
return True
def divisible_to(x):
if x < 1:
return False
elif x == 1:
return 1
else:
step = divisible_to(x-1)
number = 0
found = False
while not found:
number += step
found = is_divisible_to(number, x)
return number
print(divisible_to(20))
JavaScript1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16function isDivisibleTo(x, n) {
for (; n > 0; n -= 1) {
if (x % n !== 0) {
return false
}
}
return true
}
function divisibleTo(n) {
if (n === 1) return 1
for (var step = divisibleTo(n - 1), i = step; !isDivisibleTo(i, n); i += step);
return i
}
console.log(divisibleTo(20))
Go1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18package main
import "fmt"
func GCD(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
func main() {
lcm := 1
for i := 2; i <= 20; i++ {
lcm *= i / GCD(i, lcm)
}
fmt.Println(lcm)
}
Ruby1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#!/usr/bin/env ruby
class Numeric
def divisible_to?(x)
self > 0 and x.downto(1).all? { |i| self % i == 0 }
end
end
def divisible_to(x)
if x < 1
return false
elsif x == 1
return 1
else
n = 0
step = divisible_to(x-1)
until n.divisible_to? x
n += step
end
return n
end
end
puts divisible_to(20)
Rust1
2
3
4
5
6
7
8
9
10
11
12
13
14
15fn gcd(mut a: u64, mut b: u64) -> u64 {
while b != 0 {
let t = a;
a = b;
b = t % b;
}
a
}
fn main() {
let lcm = (2..21).fold(1, |acc, i| {
acc * i / gcd(i, acc)
});
println!("{}", lcm);
}
Haskell1
2
3
4
5
6
7
8
9
10isDivisibleTo :: Integer -> Integer -> Bool
isDivisibleTo x n = all (\i -> n `mod` i == 0) (reverse [1..x])
divisibleTo :: Integer -> Integer
divisibleTo 1 = 1
divisibleTo x = let step = divisibleTo (x-1)
in head $ filter (isDivisibleTo x) [step,2*step..]
main :: IO ()
main = print $ divisibleTo 20
Clojure1
2
3
4
5
6
7
8
9
10#!/usr/bin/env clojure
(defn divisible-to-x? [n x]
(every? #(= (rem n %) 0) (reverse (range 1 (+ x 1)))))
(defn divisible-to [x]
(if (= x 1)
x
(first (filter #(divisible-to-x? % x) (iterate inc (divisible-to (- x 1)))))))
(println (divisible-to 20))
Mathematica1
2
3
4
5
6
7
8(*
* The smallest number n that is evenly divisible by every number in a set {k1, k2, ..., k_m}
* is also known as the lowest common multiple (LCM) of the set of numbers.
* The LCM of two natural numbers x and y is given by LCM(x, y) = x * y / GCD(x, y).
* When LCM is applied to a collection of numbers, it is commutative, associative, and idempotent.
* Hence LCM(k1, k2, ..., k_m) = LCM(...(LCM(LCM(k1, k2), k3)...), k_m).
*)
Apply[LCM, Range[20]]
Java1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30import java.math.BigInteger;
public final class p005 implements EulerSolution {
public static void main(String[] args) {
System.out.println(new p005().run());
}
/*
* The smallest number n that is evenly divisible by every number in a set {k1, k2, ..., k_m}
* is also known as the lowest common multiple (LCM) of the set of numbers.
* The LCM of two natural numbers x and y is given by LCM(x, y) = x * y / GCD(x, y).
* When LCM is applied to a collection of numbers, it is commutative, associative, and idempotent.
* Hence LCM(k1, k2, ..., k_m) = LCM(...(LCM(LCM(k1, k2), k3)...), k_m).
*/
public String run() {
BigInteger allLcm = BigInteger.ONE;
for (int i = 1; i <= 20; i++)
allLcm = lcm(BigInteger.valueOf(i), allLcm);
return allLcm.toString();
}
private static BigInteger lcm(BigInteger x, BigInteger y) {
return x.divide(x.gcd(y)).multiply(y);
}
}
