Generate Pythagorean Triples

Problem

Given an integer limit, generate all Pythagorean Triples with values smaller than limit.

Pythagorean Triples are sets of three positive integers (a, b, c) such that a2 + b2 = c2.
These triples have applications in various mathematical and computational fields. In this article, we’ll discuss how to generate Pythagorean Triples within a given limit using two different approaches.

Naive Approach

One simple approach to generate Pythagorean Triples is to use nested loops to iterate over all possible values of a, b, and c within the given limit. For each combination, we check if it satisfies the Pythagorean theorem. However, this approach has a time complexity of O(n³), which can be inefficient for large limits.

Pseudocode

for a from 1 to limit:
    for b from a+1 to limit:
        for c from b+1 to limit:
            if (a^2 + b^2 == c^2):
                print (a, b, c)

Optimised Approach

A more optimized approach utilizes the fact that Pythagorean Triples can be generated using these formulas:

a = m2 - n2
b = 2mn
c = m2 + n2

Here, m and n are positive integers such that m > n.

a, b and c as calculated using above formulas, will always satisfy the property of pythagorean triples, as explained here:

We want, a2 + b2 = c2

Let's replace the values of a2 and b2 in the above equation:
(m2 - n2)2 + (2mn)2

= m4 + n4 - 2m2n2 + 4m2n2
= m4 + n4 + 2m2n2

Calculating c2, we get:
(m2 + n2)2

= m4 + n4 + 2m2n2

Hence, a2 + b2 = c2

Thus, by iterating over all possible values of m and n, we can generate Pythagorean Triples within the given limit efficiently.

Pseudocode

for m from 2 to sqrt(limit):
    for n from 1 to m-1:
        a = m^2 - n^2
        b = 2*m*n
        c = m^2 + n^2

        if c > limit:
            break
        print (a, b, c)

This approach has a time complexity of O(limit).

Code Implementation

def generate_pythagorean_triples(limit):
    triples = []

    for m in range(2, int(limit**0.5) + 1):
        for n in range(1, m):
            a = m**2 - n**2
            b = 2 * m * n
            c = m**2 + n**2
            if c < limit:
                triples.append((a, b, c))
    return triples


limit = 50
pythagorean_triples = generate_pythagorean_triples(limit)

print("Pythagorean Triples with values smaller than", limit, ":")
for triple in pythagorean_triples:
    print(triple)

Output

Pythagorean Triples with values smaller than 50 :
(3, 4, 5)
(8, 6, 10)
(5, 12, 13)
(15, 8, 17)
(12, 16, 20)
(7, 24, 25)
(24, 10, 26)
(21, 20, 29)
(16, 30, 34)
(9, 40, 41)
(35, 12, 37)
(32, 24, 40)
(27, 36, 45)