## 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:

$\displaystyle 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.000s

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.001s
user   0m0.000s
sys    0m0.000s

## 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 --harmony-destructuring divisible.js real 0m0.078s user 0m0.068s sys 0m0.008s ## 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.019s
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.027s
user   0m0.024s
sys    0m0.000s