Project Euler Solution 39: Integer right triangles

In Problem 39: Integer right triangles we take a look at right triangles with a integer side lengths.

If p is the perimeter of a right angle triangle with integral length sides, ${a,b,c}$, there are exactly three solutions for $p = 120$.

${20,48,52}$, ${24,45,51}$, ${30,40,50}$

For which value of $p \le 1000$, is the number of solutions maximised?

Let us first start with a function that gets the number of solutions for a given perimeter. It uses $a < b < c$ and therefore a can only go up to a third of the perimeter. $b$ is restricted such that $c$ can still be larger than $b$.

def get_num_solutions(perimeter: int) -> int:
    num_solutions = 0
    for a in range(1, perimeter // 3):
        for b in range(a, perimeter - 2 * a + 1):
            c = perimeter - a - b
            if a**2 + b**2 == c**2:
                num_solutions += 1
    return num_solutions

We write a simple test case to make sure that it works for the given example.

def test_get_num_solutions() -> None:
    assert get_num_solutions(120) == 3

And then it is easy to write the solution with that because we just need to find the perimeter with the most solutions.

def solution() -> int:
    return max(
        (get_num_solutions(perimeter), perimeter) for perimeter in range(1, 1000)
    )[1]

This computes the correct answer in 8.2 s. It is okay, but not that great.

After solving this one, I looked into the forums to find more ideas to optimize. One observation is that only even perimeters can have solutions. This brings the solution down to 4.1 s, which is much better.

Another person has another insight, which makes this even better. Instead of using only one equation to compute $c$ and then checking the quadratic relation, we can use both relations at the same time. We have $a + b + c = p$ and $a^2 + b^2 = c^2$. We can plug in the former into the latter for $c$ and solve for $b$. We obtain $$ b = \frac{p^2 - 2ap}{2(p-a)} \,. $$ We therefore let $a$ go from $1 \le a < p/3$ such that we still have $a < b < c$. We check for which cases the above equation has an integer solution for $b$. If that $b$ fulfils $a \le b < 1000$, we have found a solution for the triangle.

This idea translated into code is this:

def get_num_solutions(perimeter: int) -> int:
    num_solutions = 0
    for a in range(1, perimeter // 3):
        numerator = perimeter**2 - 2 * a * perimeter
        denominator = 2 * (perimeter - a)
        if numerator % denominator == 0:
            b = numerator // denominator
            if a <= b < 1000:
                num_solutions += 1
    return num_solutions

And it runs in 14 ms, which is way faster than the original version that I came up with.