Project Euler 009 – F#

28 03 2011

Problem 9

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.

Solution

(*

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.

 

*)

 

let testints = [1..998]

let answer = [for a in testints do

                for b in testints do

                    if b >= a

                       && a + b < 1000

                       && a*a + b*b = (1000-a-b)*(1000-a-b) then

                        yield a * b * (1000-a-b)]

             |> List.head

            

 

 

printfn "%A" answer

 

Discussion

I adapted this solution from my C# solution.  It’s actually not as clean as my C# solution which betrays its imperative origins.  I’m not sure I could come up with a much worse way to accomplish this task and yet it still runs quite snappy.  This is going to be roughly 1,000,000 iterations.  The b >= a makes several iterations pretty snappy.  Still, changing the b loop to

for b in [a..998] do

will would be a better decision.  While we’re at it, we could change testints too.  Perhaps tomorrow will have some additional discussion on optimizations.

 

If you have any questions, leave a comment, find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).








Follow

Get every new post delivered to your Inbox.