The 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?

F# Solution

It is very easy to brute force this solution. However, Project Euler has this rule stated clearly on their main page:

I’ve written my program but should it take days to get to the answer?

Absolutely not! Each problem has been designed according to a “one-minute rule”, which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

Given that, my initial reaction is that testing every single positive integer for all factors <= 20 is might not make it under the one-minute rule.

I’m a big believer in the principle of optimizing code later if you have to. The primary goal of code should be clarity. I try to write the clearest code I can first and then optimize it later if I have to. This is in stark contrast to the way I used to write code back in the 80s and 90s, when processor power was expensive and scarce, and programs were smaller in scope. Now, processor power is cheap and plentiful and programs are increasingly complex. In the context of large, complicated programs, it makes sense to make code clarity the primary goal. If you follow the Single Responsibility Principle, refactoring things to make them faster is very easy.

With that in mind, here is the unoptimized algorithm:

let factors = [| 1..20 |]

let isEvenlyDivisible i =
    factors
    |> Seq.forall (fun d -> i % d = 0)

let rec smallestEvenlyDivisible = function
    | x when isEvenlyDivisible x -> x
    | x -> smallestEvenlyDivisible (x+1)

#time
smallestEvenlyDivisible 20
#time

isEvenlyDivisble takes an array of factors and tests the input i against all of them.

smallestEvenlyDivisble keeps incrementing x until it finds an x for which isEvenlyDivisble returns true.

Note that I’ve included #time directives around the part of the code that does the work. If you run this code in the F# REPL, it will spit out interesting timing data. On one of the cores in my 3.9Ghz processor, the code takes 24 seconds to run.

Real: 00:00:24.333, CPU: 00:00:24.328, GC gen0: 1777, gen1: 4, gen2: 1

24 seconds gets us under the 1-minute rule, so my initial reaction was wrong. But the decision to go forward with the clearest code possible was right.

But I’m not really happy about the results. I think we can do much better and still meet the goal of clarity.

The array of factors seems the best candidate for optimization. It is simply not necessary to check every single one of them. At the very least, we can eliminate 1.

We can also eliminate 2. We know the solution must be even because the answer must be evenly divisible by 2. Thus, we can change the algorithm to only check even numbers, which eliminates half the work our program must do.

let factors = [| 3..20 |]

let isEvenlyDivisible i =
    factors
    |> Seq.forall (fun d -> i % d = 0)

let rec smallestEvenlyDivisible = function
    | x when isEvenlyDivisible x -> x
    | x -> smallestEvenlyDivisible (x+2)

#time
smallestEvenlyDivisible 20
#time

Now we’re down to 10 seconds.

Real: 00:00:10.410, CPU: 00:00:10.406, GC gen0: 889, gen1: 2, gen2: 1

We can also eliminate 20 as a factor and only check numbers that are multiples of 20.

let factors = [| 3..19 |]

let isEvenlyDivisible i =
    factors
    |> Seq.forall (fun d -> i % d = 0)

let rec smallestEvenlyDivisible = function
    | x when isEvenlyDivisible x -> x
    | x -> smallestEvenlyDivisible (x+20)

#time
smallestEvenlyDivisible 20
#time

Now I’m down to 1.2 seconds. I’d feel reasonably good about stopping there, except that there are more factors we can eliminate from the array at only a tiny cost to clarity.

• We can eliminate 3 and 5 and leave 15, because 3 and 5 are factors of 15.
• We can eliminate 4 and 8 and leave 16.
• We can eliminate 6 and 9 and leave 18.
• We can eliminate 7 and leave 14.
• We can eliminate 10 because we’re only testing multiples of 20, which are also divisible by 10.

Thus, we only have to test factors [| 11..19 |], which brings the total execution time own to 0.953 seconds on my machine.

Now I feel like I’m done.