## Sunday, July 5, 2009

### Grind Report 10

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.

*Warning: This contains the solution!*

As I began working on this problem I decided I should learn a little bit more about Pythagorean triplets. So I went to the Wikipedia page for them. Here I found the useful Euclid's formula.
$a = 2mn \,:\, b = m^2 - n^2 \,:\, c = m^2 + n^2$
I started playing around with this...

a + b + c = 1000
2mn + (m2 - n2) + (m2 + n2) = 1000
2mn + 2m2 = 1000
mn + m2 = 500

Unfortunately I only have one equation and 2 unknowns so I wasn't quite sure what to do with this by hand. There are two things I do know though.
1. m > n > 0
2. both m and n are integral
3. m must be less than sqrt(500) = 22.36
In order to solve this I quickly threw together a simple program to figure out m and n.

` for (int m = 1; m <= 22; ++m){for (int n = 1; n < m; ++n){if (m * n + m * m == 500) cout << m << ", " << n;}}`
This could have been much more efficient like starting from 22 and working down.

20, 5 was the output to this program. I simply had to plug them back in and then solve for abc. Very simple and easy. I may come back to this and write something to be able to solve for any number - not just 1000. We'll see.

*saved game*