1. Pythagorean triples
VC2M9SP03: level 9: design, test and refine algorithms involving a sequence of steps and decisions based on geometric constructions and theorems; discuss and evaluate refinements
creating an algorithm using pseudocode or flow charts to apply the triangle inequality, or an algorithm to generate Pythagorean triples
1.1. Pythagorean triples up to a given integer
Euclid’s formula for Pythagorean triples is a way to generate sets of three positive integers that satisfy the equation \(a^2 + b^2 = c^2\), where a, b and c are the sides of a right-angled triangle. The formula states that if you choose any two positive integers m and n, where m > n, then the following equations will give you a Pythagorean triple:
\(a = 2mn\)
\(b = m^2 - n^2\)
\(c = m^2 + n^2\)
For example, if you choose m = 3 and n = 2, then you get:
\(a = 2 \times 3 \times 2 = 12\)
\(b = 3^2 - 2^2 = 9 - 4 = 5\)
\(c = 3^2 + 2^2 = 9 + 4 = 13\)
1import math # import the math module
2
3def pythagorean_triples(num):
4 # create an empty list to store the triples
5 triples = []
6 # initialize c and m variables
7 c, m = 0, 2
8 # initialize a flag variable
9 done = False
10 # loop until c exceeds the given limit or done is True
11 while m <= math.sqrt(num):
12 # loop over n from 1 to m-1
13 for n in range(1, m):
14 # check if m and n are coprime and have different parity i.e not both odd by checking remainders form div by 2
15 if math.gcd(m, n) == 1 and m % 2 != n % 2:
16 # calculate a using Euclid's formula
17 a = m * m - n * n
18 b = 2 * m * n
19 c = m * m + n * n
20 # if c exceeds the limit, set done to True and break the inner loop
21 if c < num:
22 # append the triple to the list after checking the limit
23 triples.append([a, b, c])
24 # triples.append(sorted([a, b, c]))
25 print([n,m],[a, b, c])
26 # increment m by 1
27 m += 1
28 # print([n,m],end=" ")
29 # return the list of triples
30 return triples
31
32# print the result for num = 100
33pt = pythagorean_triples(100)
34pt = sorted(pt, key=lambda x: x[2])
35print(pt)
36
37#Output:
38# [[3, 4, 5], [5, 12, 13], [15, 8, 17], [7, 24, 25], [21, 20, 29], [35, 12, 37], [9, 40, 41], [45, 28, 53],
39# [11, 60, 61], [33, 56, 65], [63, 16, 65], [55, 48, 73], [13, 84, 85], [77, 36, 85], [39, 80, 89], [65, 72, 97]]
Sample output giving lists of Pythagorean triples for numbers up to 100.
[[3, 4, 5], [5, 12, 13], [15, 8, 17], [7, 24, 25], [21, 20, 29], [35, 12, 37], [9, 40, 41],
[45, 28, 53], [11, 60, 61], [33, 56, 65], [63, 16, 65], [55, 48, 73],
[13, 84, 85], [77, 36, 85], [39, 80, 89], [65, 72, 97]]
A second verion is below that uses list comprehension with conditionals:
The := operator is called the walrus operator or the assignment expression. It allows you to assign a value to a variable and use it in the same expression.
the value of math.pow(m, 2) + math.pow(n, 2)
is assigned to the variable c and then compared with num. This way, you don’t have to calculate c twice or use a separate line to assign it.
The walrus operator was introduced in Python 3.8 and can be used in list comprehensions, lambda functions, if statements and other places where you want to avoid repeating calculations or code.
1import math # import the math module
2
3def pythagorean_triples(num):
4 # create a list comprehension to generate the triples
5 triples = [[int(a), int(b), int(c)] for m in range(2, math.ceil(math.sqrt(num)))
6 for n in range(1, m)
7 if math.gcd(m, n) == 1 and m % 2 != n % 2
8 and (c := math.pow(m, 2) + math.pow(n, 2)) < num
9 and (a := math.pow(m, 2) - math.pow(n, 2)) > 0
10 and (b := 2 * m * n) > 0]
11 # return the sorted list of triples
12 return sorted(triples, key=lambda x: x[2])
13
14# print the result for num = 100
15print(pythagorean_triples(100))
16
17
18#Output:
19# [[3, 4, 5], [5, 12, 13], [15, 8, 17], [7, 24, 25], [21, 20, 29], [35, 12, 37], [9, 40, 41], [45, 28, 53],
20# [11, 60, 61], [33, 56, 65], [63, 16, 65], [55, 48, 73], [13, 84, 85], [77, 36, 85], [39, 80, 89], [65, 72, 97]]
21