# 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:

solutions.problem39.solve()