Pythagorean triples

exercise No. 82

Q:

Pythagorean triples are integer combinations of three values being related by the Pythagorean theorem:

Find all Pythagorean triples ( a , b , c ) of non-zero integer values which simultaneously obey the additional constraint a + b + c = 840 .

Tip

Think of creating all possible triples ( a , b , c ) not yet obeying any restrictions at all:

a b c
1 1 1
2 1 1
... ... ...
838 838 838

Why does an upper value of 838 rather then the proposed sum value of 840 appears here?

This list mostly contains values like ( 1 , 3 , 4 ) failing both our restrictions 1 2 + 3 2 4 2 and 1 + 3 + 4 840 . These triples have thus to be filtered retaining only the desired combinations simultaneously obeying both a 2 + b 2 = c 2 and a + b + c = 840 . This might be accomplished by implementing three nested loops:

for (int a = 1; a <= 838; a++) {
   for (int b = 1; b <= 838; b++) {
       for (int c = 1; c <= 838; c++) {
          if (a*a + b*b == c*c &&     // Pythagorean condition
              a + b + c == 840) {     // sum constraint
             System.out.println(" Found (" + a + ", " + b + ", " + c + ")");
          }
       }
    }
}

The above code generating 838 × 838 × 838 = 588480472 combinations will run quite some time! Thus we are looking for a better (more efficient) solution.

There are several issues with the above code. It creates a great number of combinations like ( 1 , 4 , 3 ) which could be ruled out beforehand easily rather then creating and filtering them. Do we really need three nested loops?

Also triples having identical values but in a different order like (40, 399, 401) and (40, 401, 399) are equivalent. For this reason we may consider only triples being ordered by size.

So the problem can be stated to find the set of all triples ( a , b , c ) [ 1 , 838 ] 3 which simultaneously obey:

  1. a b c

  2. a + b + c = 840

  3. a 2 + b 2 = c 2

A:

Since each variable value must be greater than zero the maximum possible value is 840 - 1 - 1 = 838.

The last triple obeying both restrictions 1 and 2 is (280, 280, 280). Due to the restriction a + b + c = 840 two variable values already determine the third one: For a given value of variable a from the outer for loop any value of b will imply c = 840 - a - b .

We thus only need two nested loops for generating all possible triples: If the value of b is being incremented by 1 then c has to be decremented by 1 as well and is thus completely determined.

For convenience reasons we introduce a variable int sum = 840 representing our sum of all three values. Our filter condition now only needs to check for the remaining Pythagorean condition a 2 + b 2 = c 2 :

final int sum = 840;

for (int a = 1; a <= sum / 3; a++) {

   final int aSquare = a * a; // Calculate square of variable a
                              // outside subsequent loop.

   for (int b = a, c = sum - a - b; b < c; b++, c--) {

      if (aSquare + b * b == c * c) { // Filter for pythagorean triples
          System.out.println("(" + a + ", " + b + ", " + c + ")");
      }
   }
}

This leaves us with eight triples:

(40, 399, 401)
(56, 390, 394)
(105, 360, 375)
(120, 350, 370)
(140, 336, 364)
(168, 315, 357)
(210, 280, 350)
(240, 252, 348)

The above code can be simplified even further. We introduce the variable s being shorthand for sum in our Java code. The inner for loop so far starts with a value of b = a and thus c = s - 2 a . Then during each step b is being incremented by 1 and c will be decremented by the same amount.

Regarding the n-th step of the inner for loop we thus look for a value of n so that the following equation becomes true:

a 2 + ( a + n ) 2 b 2 = ( s - 2 a - n ) 2 c 2

Solving this equation for n results in:

n = ( s - 2 a ) 2 - 2 a 2 2 ( s - a )

So for each given value of a there is either no or exactly one possible solution (since n is of integer type). Our inner nested loop becomes obsolete.

The above equation must hold for integer arithmetic leaving no fractional remainder. We introduce two variables numerator and denominator representing the above terms ( s - 2 a ) 2 - 2 a 2 and 2 ( s - a ) . The remainder of modulus operator % testing for a zero remainder filters the desired triples:

final int sum = 840;

for (int a = 1; a <= sum / 3; a++) {

  final int numerator = (sum - 2 * a) * (sum - 2 * a) - 2 * a * a,
          denominator = 2 * (sum - a);

  final int remainder =  numerator % denominator;
  if (0 == remainder) {
     final int n = numerator / denominator;
     System.out.println("(" + a + ", " + (a + n) + ", " + (sum - 2 * a - n) + ")");
  }
}

This yields the same result as before but execution is (again) ways faster paying off when looking for larger values of sum.