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

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.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