Pythagorean triples

exercise No. 87

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

Sample integer triple examples:

$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 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

Implement a two-step process:

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

a	b	c
1	1	2
2	1	2
...	...	...
3	4	5
...	...	...
99	99	100

The vast majority of these triplets do not match $a^{2} + b^{2} = c^{2}$ . But (3, 4, 5) for example does.

Filter those triples $(a, b, c)$ from the above table matching $a^{2} + b^{2} = c^{2}$ .

Use three nested loops for creating all possible combinations. Do not yet bother about possible duplicates. Your result output should 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 would 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:

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 current implementation creates a great number of combinations like $(4, 4, 5)$ which can be ruled out beforehand rather then creating and filtering them.

The former solution filters $99^{3}$ combinations or roughly one million yielding just 52 matching ordered triples.

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.

The c leg must be the triangle's longest one. The innermost loop may thus 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");

Result:

( 3,  4,   5)
( 5, 12,  13)
...
(65, 72,  97)
52 triples found by filtering 33338 combinations

In essence we reduced the number of triples being constructed in the first place from nearly a million to just 33338. This is just 3% resulting in much shorter execution time.

Prev	Up	Next
Smallest multiple	Home	Logic related external exercises