Project Euler #39 - Interger right triangle

프로젝트 오일러 39번

둘레의 길이가 120이 되는 각 변의 길이가 정수인 직각삼각형은 3가지가 있다.

둘레의 길이가 얼마일 때 경우의 수가 가장 많을까? 단, 둘레의 길이는 1000이하.

제일 긴 변을 c 라고 하자.

a^2 + b^2 = c^2

=> a^2 = (c+b)(c-b)

=> c-b < a < c+b

d = c-b 라고 두면 아래와 같이 코딩할 수 있다.

from sympy import divisors

rs = {}
for a in range(3,333):
    for d in [x for x in divisors(a**2) if x < a]:
        if (d + a**2/d) % 2 == 0:
            c = (d + a**2/d) / 2
            b = c - d
            if a < b and a + b + c < 1000:
                if a+b+c in rs: rs[a+b+c] += 1
                else: rs[a+b+c] = 1
    
print max(rs,key=rs.get)

피타고라스 수의 성질을 이용하면 종이에(또는 암산으로) 답을 찾을 수 있다.

a, b, c = m^2-n^2, 2mn, m^2+n^2 이라고 하면,

둘레의 길이는 2m(m+n)이다. 다르게 표현하면, 둘레의 길이 l(숫자 일이 아니라 알파벳 엘)은 2*m*(m+n)의 형태로 표현될 수 있다. 1000이하의 수 중 약수의 수가 최대가 되는 l 을 찾으면 되지 않을까? 

소수를 늘어놓고.. 2, 3, 5, 7, 11

l = 2*3*5*7*11은 1000을 넘어가므로 not good

l = 2*2*3*5*7 은 1000을 넘지 않고 약수가 충분히 많다

l = 2*2*2*3*5*7 도 1000을 넘지 않고 약수가 충분히 많다. 약수가 더 많아질 수는 없다.

그래서 답은 840으로 추측.

(m > n 조건도 체크해야 하는데 생략했으므로 '추측'이라고 했다.)