Select Page

Brain Teaser: Finding Pythagorean Triplets

Jul 9, 2012

In an earlier post I wrote about a brain teaser from middle school.  Here’s one that is a bit more advanced.

My high school computer teacher issued us a challenge:

“I want you to write an algorithm to identify Pythagorean triplets.”

At the time, I didn’t know what an algorithm was; but a dictionary solved that problem. Sadly, the dictionary let me down on the rest of the problem.

In case you’ve forgotten your geometry, a Pythagorean triplet is any set of integers (a, b, c) that satisfy the Pythagorean equation:

a^2 + b^2 = c^2

(3, 4, 5) is an example of a Pythagorean triplet. It works because:

3^2 + 4^2 = 5^2

Likewise, (8, 15, 17) works. Go ahead and try it.

So that’s what we want to find. But how do we find them?

The “Brute Force” Method

The obvious answer is to pick a value for a, pick another value for b, and then calculate c. But that’s tricky because all three numbers need to be integers. So we have to check to see if c is an integer.

Eventually, most of the students settled on the same approach, or algorithm:

  1. Create a list of possible triplets.
  2. Test each set of three numbers to see if they work.
  3. If they don’t work, discard that triplet.
  4. If they do work, add that triplet to the list of answers.

This means you have to test each individual triplet:

(1, 1, 1)

(1, 1, 2)

(1, 1, 3)

(1, 1, 4)

and so on.

Unfortunately, this is a very slow approach. It requires you to try many, many triplets to find a handful that work. In those days, writing in BASIC or FORTRAN on an Apple II, that meant you could sit there and watch the computer as it found each new triplet.  Even today, this is an incredibly inefficient approach.

The Challenge

So here’s my challenge to you:

Can you think of a better way? How can you find Pythagorean triplets quickly and efficiently, without a lot of wasted effort?

I’ll share one possible approach next week.