# Project Euler 39: Integer right triangles

I just finished Project Euler 39:

If p is the perimeter of a right angle triangle with integral length sides, {a, b, c} … For which value of p ≤ 1000, is the number of solutions maximised?

I'm pretty satisfied with my solution. I derive the formula for the hypotenuse as follows:

\begin{align} a + b + c &= p \tag{Def. perimeter}\\ b + c &= p - a \tag{2}\\ \\ a^2 + b^2 &= c^2 \tag{Pythagorean}\\ a^2 &= c^2 - b^2 \\ a^2 &= (c - b)(c + b) \\ a^2 &= (c - b)(p - a) \tag{from (2)} \\ \frac{a^2}{p - a} &= c - b \tag{7} \\ \\ (c - b) + (c + b) &= \frac{a^2}{p - a} + (p - a) \tag{from (7) and (2)}\\ 2c &= \frac{a^2}{p - a} + \frac{(p - a)^2}{p - a} \\ 2c &= \frac{a^2 + (p - a)^2}{p - a} \\ c &= \frac{a^2 + (p - a)^2}{2\ (p - a)} \end{align}

Any optimization would be appreciated.

from timeit import default_timer as timer

start = timer()
def find_pythagorean_triples(perimeter):
count = 0
for a in range(3, perimeter / 2 - 1): # triangle inequality
c = (a**2 + (perimeter - a)**2) / (2*(perimeter - a)) # derived formula
b = (c**2 - a**2)**0.5
if b.is_integer() and a + b + c == perimeter:
count += 1
return count

def find_most_solutions_upto(limit):
data = {"most": 0, "num": 0}
for p in range(limit/2, limit + 1): # scale upwards
if find_pythagorean_triples(p) > data['most']:
data['most'] = find_pythagorean_triples(p)
data['num'] = p
return data['num']

ans = find_most_solutions_upto(1000)
elapsed_time = (timer() - start) * 1000 # s --> ms

print "Found %d in %r ms." % (ans, elapsed_time)


• You are using a dictionary data = {"most": 0, "num": 0} where you could just as well use local variables. The locals would be more readable and faster.
• The built-in max function is convenient when looking for a maximum. You could write find_most_solutions_upto like this:
def find_most_solutions_upto(limit):