Project Euler problem 9 in one line of Haskell

Problem 9 of Project Euler asks you to find the product of the sole Pythagorean triplet, the sum of whose values is 1000, where a Pythagorean triplet (familiar from elementary school math) is a set of natural numbers  a < b < c where a^2 + b^2 = c^2.

This snippet of Haskell solves it in one line and demonstrates some of what makes Haskell an interesting language, but takes several minutes to run on my MBP:

problem9 = take 1 [a * b * c | a <- [1..1000], b <- [1..1000], c <- [1..1000], a + b + c == 1000, a^2 + b^2 == c^2]

A version with some simple improvements runs much faster. Since a < b < c, we know the largest possible value for a is 332 (since 333 + 334 + 335 is 1002). And since b must be larger than a, we can narrow down its possible values as well, based on a. C does not need to be independently calculated at all, since by definition it must be a value that will satisfy the Pythagorean theorem. So:

problem9' = floor $ head [a * b * sqrt (a^2 + b^2) | a <- [1..332], b <- [(a+1)..(999-a)], a + b + sqrt (a^2 + b^2) == 1000]

This version runs in a couple seconds.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.