Project Euler Problem 9 in F#

Project Euler Problem 9 introduces the interesting mathematical concept of Pythagorean Triple. Let’s have a look at the question:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

As usual, I first show my solution and then comment on the approach:

#light

// generate triplets using Euclid's Formula
let pythagorean_triplets top =
    [ for m in 1 .. top do
          for n in 1 .. m-1 do
          let a = m*m-n*n
          let b = 2*m*n
          let c = m*m+n*n
          yield [a;b;c] ]

// multiply all the values of a list     
let multiply_list list =
    List.fold (fun acc elem -> acc*elem) 1 list

// find a triplet where the sum of values 
// is equal to a given number
let find_triplet_with_sum sum =
    pythagorean_triplets sum
    |> List.find (fun [a;b;c] -> a+b+c=sum)

let problem_9 () =
    find_triplet_with_sum 1000 
    |> multiply_list

Let’s go through the solution step by step:

• The first function, pythagorean_triplets uses Euclid’s Formula to enumerate all possible Pytagorean Triplets up to a given threshold. The formula can be summarized like this:
  a = m² – n², b = 2mn, c = m² + n², where m and n are positive integers with m > n.

  It’s interesting to note that each item of the list is itself a list of three numbers. I could have generated a tuple, but since in the end I need to multiply all the 3 values together, the list was more straightfoward to use.

• multiply_list is just a convenience function to multiply all the elements of a list together
• find_triplet_with_sum does the heavy work of generating the actual triplets picking the first one where the sum is equal to a given value.
• At the end I just put the pieces together and solve the problem.

One caveat: Euclid’s Formula does not generate all Pytagorean Triplets(there are other formulas that do). I can say that I have been lucky that it generated the one requested by the Project’s Euler problem. The code above might not work if the goal is changed to find a triplet with a different product.

See all Project Euler problems solutions.