On to problem nine:

*Question: There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.*

There’s two ways that I could potentially solve this problem. One is to use brute force and test a lot of combinations of numbers to find the solution. Another is to somehow generate a stream of pythagorean triples and test only those, which would likely be faster. However, I could not find a reliable method to do this, so in the end I used brute force.

Here’s my solution:

for a in range(1, 1000):
for b in range(1, 1000):
c = 1000 - a - b
if a**2 + b**2 == c**2:
print(a,b,c, a*b*c)

It’s five lines and runs in 3.5 seconds, not bad for brute force. We test all *a*‘s and *b*‘s in the arbitrary range of 1-1000, and set *c* equal to *1000 – a – b *, since it’s given in the problem that a + b + c = 1000. For each set of *a*, *b*, and *c*‘s, we check to see if it’s a pythagorean triplet by plugging it into the pythagorean theorem. If the numbers all work, we print them and their product.

As for formulas to generate pythagorean triples, I found three of them (that I could understand) from a couple of google searches. I’ll summarize them here.

The first I found was a strange little formula with several names and definitions. This was actually derived from the second formula I found, but the two are distinct enough to treat separately. To the best of my knowledge, Pythagoras came up with this formula first, which is a = m , b =((m2 – 1)/2), c = ((m2 + 1)/2). Wikipedia has a version of this formula where (since a = m) a is substituted into the last two equations. There is also a version where all of these are raised to the power of two (I’m pretty sure the former is more accurate, since it is referenced in both Wikipedia and MathWorld).

However, this formula has limitations, mainly that m has to be odd. So Plato came up with another formula (this is where it gets tricky, there’s actually differing accounts of what this formula is). Wikipedia states that Plato created a formula for only even integers, which was a = m , b = (m/2)2 – 1, c = (m/2)2 + 1. Wikipedia actually substitutes a for m, but I’ll stick with m for the sake of consistency. Another website states that Plato actually came up with a formula for all natural numbers, not just even ones. It’s: a = (2m)2, b = (m2 – 1)2, c = (m2 + 1)2 (slightly modified for consistency). MathWorld also has a formula very similar to this: a = 2m, b = (m2 – 1), c = (m2 + 1). However, this version, as you can see, does not contain the outer exponents and is also not accredited to Plato; instead they claim that it was made by Pythagoras and the Babylonians! There are some serious contradictions here.

I decided not to use these first couple of formulas since they were very inconsistent, and, even overlooking this fact, they do not generate all pythagorean triples. Quick note here: a primitive pythagorean triple is one where its greatest common divisor is one. It is only necessary to find all primitive pythagorean triples, since the rest can be found by multiplying them by any integer.

The second formula I found could actually generate all primitive pythagorean triples. It’s called Euclid’s formula and was stated as: a = v2 – u2, b = 2vu, c = v2 + u2. However, this is only true if v and u are of opposite parity and coprime (i.e. gcf is one). Since it generates all primitive pythagorean triples, we can find all non-primitive triples by multiplying by an arbitrary integer k. However, the constraints for v and u make this impractical to write out in code, so I decided not to use this formula either.

The third formula I found was utilized a sequence of Fibonacci numbers. However, the very fact that it uses Fibonacci numbers makes it impractical to code, and furthermore it does not generate all primitive pythagorean triples. Therefore I couldn’t use the third formula either.

So in the end, I still had to revert to using brute force.

If you’re curious, here are my sources:

http://mathworld.wolfram.com/PythagoreanTriple.html

http://en.wikipedia.org/wiki/Formulas_for_generating_Pythagorean_triples

http://jwilson.coe.uga.edu/EMT668/EMT668.Folders.F97/Edenfield/Pythtriples/Pythriples.html

*Answer: 31875000 (200*375*425)*

Tags: product, pythagorean triple