Last week I posed a challenge that came from my high school computer teacher: Can you find an efficient method (or “algorithm”) to generate Pythagorean triplets?
As a reminder, a Pythagorean triplet is a set of three integers that satisfy the Pythagorean equation:
This equation is an example of a Diophantine equation. Diophantine equations are just polynomials that require the solutions to be integers. Because of that, they can be hard to solve.
The Brute Force Method
The first method most people try is the brute force method: they simply try a bunch of triplets and see if they work. Not exactly elegant, and very, very slow. But it does work.
A Substitution Method
I didn’t like the idea of having to try triplets over and over again to see if they worked. I wanted a solution you could simply calculate. Here’s the approach I came up with:
- First, we need to find some equations we can use to calculate , , and .
- Second, those equations, when plugged into the Pythagorean equation, must give us a true equation.
- Finally, we can then use those equations to calculate values forÂ , , and which we know will satisfy the Pythagorean equation, and therefor will be Pythagorean triplets.
The equations I created used the variablesÂ , and .
If we plug those into the Pythagorean equation, we get:
the left side of that equation becomes:
and the right side becomes:
Since both sides become the same thing, we know the equation is true. That’s great news, because it means our equations to calculateÂ , , and do in fact work in the Pythagorean equation.
So, how do we use them to find Pythagorean triplets?
Well, we know we never want
Because of that, we have to constrain our choices to
So now we just choose all of the positive integers and plug them into the equations. Â Here’s what we get:
and so on.
As you can imagine, this is far, far faster for generating Pythagorean triplets than the standard “Brute Force” try-every-possible-combination approach.
Let me know if you come up with a better approach.