Project Euler Problem 39: Integer Right Triangles

The source code for this problem can be found here.

Problem Statement

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\).

\[\lbrace 20,48,52 \rbrace, \lbrace 24,45,51 \rbrace, \lbrace 30,40,50 \rbrace\]

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

Solution Discussion

We are searching for integer solutions \(a,b,c\) s.t. \(a + b + c = p \le 1000\).

The obvious approach to this problem is to search explicitly through values of \(p\), counting the number of integer solutions \((a,b,c)\). However, this involves many redundant calculations; there are better options.

Let \(a,b,c\) be the sides of a right-angled triangle
Let \(c\) be the hypotenuse
Given \(a\) and \(b\), we can solve for \(c\) using Pythagoras’ theorem
Now, if \(c \le 1000\) and \(c \in \mathbb{Z}\) then we have identified a solution for \(p = a + b + c\)

We need only search over all \(a\) and \(b\), solving for \(c\) and filtering out appropriate solutions. Finally, by ensuring that \(b \ge a\), we avoid double counting the simple transposition \((a,b,c) \rightarrow (b,a,c)\).

Solution Implementation

from math import sqrt

from lib.numbertheory import is_square

def solve():
    """ Compute the answer to Project Euler's problem #39 """
    upper_limit = 1000
    answers = [0] * (upper_limit + 1)
    for a in range(1, upper_limit + 1):
        for b in range(a, upper_limit + 1):
            c2 = a * a + b * b
            if c2 <= (upper_limit - a - b) * (upper_limit - a - b) and is_square(c2):
                # a + b + c <= upper_limit
                # c <= upper_limit - a - b
                # c^2 <= (upper_limit - a - b)^2
                c = int(sqrt(c2))
                p = a + b + c
                if p <= upper_limit:
                    answers[p] += 1
    answer = max(range(len(answers)), key=lambda _p: answers[_p])  # find arg-max(answers)
    return answer

expected_answer = 840

Compute the answer to Project Euler’s problem #39