Pythagorean Triples

The Pythagorean theorem, linking the sides of a right triangle, is one of the most useful basic mathematical identities. It is also one of the more entertaining. Loomis, in his book The Pythagorean Proposition (1968), gives 370 different proofs of the theorem. However, we’ll more often interested in computing the length of the hypotenuse, or finding triples—three natural numbers that makes the theorem hold—than finding a new proof for it.

There is, of course, the smallest possible triple (defined as involving the smallest possible numbers) 3, 4, 5. But there are infinitely more triples. Let’s see how we can generate them.

Some time in antiquity, Euclid proposed a way of generating triples from two numbers, m and n. He put:

a=m^2-n^2

b=2mn

c=m^2+n^2

And showed that these three numbers respect the Pythagorean theorem. It’s fortunately rather straightforward to verify:

a^2+b^2=c^2

(m^2-n^2)^2+4m^2n^2=(m^2+n^2)^2

m^4-2m^2n^2+n^4+4m^2n^2=m^4+2m^2n^2+n^4

m^4+2m^2n^2+n^4=m^4+2m^2n^2+n^4

This trick, however, is not sufficient to enumerate all possible triples: it cannot generate directly multiples of a given triple. Adding a scaling s will, however, allow us to do just that:

a_s=s(m^2-n^2)

b_s=s(2mn)

c_s=s(m^2+n^2)

*
* *

We now know that there are infinitely many Pythagorean triples. But are they relatively rare? Let’s find out using a simple tool: brute force. The following C++ program enumerates all triples in the first octant of the plane (where a<=b). The program scans the first octant, taking trapezoidal chunks, which I called buckets (because all triples found are in the same “bucket”):

buckets

This slicing makes some optimizations possible, such as scanning less than a rectangular area. The program also makes use of OpenMP parallelism (note the #pragma in the code, that’s all that is needed).

#include <cmath>
#include <string>
#include <iostream>

// -std=c++11
// -fopenmp (if parallelism is wanted)

template <typename T> T sqr(const T & a) { return a*a; }
bool solution(size_t a, size_t b)
 {
  size_t c=sqr(a)+sqr(b);
  return sqr((size_t)std::sqrt(c))==c; // ± safe
 }

int main(int argc, char * argv[])
 {
  if (argc==3)
   {
    size_t limit=std::stoll(argv[1]);
    size_t bucket=std::stoll(argv[2]);

    // let's exploit buckets and symmetry
    size_t all_found=0;

    for (int i=0;i<limit;i+=bucket)
     {
      size_t found_in_bucket=0;

      // scan of trapezoidal region

      #pragma omp parallel for reduction(+:found_in_bucket)
      for (size_t b=i;b<i+bucket;b++)
       for (size_t a=1; a<=b; a++)
        found_in_bucket+=solution(a,b);

      all_found+=found_in_bucket;
      std::cout
       << i << " -- " << i+bucket-1
       << " " << found_in_bucket
       << " " << all_found
       << " " << all_found/(double)sqr(limit)
       << std::endl;
     }
   }
  else
   std::cerr << "need max value (size_t) and bucket size (size_t)" << std::endl;
  return 0;
 }

By symmetry, we should multiply by 8 to get the number of triples over the plane. We could argue that only the first quadrant will yield “true” triples, since non-negative integers all lie in it. I’m not sure it’s a distinction worth making as right triangle may be oriented differently.

With the above program, we get the following density (for the first octant):

density

It indicates that while the triples are rare, their relative number grows as the numbers involved grow.

We can also seek large-scale structures in the distribution of (the first two numbers in) triples across the plane. A quick Mathematica plot shows indeed structure:

pythagorean-triples-small

Click to embiggen:
pythagorean-triples

The strong “straight lines” correspond to the triples linked by a scaling factor s, as above. There are other structures: “arcs” that correspond to rotations of tripples.

*
* *

The Pythagorean triples—or, more precisely, their enumeration—is something more of mathematical recreation than theoretical importance. Indeed, we use the Pythagorean theorem to measure distance (and in any number of dimensions) and aren’t all that worried if the result is integer, rational or irrational. We just don’t care. We think of the hypotenuse as \sqrt{a^2+b^2} and that’s it.

But there are a few use of these triples. For construction, say. It is theorized that the ancient Egyptians managed to build right angles with the triple 3-4-5 (which would require a somewhat accurate ruler). They might even have used it to build Khafre’s pyramid some time around 2550 BC. However, it is thought they new nothing about the theorem itself, that they knew only about particular triples, until the Persian rule, millennia later.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: