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\).
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
-
solutions.problem39.solve()¶ Compute the answer to Project Euler’s problem #39