Select Page

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: $a^2 + b^2 = c^2$

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 $a$, $b$, and $c$.
• 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Â $a$, $b$, and $c$ which we know will satisfy the Pythagorean equation, and therefor will be Pythagorean triplets.

The equations I created used the variablesÂ $m$, and $n$. $a = (m^2 - n^2)$ $b = 2mn$ $c = (m^2 + n^2)$

If we plug those into the Pythagorean equation, we get: $(m^2 - n^2)^2 + (2mn)^2 = (m^2 + n^2)^2$

the left side of that equation becomes: $m^4 - 2m^2n^2 + n^4 + 4m^2n^2 = m^4 + 2m^2n^2 + n^4$

and the right side becomes: $(m^2 + n^2)^2 = m^4 + 2m^2n^2 + n^4$

Since both sides become the same thing, we know the equation is true. That’s great news, because it means our equations to calculateÂ $a$, $b$, and $c$ do in fact work in the Pythagorean equation.

So, how do we use them to find Pythagorean triplets?

Well, we know we never want $a < 1$.

Because of that, we have to constrain our choices to $m > n$.

So now we just choose all of the positive integers $(m, n)$ and plug them into the equations. Â Here’s what we get: $m=2; n=1: (3, 4, 5)$ $m=3; n=1: (8, 6, 10)$ $m=3; n=2: (5, 12, 13)$ $m=4; n=1: (15, 8, 17)$ $m=4; n=2: (12, 16, 20)$ $m=4; n=3: (7, 24, 25)$

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.