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^2 + b^2 = c^2For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2
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:
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^2 - n^2, b = 2mn, c = m^2 + n^2 \), 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 togetherfind_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.
Leave a Comment