60 Days of Euler in F# - Problem 9

This took me a lot longer to solve than it should have. In fact, I got the solution right, then started over from scratch. The end result was much better.

The Problem

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

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

The Solution

First, let’s define some functions that let us know when we have the right answer:

let max = 1000

let isTriplet (a,b,c) = a*a + b*b = c*c

let isSpecial (a,b,c) = a+b+c=max

isTriplet returns true if a,b,c is a Pythagorean triplet. isSpecial returns true if the sum of a,b,c is 1000. If both return true for an a,b,c, that’s our answer.

Since we like expressing our problems as a pipeline, here’s the plan of attack.

  • Use Seq.unfold to generate a sequence of possible triplets
  • Use Seq.filter to filter out triplets that don’t add up to 1000
  • Use Seq.filter to filter out non-Pythagorean triplets
  • The first one of those is our answer.

The first thing we need is a sequence generator. This is made up of two functions, incState and generator. incState finds the next triplet.

let incState = function
    | a,b,c when b<>(max-1) && c=max -> a,b+1,b+2
    | a,b,c when b=(max-1) && c=max -> a+1,a+2,a+3
    | a,b,c -> a,b,c+1

I could have made this slightly simpler, but since the problem definition specifies that a < b < c, I wanted to make sure that the result of this function obeyed that rule. Doing so decreases the possible sequences from 1 billion to about 160 million, which is quite the improvement.

let generator ((a,_,_) as state) =
    if a>=(max-1) then
        Some(state, (incState state))

The above generates a sequence of triplets by incrementing the state until a hits 999.

Now that we can tell if we have the answer and we have a sequence of possible answers, finding the answer is easy:

Seq.unfold generator (1, 2, 997)
|> Seq.filter isSpecial
|> Seq.filter isTriplet
|> Seq.head
Other Posts in This Series