Problem 39 - If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p ≤ 1000, has the most solutions?

링크

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?

참고

Problem 9 - "Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000"

python

import math import fractions ans = (0, 0) for p in range(12, 1001, 2): cnt = 0 p2 = p / 2 mlimit = int(math.ceil(p2**0.5) - 1) for m in range(2, mlimit + 1): if p2 % m == 0: pm = p2 / m while pm % 2 == 0: pm = pm / 2 if m % 2 == 1: k = m + 2 else: k = m + 1 while k < 2*m and k <= pm: if pm % k == 0 and fractions.gcd(k, m) == 1: cnt += 1 k += 2 tmp = (cnt, p) ans = max(ans, tmp) print ans