A Pythagorean Triplet is a 3 number sequence of a, b and c such that
a2 + b2 = c2
Some examples of Pythagorean triplets are
3,4 and 5 where 32 + 42 = 52, that is 9 + 16 = 25
Another example is 8, 15 and 17
82 + 152 = 172, that is 64 + 225 = 289
The Solution
The straightforward solution to this problem is running 3 loops and checking for the existence of a Pythagorean Triplet.
Let us say we want to find all triplets from 1 to 10
Steps
1. Run a loop (i) from 1 to 10
2. Run a loop (j) from i + 1 to 10
3. Run a loop (k) from j + 1 to 10
4. Check for all cases where i*i + j*j == k*k and print them. the loop will run 1000 times in this case. In general cases it will run n*n*n times where n is the limit.
Here is one solution:
# Program to find all Pythagorean Triplets up to limit
"""
Pythagorean triplet is a three number sequence like 3,4 and 5,
where 3 squared + 4 squared = 5 squared
9 + 16 = 25
"""
loopruns = 0
count = 0
n = 20 # Set the limit
for i in range(1, n + 1): # Run a loop of i from 1 to the limit
for j in range(i + 1, n + 1): # Run another loop of j from i+1 to the limit
for k in range(j + 1, n + 1): # Run loop of k from j+1 to the limit
loopruns += 1 # Count the number of times the loop runs. We will optimize it using this
if i * i + j * j == k * k: # Check if current combination is a Pythagorean Triplet
count += 1 # If triplet found then increment the count
print(count, ")", i, ",", j, ",", k, ', triplet is ', i * i, " + ", j * j, " = ",
k * k) # Print the triplet with full info
print("Loop runs ", loopruns, "times")
# End Program
Output
1 ) 3 , 4 , 5 , triplet is 9 + 16 = 25
2 ) 5 , 12 , 13 , triplet is 25 + 144 = 169
3 ) 6 , 8 , 10 , triplet is 36 + 64 = 100
4 ) 8 , 15 , 17 , triplet is 64 + 225 = 289
5 ) 9 , 12 , 15 , triplet is 81 + 144 = 225
6 ) 12 , 16 , 20 , triplet is 144 + 256 = 400
Loop runs 1140 times
Process finished with exit code 0
Can we run the i loop lesser no of times and still get a solution. i*i + j*j = k*k is the condition. The highest value for k*k is going to be n*n In our case n= 20 therefore the highest value of k*k is going to be 400. Half of 400 is 200. Therefore i*i and j*j can be 200 at most, i therefore can be square root of 200 at the most. Let us incorporate this in our program.
Optimized Version of the above program
# Program to find all Pythagorean Triplets up to limit
"""
Pythagorean triplet is a three number sequence like 3,4 and 5,
where 3 squared + 4 squared = 5 squared
9 + 16 = 25
"""
loopruns = 0
count = 0
n = 20 # Set the limit
looplimit = int(((n * n) / 2) ** .5)
for i in range(1, looplimit + 1): # Run a loop of i from 1 to the limit
remaining = int((n * n - i * i) ** 0.5)
for j in range(i + 1, remaining + 1): # Run another loop of j from i+1 to the limit
for k in range(j + 1, n + 1): # Run loop of k from j+1 to the limit
loopruns += 1 # Count the number of times the loop runs. We will optimize it using this
if i * i + j * j == k * k: # Check if current combination is a Pythagorean Triplet
count += 1 # If triplet found then increment the count
print(count, ")", i, ",", j, ",", k, ', triplet is ', i * i, " + ", j * j, " = ",
k * k) # Print the triplet with full info
print("Loop runs ", loopruns, "times")
# End Program
Output
1 ) 3 , 4 , 5 , triplet is 9 + 16 = 25
2 ) 5 , 12 , 13 , triplet is 25 + 144 = 169
3 ) 6 , 8 , 10 , triplet is 36 + 64 = 100
4 ) 8 , 15 , 17 , triplet is 64 + 225 = 289
5 ) 9 , 12 , 15 , triplet is 81 + 144 = 225
6 ) 12 , 16 , 20 , triplet is 144 + 256 = 400
Loop runs 1075 times
Process finished with exit code 0
Run this program with n=100
# Program to find all Pythagorean Triplets up to limit
"""
Pythagorean triplet is a three number sequence like 3,4 and 5,
where 3 squared + 4 squared = 5 squared
9 + 16 = 25
"""
loopruns = 0
count = 0
n = 100 # Set the limit
looplimit = int(((n * n) / 2) ** .5)
for i in range(1, looplimit + 1): # Run a loop of i from 1 to the limit
remaining = int((n * n - i * i) ** 0.5)
for j in range(i + 1, remaining + 1): # Run another loop of j from i+1 to the limit
for k in range(j + 1, n + 1): # Run loop of k from j+1 to the limit
loopruns += 1 # Count the number of times the loop runs. We will optimize it using this
if i * i + j * j == k * k: # Check if current combination is a Pythagorean Triplet
count += 1 # If triplet found then increment the count
print(count, ")", i, ",", j, ",", k, ', triplet is ', i * i, " + ", j * j, " = ",
k * k) # Print the triplet with full info
print("Loop runs ", loopruns, "times")
# End Program
Output
1 ) 3 , 4 , 5 , triplet is 9 + 16 = 25
2 ) 5 , 12 , 13 , triplet is 25 + 144 = 169
3 ) 6 , 8 , 10 , triplet is 36 + 64 = 100
4 ) 7 , 24 , 25 , triplet is 49 + 576 = 625
5 ) 8 , 15 , 17 , triplet is 64 + 225 = 289
6 ) 9 , 12 , 15 , triplet is 81 + 144 = 225
7 ) 9 , 40 , 41 , triplet is 81 + 1600 = 1681
8 ) 10 , 24 , 26 , triplet is 100 + 576 = 676
9 ) 11 , 60 , 61 , triplet is 121 + 3600 = 3721
10 ) 12 , 16 , 20 , triplet is 144 + 256 = 400
11 ) 12 , 35 , 37 , triplet is 144 + 1225 = 1369
12 ) 13 , 84 , 85 , triplet is 169 + 7056 = 7225
13 ) 14 , 48 , 50 , triplet is 196 + 2304 = 2500
14 ) 15 , 20 , 25 , triplet is 225 + 400 = 625
15 ) 15 , 36 , 39 , triplet is 225 + 1296 = 1521
16 ) 16 , 30 , 34 , triplet is 256 + 900 = 1156
17 ) 16 , 63 , 65 , triplet is 256 + 3969 = 4225
18 ) 18 , 24 , 30 , triplet is 324 + 576 = 900
19 ) 18 , 80 , 82 , triplet is 324 + 6400 = 6724
20 ) 20 , 21 , 29 , triplet is 400 + 441 = 841
21 ) 20 , 48 , 52 , triplet is 400 + 2304 = 2704
22 ) 21 , 28 , 35 , triplet is 441 + 784 = 1225
23 ) 21 , 72 , 75 , triplet is 441 + 5184 = 5625
24 ) 24 , 32 , 40 , triplet is 576 + 1024 = 1600
25 ) 24 , 45 , 51 , triplet is 576 + 2025 = 2601
26 ) 24 , 70 , 74 , triplet is 576 + 4900 = 5476
27 ) 25 , 60 , 65 , triplet is 625 + 3600 = 4225
28 ) 27 , 36 , 45 , triplet is 729 + 1296 = 2025
29 ) 28 , 45 , 53 , triplet is 784 + 2025 = 2809
30 ) 28 , 96 , 100 , triplet is 784 + 9216 = 10000
31 ) 30 , 40 , 50 , triplet is 900 + 1600 = 2500
32 ) 30 , 72 , 78 , triplet is 900 + 5184 = 6084
33 ) 32 , 60 , 68 , triplet is 1024 + 3600 = 4624
34 ) 33 , 44 , 55 , triplet is 1089 + 1936 = 3025
35 ) 33 , 56 , 65 , triplet is 1089 + 3136 = 4225
36 ) 35 , 84 , 91 , triplet is 1225 + 7056 = 8281
37 ) 36 , 48 , 60 , triplet is 1296 + 2304 = 3600
38 ) 36 , 77 , 85 , triplet is 1296 + 5929 = 7225
39 ) 39 , 52 , 65 , triplet is 1521 + 2704 = 4225
40 ) 39 , 80 , 89 , triplet is 1521 + 6400 = 7921
41 ) 40 , 42 , 58 , triplet is 1600 + 1764 = 3364
42 ) 40 , 75 , 85 , triplet is 1600 + 5625 = 7225
43 ) 42 , 56 , 70 , triplet is 1764 + 3136 = 4900
44 ) 45 , 60 , 75 , triplet is 2025 + 3600 = 5625
45 ) 48 , 55 , 73 , triplet is 2304 + 3025 = 5329
46 ) 48 , 64 , 80 , triplet is 2304 + 4096 = 6400
47 ) 51 , 68 , 85 , triplet is 2601 + 4624 = 7225
48 ) 54 , 72 , 90 , triplet is 2916 + 5184 = 8100
49 ) 57 , 76 , 95 , triplet is 3249 + 5776 = 9025
50 ) 60 , 63 , 87 , triplet is 3600 + 3969 = 7569
51 ) 60 , 80 , 100 , triplet is 3600 + 6400 = 10000
52 ) 65 , 72 , 97 , triplet is 4225 + 5184 = 9409
Loop runs 152285 times
Process finished with exit code 0
.png)
0 Comments