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×divisibleto(x1)\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

Haskell

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