Finding integer lengths for a right triangle with a given perimeter

Question

I'm using Python 3 and have written this code to find the right triangle sides when given the perimeter:

def intRightTri(p):
    l = [(a,b,c) for a in range (1, p)
                 for b in range (1, p)
                 for c in range (1, p)
                 if (a**2 + b**2 == c**2) and (a + b + c == p) and (a<=b) and (b<c)]
    return l

When I run my tests, they work, but the last one seems to be taking a really long time. What would be a good way to improve my code so it executes quicker?

import unittest
tc = unittest.TestCase()
tc.assertEqual(intRightTri(100), [])
tc.assertEqual(intRightTri(180), [(18, 80, 82), (30, 72, 78), (45, 60, 75)])
tc.assertEqual(intRightTri(840), 
           [(40, 399, 401),
            (56, 390, 394),
            (105, 360, 375),
            (120, 350, 370),
            (140, 336, 364),
            (168, 315, 357),
            (210, 280, 350),
            (240, 252, 348)])

Update

New quicker method combining both answers.

def integer_right_triangles(p):
    l = [(a,b,p-a-b) for a in range (1, p)
            for b in range (a, p-a)
            if (a**2 + b**2 == (p - (a+b))**2 )]
    return l

Answer 1

This feels like the sort of thing where you can find a clever algorithm to make it super-efficient. That's not my strength, so I'm just going to point out some simple things you can do to make things faster.

First, I'm going to rewrite it without a list-comprehension to make it easier to think about:

def intRightTri(p):
    triples = []
    for a in range(1, p):
        for b in range(1, p):
            for c in range(1, p):
                if (a**2 + b**2 == c**2) and (a + b + c == p) and (a <= b) and (b<c):
                    triples.append((a, b, c))           
    return triples

And that inner comparison happens p^3 times.

You have some constraints in your check that you can get rid of by setting things up a little more carefully.

def intRightTri(p):
    triples = []
    for a in range(1, p):
        for b in range(a, p):          #ensure b >= a
            for c in range(b+1, p):    #ensure c > b
                if (a**2 + b**2 == c**2) and (a + b + c == p):
                    triples.append((a, b, c))           
    return triples

This is a little better. But then after we have our a and b, there is only one possible value for c to satisfy a + b + c == p, so you don't even need that last nested loop.

def intRightTri(p):
    triples = []
    for a in range(1, p):
        for b in range(a, p-a):     
            c = p - (a + b)
            if a**2 + b**2 == c**2:
                 triples.append((a, b, c)) 
            elif a**2 + b**2 > c**2:
                # As we continue our innermost loop, the left side 
                # gets bigger, right gets smaller, so we're done here
                break    

    return triples

Answer 2

You can improve the performance with a bit of math. Rather than doing this in \$O(p^3)\$ you can do it in in \$O(p)\$.

First remove \$c\$ from the equation:

$$ a + b + c = p\\ c = p - a - b\\ a^2 + b^2 = c^2\\ a^2 + b^2 = (a + b - p)^2$$

After this you can expand the right hand side and simplify.

$$ a^2 + b^2 = (a + b - p)(a + b - p)\\ a^2 + b^2 = a^2 + b^2 + 2ab - 2ap - 2bp + p^2\\ 2ab - 2ap - 2bp + p^2 = 0\\ a = \frac{2bp - p^2}{2b - 2p}\\ $$

Which in Python can be:

def _right_a(p):
    for b in range(1, p // 2):
        a = (2*b*p - p**2) / (2 * (b - p))
        if a % 1:
            continue
        a = int(a)
        yield a, b, p - a - b


def int_right_tri(p):
    return {tuple(sorted(i)) for i in _right_a(p)}