Pythagorean triples

exercise No. 87

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

Some integer triples do exist e.g.:

$3^{2} + 4^{2} = 5^{2}$
$6^{2} + 8^{2} = 10^{2}$
$5^{2} + 12^{2} = 13^{2}$

For most combinations however at least one value will be of real rather than of integer value e.g.:

$3^{2} + 5^{2} = {5,83095...}^{2}$
$5^{2} + {4,8989...}^{2} = 7^{2}$

Find all Pythagorean triples $(a, b, c)$ of non-zero integer values being smaller than 100 each. Keep the limit of 100 flexible.

Tip

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

a	b	c
1	1	2
2	1	2
...	...	...
99	99	100

Why does an upper value of 99 appears here for a and b? Why do we have a lower bond of 2 for the variable c?

Tip

Consider using three nested loops for creating all possible combinations. Do not yet bother about possible duplicates. Your result output may look like:

Found (4, 3, 5)
Found (3, 4, 5)
Found (8, 6, 10)
Found (6, 8, 10)
...

A value of e.g. b == 100 would imply a == 0 contradicting the description. Likewise c == 1 wouls imply either a == 0 or b == 0;

We create all possible combinations by using three nested loops and filtering for the desired results:

final int LIMIT = 100;

for (int c = 1; c <= LIMIT; c++) {
    for (int b = 1; b < LIMIT; b++) {
        for (int a = 1; a < LIMIT; a++) {
            if (a * a + b * b == c * c ) {              // Limit output by filtering for pythagorean triples;
                System.out.println("Found (" + a + ", " +
                        "" + b + ", " + c + ")");
            }
        }
    }
}

This results in:

Found (4, 3, 5)
Found (3, 4, 5)
Found (8, 6, 10)
Found (6, 8, 10)
Found (12, 5, 13)
...
Found (96, 28, 100)
Found (80, 60, 100)
Found (60, 80, 100)
Found (28, 96, 100)

Note duplicates like (4, 3, 5) and (3, 4, 5) being present in the above list

exercise No. 88

Avoiding duplicates and gaining performance

There are several issues with the previous solution:

It creates a great number of combinations like $(4, 4, 5)$ which could be easily ruled out beforehand rather then creating and filtering them.

The former solution filters $99^{3}$ combinations or roughly one million.
Triples having identical values of a and b in different order like (3, 4, 5) and (4, 3, 5) are equivalent. For this reason we look for ordered triples only.

The problem can thus be restated to find the set of all triples $(a, b, c) \in {[1, LIMIT]}^{3}$ simultaneously obeying:

$a \leq b < c$
$a^{2} + b^{2} = c^{2}$

Your solution shall account for both the number of combinations being evaluated and the number of Pythagorean triples being found creating a final line like:

...
(60, 63, 87)
(60, 80,100)
(65, 72, 97)
52 triples found by filtering 33338 combinations

Your solution should find all 52 triples by filtering from at most 33338 combinations. If you do need less combinations in the first place please let me know. I'm more than happy publishing an enhanced solution.

Based on our previous solution we introduce the following changes:

We start with the rectangle's smaller leg:
```
...
for (int a = 1; a < LIMIT - 1; a++) {
  ...
}
...
```
Note
- Our rectangle's legs a and b must differ. Otherwise $a^{2} + a^{2} = 2 a^{2} = c^{2}$ would imply $c = a \sqrt{2}$ which cannot be satisfied for natural numbers.
- From a rectangular triangle's perspective c must be larger than both legs a and b respectively.
- We want our triples to be ordered. Thus $0 < a < b < c \leq LIMIT$ must hold and the rectangle's leg a therefore can only exceed a value of LIMIT - 2.
Since $a < b$ holds the next inner loop is straightforward:
```
...
for (int b = a + 1; b < LIMIT; b++) {
  final int /* useful constants*/
    aPlusB = a + b,
    aSquarePlusBsquare = a * a + b * b;
  ...
}
...
```
Note

The two variables aPlusB and aSquarePlusBsquare will not have to be re-calculated inside the innermost loop yet to be defined.
We are dealing with triangles. c must thus be longer than the triangle's longest leg. The innermost loop will terminate on multiple conditions:
```
...
for (int c = b + 1;
     c <= LIMIT &&                                          
     c < aPlusB &&                    // 
     c * c <= aSquarePlusBsquare;
     c++) { ...
```

Finally we re-write our filtering condition:

...
if (aSquarePlusBsquare == c * c) {              // Equivalent to a² + b² == c²
  System.out.format("(%2d, %2d, %3d)\n", a, b, c);
}

Piecing together these snippets and adding two variables comparisons and countTriples for accounting yields our final solution:

final int LIMIT = 100;

int comparisons = 0, countTriples = 0;

for (int a = 1; a < LIMIT - 1; a++) {
  for (int b = a + 1; b < LIMIT; b++) {
    final int
       aPlusB = a + b,
       aSquarePlusBsquare = a * a + b * b;

    for (int c = b + 1;         // c must be longer than the maximum of a and b
             c <= LIMIT &&
             c < aPlusB &&          // c must be smaller than the sum of a and b
             c * c <= aSquarePlusBsquare; // c² must not be larger than a² + b²
             c++) {
        if (aSquarePlusBsquare == c * c) {              // Equivalent to a² + b² == c²
          System.out.format("(%2d, %2d, %3d)\n", a, b , c);
          countTriples++;
        }
        comparisons++;
    }
  }
}
System.out.println(countTriples + " triples found by filtering " + comparisons + " combinations");

Prev	Up	Next
Smallest multiple	Home	Logic related external exercises