Sunday, July 5, 2009

Grind Report 10

Problem 9

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 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) - n^(2)) + (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*
)

3 comments: