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.