# Project Euler Problem 5 Solution

## Question

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?

## Commentary

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.

## Go

package 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)
}
$go build -o divisible divisible.go$ time ./divisible
real   0m0.001s
user   0m0.000s
sys    0m0.001s

isDivisibleTo ::  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
$ghc -O2 -o divisible divisible.hs$ time ./divisible
real   0m0.002s
user   0m0.000s
sys    0m0.002s

## JavaScript

function 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))
$time node --use-strict divisible.js real 0m0.052s user 0m0.039s sys 0m0.013s ## Python #!/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)) $ time python3 divisible.py
real   0m0.016s
user   0m0.016s
sys    0m0.000s

## Ruby

#!/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)
$time ruby divisible.rb real 0m0.038s user 0m0.038s sys 0m0.000s ## Rust fn 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); } $ rustc -C target-cpu=native -C opt-level=3 -o divisible divisible.rs
\$ time ./divisible
real   0m0.001s
user   0m0.000s
sys    0m0.001s