Monday, May 05, 2008

At first glance, Project Euler problem five looks like a walk in the park:

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 number that is evenly divisible by all of the numbers from 1 to 20?

Sounds easy! The most straightforward solution is to take the sequence of all natural numbers, filter those that are evenly divisible by 1 through 20, and pop off the first element of the sequence (the head). Something like the code below would do the trick.

{ 1L .. Int64.max_int }
  |> Seq.filter (fun n ->
       [1L .. 20L] |> List.for_all (fun d -> n % d = 0L))
  |> Seq.hd

Unfortunately, that solution, while direct, falls far outside of Project Euler's "one-minute rule." It eventually calculates the correct answer but takes as much as 10 minutes on my machine!

OK, let's take a step back. What exactly is the problem asking us to find? Stating it differently, "What is the least common multiple of all of the numbers from 1 to 20?"

The least common multiple (LCM) of two numbers is the smallest number that is evenly divisible by each. Still not familiar? Think about how fractions are added. The first step in adding fractions is to find the least common denominator, which is simply the LCM of the denominators. For example, given the fractions 1/8 and 1/12, we would find the LCM of 8 and 12. Then, the fractions would be rewritten with the LCM (24) as their denominators. Once this is done, we can easily add the fractions 3/24 and 2/24 to get the answer, 5/24.

So, how should we go about calculating the LCM of two numbers? It turns out that there are many well-known possibilities. One of the most popular methods involves finding the prime factors of both numbers. It goes something like this:

Suppose we wanted to find the least common multiple of 160 and 90. First, we would write out the prime factors of each:

160 = 25 * 51
90 = 21 * 32 * 51

The least common multiple can be computed by multiplying the highest power of each unique factor.

lcm(160,90) = 25 * 32 * 51 = 1440.

Many people have chosen this method when working through problem five, and I was tempted to take this road as well because it would allow us to reuse our primeFactors function from problem three. However, the code would be fairly complex.

let countItems lst =
  let incrCount m i =
    match Map.tryfind i m with
    | Some(c) -> Map.add i (c+1) m
    | None -> Map.add i 1 m

  lst |> List.fold_left incrCount Map.empty |> Map.to_list

let lcm x y =
  let rec updateMap m t =
    let i,c = t
    match Map.tryfind i m with
    | Some(v) when v < c -> Map.add i c m
    | None -> Map.add i c m
    | _ -> m

  let factors =
    [x; y]
    |> primeFactors
    |> countItems
    |> List.fold_left (List.fold_left updateMap) Map.empty

  Map.fold (fun i c res -> res * int64 (float i ** float c)) factors 1L

Personally, I feel a sense of accomplishment at writing all of those folds—particularly the double-fold near the end, that's really cool. :-) However, it's pretty far below my standard for code beauty. If you recall, I'm trying to present the most beautiful solution that I can. So, I'm rejecting this solution, even though it's efficient enough to meet Project Euler's requirements. Admittedly, there's a certain beauty in the list transformations, but there's a much better method.

The least common multiple of two numbers can be calculated quite simply using their greatest common divisor (GCD), or the largest number that divides evenly into both numbers. The GCD can be computed easily with the Euclidean algorithm. Here's how it works:

  1. Start with 2 natural numbers, x and y
  2. If y is equal to zero, the answer is x.
  3. If not, set x to the value of y, and y to the remainder of dividing x by y.
  4. Go back to step 2.

For the more visual among you, a flowchart of the Euclidean algorithm is pictured below.


Once we have the GCD, calculating the LCM is easy. Simply divide x by the GCD of x and y, and multiply the result by y. These two algorithms can be implemented quite beautifully in F#.

let rec gcd x y =
  if y = 0 then x
  else gcd y (x%y)

let lcm x y =
  if x = 0 or y = 0 then 0
  else (x / (gcd x y)) * y

However, the F# libraries already supply a function to calculate the GCD of two numbers. The greatest common denominator also goes by another name, highest common factor (HCF), and there is an HCF function in the Microsoft.FSharp.Math.BigInt module. It's a simple matter to rewrite lcm using BigInt.hcf.

open Microsoft.FSharp.Math

let lcm x y =
  if x = 0I or y = 0I then 0I
  else (x / (BigInt.hcf x y)) * y

With lcm in place, would you believe that our solution looks like this?

[1I..20I] |> List.reduce_left lcm

F# can produce truly beautiful code indeed!

posted on Monday, May 05, 2008 5:12:44 AM (Pacific Standard Time, UTC-08:00)  #    Comments [6]

kick it on