Project Euler 39: Integer right triangles

Question

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)

Answer 1

• 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):
      return max(xrange(limit/2, limit + 1), key=find_pythagorean_triples)