Project Euler: Problema 39 (python)

El problema 39 de Project Euler dice lo siguiente:

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.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p 1000, is the number of solutions maximised?

Respuesta: 840

La manera en que he pensado este problema es analizar todos los triángulos rectángulos posibles con lados enteros. El siguiente código genera una lista con todos los triángulos rectángulos de hipotenusa menor o igual a n.
Si n == 20: triangulos_menores(20), entonces esta función devuelve
[(5, 3, 4), (13, 5, 12), (10, 6, 8), (17, 8, 15), (15, 9, 12), (20, 12, 16)]

def triangulos_menores(n):
    #lista de triangulos con hipotenusa 
    #menor o igual a n
    l = []
    n += 1     
    for i in range(1, n):
        for j in range(i, n):
            h = (i ** 2 + j ** 2) ** 0.5 #hipotenusa
            if (h <= n) and (h == round(h)):
                t = (int(h), i, j) #triangulo
                l.append(t)
    return l

Sin embargo el problema no está en función a la hipotenusa, sino al perímetro máximo. Sea p_max el perímetro máximo que puede tener nuestro triángulo y supongamos que tenemos un triángulo de lados variables de catetos ‘i’, 'j’ e hipotenusa 'h’, entonces se cumple: 'h <= p_max - i - j’. La función devuelve un diccionario donde los índices son los perímetros y sus valores son las veces que se repiten: {perimetro: veces-que-se-repite, …}. El código es el siguiente:

import time

inicio = time.time()
def perimetros(p_max):
    dic = {}
    p_max += 1     
    for i in range(1, p_max):
        for j in range(i, p_max):
            h = (i ** 2 + j ** 2) ** 0.5 #hipotenusa
            if (h <= p_max - i -j) and (h == round(h)):
                p = int(h + i + j)
                if p in dic:
                    dic[p] += 1
                else:
                    dic[p] = 1
                        
    return dic

p_max = 1000
d = perimetros(p_max)
d_values = d.values()
d_keys = d.keys()

i = d_values.index(max(d_values))

final = time.time()
tiempo = final - inicio

print "Respuesta: ", d_keys[i]
print "Tiempo: ", tiempo

Recomiendo ver la solución en

http://blog.dreamshire.com/2009/04/22/project-euler-problem-39-solution/