"Euler #9 : Pythagorean Triplets"

by Nicolas Wu


Posted on 26 August 2010

Tags: Haskell, Euler


In this article we’ll be solving the following question from Project Euler:

Find the only Pythagorean triplet, (a, b, c), for which a + b + c = 1000.

To solve this problem, we’ll be constructing most of our values from a list comprehesion. There isn’t much to say in this week’s post, so I’ll just cut straight to the heart of the problem.

Much of the work in calculating these triplets can be avoided by ensuring that a < b < c. Here’s the code that takes this into account:

> triplets :: Int -> [[Int]]
> triplets n = [[a, b, c] | a <- [1 .. n `div` 3]
>                         , b <- [a+1 .. (n - a) `div` 2]
>                         , let c = n - a - b
>                         , a*a + b*b == c*c]

The code above produces all the triplets that sum to some value n. Since the question actually asks for the product of these three numbers, we calculate this by using the product function, which calculates the product of a list:

> euler9 = (product . head . triplets) 1000

Summary

Well, this week’s challenge hasn’t stretched us very much. I guess here’s a lesson we can learn:

  • List comprehensions are powerful, but helping them by restricting productions makes them even better!

Comments