Welcome back F# junkies! In this installment of YAPES^{1}, we’re tackling Project Euler problem nine.

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

a^{2}+b^{2}=c^{2}

For example, 3^{2}+ 4^{2}= 9 + 16 = 25 = 5^{2}.

There exists exactly one Pythagorean triplet for whicha+b+c= 1000. Find the productabc.

Like we’ve done before, we’ll break this problem down into steps:

- Generate a stream of Pythagorean triples.
- Find the Pythagorean triple whose sum is equal to 1000.
- Calculate the product of that triple.

Sound good?

The first order of business is to determine how to generate Pythagorean triples. It turns out that there are many ways to do this. However, to keep it simple, we will use Euclid’s classic formula:

Given a pair of positive integersmandnwithm>n

a= 2mn,b=m^{2}–n^{2},c=m^{2}+n^{2}

Truthfully, this formula doesn’t actually produce every possible Pythagorean triple. However, since the solution is within the set that it generates, that really isn’t a problem.

**NeRd Note**

*every*Pythagorean triple, we would have to introduce an additional parameter,

*k*, into the formula.

a= 2kmn,b=k(m^{2}–n^{2}),c=k(m^{2}+n^{2})

First, we’ll declare an F# function that calculates a Pythagorean triple using Euclid’s formula.

let a = 2*m*n

let b = m*m - n*n

let c = m*m + n*n

a,b,c

Using the above function, it’s easy to produce a stream of Pythagorean triples. Our strategy will be to start with the pair, *m* = 2 and *n* = 1. To generate the next pair, we’ll first check if *n* + 1 is less than *m*. If it is, we’ll use *m* and *n* + 1 as the next pair, otherwise we’ll use *m* + 1 and 1. Using Seq.unfold, we can use this algorithm to produce an infinite stream of Pythagorean triples:

Seq.unfold (fun (m,n) ->

let res = getTriple m n

let next = if n+1 < m then m,n+1 else m+1,1

Some(res, next))

(2,1)

With our generator in place, we can easily solve the problem.

|> Seq.find (fun (a,b,c) –> a+b+c = 1000)

|> (fun (a,b,c) –> a*b*c)

While the above solution works well, we can abstract further to produce a more elegant solution. First, we’ll declare three functions to handle the three operations that we’re performing explicitly, *sum*, *product* and *equals*.

let product (a,b,c) = a*b*c

let equals x y = x = y

Now, we can restate our solution using these functions with a bit of function composition to produce a truly beautiful solution.

|> Seq.find (sum >> equals 1000)

|> product

As we’ve seen once before, function composition is beautiful.

^{1}Yet Another Project Euler Series

Page rendered at Monday, December 22, 2014 1:05:54 AM (Pacific Standard Time, UTC-08:00)

{12 Days of Refactor!} {Articles} {C#} {CodeRush} {Community} {Debugging} {Extending Visual Studio} {F#} {Feeble Attempts At Humor} {Functional Programming} {Geek Life} {History} {IntelliSense} {It's all about me} {Learning} {LINQ} {Microsoft} {Music} {Power Tools} {Project Euler} {Quality Code} {Rants} {Refactor!} {Speaking} {The Bleeding Edge} {Tips & Tricks} {Visual Basic} {Visual Studio} {Why I Love F#} {XML Literals} {Z-Machine} |

WPF 4 Unleashed

Adam Nathan

If feel a bit behind and need to catch up on WPF, this is **the** book.

Programming F#

Chris Smith

Great book on F# containing from Beginner to Advanced. It even has chapters on more arcane features of the language, such as Computation Expressions and Quotations.

Purely Functional Data Structures

Chris Okasaki

Because this book provides source code in Standard ML, it's a fantastic resource for learning F#. One bit of warning: this book does not teach classic data structures. While structures such as binomial heaps and red-black trees are presented, it is assumed that the reader already knows and understands them.

World War Z: An Oral History of the Zombie War

Max Brooks

That's right. This isn't a programming book. It's a

*diversion*. Reading programming books all of the time is hazardous to your happiness and well-being. Take the time to enjoy something else. You'll thank me later.

**Disclaimer**

The opinions expressed herein are my own personal opinions and do not represent
my employer's view in any way.

This work is licensed under a Creative Commons Attribution 3.0 United States License.

© Copyright 2014 Dustin Campbell

Sign In