can anyone optimize my python code for "Pythagorean triplets"?

Question

I have written a code to find Pythagorean triplets but it is not optimized

it took 5-6 minutes for the algorithm to find answer for big numbers... my teacher said it should take less than 3 secs...

num = int(input())

def main(n):
    for x in range(1, n):
        for y in range(1, x):
            for z in range(1, y):
                if x + y + z == n:
                    if x * x == y * y + z * z or y * y == x * x + z * z or z * z == x * x + y * y:
                        a = f'{z} {y} {x}'
                        print(a)
                        return

    else:
        print('Impossible')

for example if you enter 12, you'll get 3,4,5 if you enter 30 , the answer will be 5,12,13

The sum of these three numbers must be equal to the number you entered.

can anyone please help me ?

Answer 1

Note the proof for the parametric representation of primitive pythagorean triples. In the proof, the author states:

We can use this proof to write an optimized algorithm:

def p(num):
    a, b, c = 1, 1, 0
    n = 0

    while c < num:
        for m in range(1, n):
            a = 2 * m * n
            b = n ** 2 - m ** 2
            c = n ** 2 + m ** 2

            if c >= num:
                return "Impossible!"
            elif a + b + c == num:
                return b, a, c

        n = n + 1

print(p(12)) # >>> (3, 4, 5)
print(p(30)) # >>> (5, 12, 13)
print(p(31)) # >>> Impossible!

Answer 2

The approach you discussed takes O(n^3) complexity.

An efficient solution is to run two loops, where first loop runs from x = 1 to n/3, second loop runs from y = x+1 to n/2. In second loop, we check if (n – x – y) is equal to (x * x + y * y):

def pythagoreanTriplet(n): 

    # Considering triplets in  
    # sorted order. The value  
    # of first element in sorted  
    # triplet can be at-most n/3. 
    for x in range(1, int(n / 3) + 1):  

        # The value of second element  
        # must be less than equal to n/2 
        for y in range(x + 1,  
                       int(n / 2) + 1):  

            z = n - x - y 
            if (x * x + y * y == z * z):  
                print(x, " ", y, " ",  z)
                return

    print("Impossible") 

# Driver Code 
n = int(input())
pythagoreanTriplet(n)

PS: Time complexity = O(n^2)

Answer 3

You're doing a lot of repeated and unnecessary work. You know that A^2 + B^2 = C^2 and you know that C > B > A. It doesn't matter if you want to say C > A > B because any solution you find with that would be satisfied with C > B > A. For instance take 12 and solution 3, 4, 5. It doesn't actually matter if you say that A=3 and B=4 or A=4 and B=3. Knowing this we can adjust the loops of each for loop.

A can go from 1 to num, that's fine. Technically it can go to a bit less since you are adding another value to it that has to be at least 1 as well.

B then can go from A+1 to num since it needs to be greater than it.

So what about C? Well it doesnt' need to go from 1 since that's not possible. In fact we only care about A + B + C = num, so solve for C and you get C = num - A - B. That means you don't need to use a loop to find C since you can just solve for it. Knowing this you can do something like so:

In [142]: def find_triplet(num): 
 ...:     for a in range(1, num-1): 
 ...:         for b in range(a+1, num): 
 ...:             # A^2 + B^2 = C^2 
 ...:             # And A+B+C = N 
 ...:             c = num - a - b 
 ...:             if c > 0:
 ...:                 if a*a + b*b == c*c: 
 ...:                     print(f'{a} {b} {c}') 
 ...:             else: 
 ...:                 break 
 ...:                                                                                                                    

In [143]: find_triplet(30)                                                                                                   
5 12 13

So why check to see if C > 0 and break otherwise? Well, if you know C = num - A - B and you are incrementing B, then once B becomes too large, C is going to continue to get more and more negative. Because of that you can check if C > 0 and if it's not, break out of that inner loop to have A increment and B reset.