Project Euler #9 - 둘레가 1000인 피타고라스 수 찾기

둘레가 1000이 되는 피타고라스 수는 하나 밖에 없다. 이 때 세 변의 길이의 곱은?

세 변의 길이 a, b, c 를 임의로 a<b<c라고 해 보자. (직각이등변 삼각형은 피타고라스 수가 나올 수 없으니 등호는 무시)
c는 500보다 작아야 하고, 334보다 커야 한다.
b는 (1000-c)/2 보다 크다.
a = 1000-b-c이다.

문제에서 그런 조건을 만족하는 경우는 한가지 밖에 없다고 했으니 loop를 돌다가 하나 찾으면 멈춘다.

def findtri():
    for c in range(500,333,-1):
        for b in range(c-1,(1000-c)/2,-1):
            if c**2 == (1000-b-c)**2 + b**2:
                return (1000-b-c) * b * c

print findtri()

포럼에 올라온 글을 읽다보니

c = m^2 + n^2

b = m^2 - n^2

a = 2mn (m>n)

으로 대체하여 푼 사람이 있다. (c> a, b이지만 a>b, a<b 모두 가능)

이게 뭔가하고 찾아보니 위키피디아에 잘 정리되어 있다. 링크글을 읽어보면 알겠지만 모든 (기본) 피타고라스 수는 이렇게 표현이 가능하다. 즉, a, b, c 에 대해 loop를 돌면서 피타고라스수를 찾는 대신 m,n에 대해 loop를 돌면서 찾는 게 가능하다는 얘기.

이 성질을 이용하면 이번 문제는 암산으로도 풀 수 있다. a+b+c = 1000은, 2m^2+2mn = 2m(m+n) 이 되고, 1000 = 2*1*(1+499)=2*2*(2+248)= ... =2*20*(20+5) 에서 m>n 조건을 만족하는.. m=20, n=5를 찾을 수 있고, 그럼 c = 425, b = 375, a = 200! abc = (400+25)*(400-25)*200=(160000-625)*200=32000000-125000=31875000

(In retrospect,) a,b,c를 m,n으로 바꾸어 푸는 문제는 뒤에 가서 계속 나온다. 프로젝트 오일러를 운영하는 euler라는 필명을 쓰는 운영자가 뒤쪽 포럼에서 말하길.. 이 문제에 딸린 포럼에 올라온 이 글에서 영감을 얻어서 뒤에서 그런 문제를 계속 내게 되었다고 한다. 뒤쪽 문제를 풀려면 이 공식은 잊지 말아야 한다.