프로젝트 오일러 139번

Let \((a, \;b, \;c)\) represent the three sides of a right angle triangle with integral length sides. It is possible to place four such triangles together to form a square with length \(c\).

For example, \((3, \;4, \;5)\) triangles can be placed together to form 1 \(5\) by \(5\) square with a \(1\) by \(1\) hole in the middle and it can be seen that the \(5\) by \(5\) square can be tiled with twenty-five \(1\) by \(1\) squares.

However, if \((5, \;12,\; 13)\) triangles were used then the hole would measure \(7\) by \(7\) and these could not be used to tile the \(13\) by \(13\) square.

Given that the perimeter of the right triangle is less than one-hundred million, how many Pythagorean triangles would allow such a tiling to take place?

---

\((a, \;b,\; c)\) 가 모든 변의 길이가 정수인 직각삼각형의 세 변의 길이를 나타낸다고 하자. 이와 같은 직각삼각형 네 개를 가지고 위의 왼쪽 그림과 같이 빗변의 길이 \(c\) 를 한 변으로 하는 정사각형을 만들 수 있다. 예를 들어, 각 변의 길이가 각각 \((3, \;4, \;5)\) 인 직각삼각형으로는 한 변의 길이가 \(5\) 인 정사각형 하나를 만들 수 있는데, 중간에 한 변의 길이가 \(1\) 인 정사각형이 비게 된다. 이때, 위 오른쪽 그림과 같이 비는 정사각형과 똑같은 모양(한 변의 길이가 \(1\)인 정사각형)의 정사각형 스물 다섯개로 전체 정사각형을 빈틈없이 채우는게 가능하다.

그러나 세 변의 길이가 각각 \((5, \; 12,\; 13)\) 인 직각삼각형으로 만든 한 변의 길이 \(13\) 인 정사각형은 중간에 비게 되는 정사각형과 똑같은 모양의 정사각형(한 변의 길이 \(7\) 인 정사각형)들로는 빈틈없이 채우는 것이 불가능하다. 

모든 변의 길이가 정수인 직각삼각형의 둘레의 길이가 \(10^8\) 보다 작은 범위에서 위의 그림처럼 중간에 비는 정사각형과 같은 모양의 정사각형들로 전체 정사각형을 채울 수 있는 직각삼각형은 몇 개 존재할까?

위키피디아에 따르면 피타고라스 수(pythagorean triple)는 피타고라스의 정리 \(a^2 + b^2 = c^2\) 을 따르는 세 자연수 순서쌍 \((a, \;b,\;c)\) 를 말한다. 이 중 \(a, \;b,\; c\) 가 서로소인 피타고라스 수를 원시 피타고라스 수(primitive pythagorean triple)라고 한다. 이 원시 피타고라스 수를 찾는 방법은 다음과 같다.

서로 소인 두 홀수 \(m, \;n\;(m>n>0)\) 에 대해서 \[\begin{split} a &= mn \\ b &= \dfrac{m^2 - n^2}{2} \\ c &= \dfrac{m^2+n^2}{2} \end{split}\] 는 원시 피타고라스의 수가 된다. 또한 \((ka, \; kb,\; kc)\) (단, \(k\) 는 자연수) 는 모두 피타고라스의 수가 된다. 

따라서 문제의 조건을 만족하려면 \(c\) 가 \(|a-b|\) 로 나누어 떨어지는 원시 피타고라스의 수를 먼저 찾은 다음 \(10^8\) 을 \(a+b+c\) 로 나눈 몫을 카운트 해 주면 된다. 물론 \(a+b+c<10^8\) 인 범위에서만 생각한다.

그런데 이런식으로 접근하면 시간이 너무 많이 걸린다. 실제 약 70초 정도가 소요되는 것을 확인할 수 있었다. (물론 본인의 노트북이 고물이긴 하지만...ㅠㅠ)

따라서 다른 방법을 생각해 볼 수 있는데, 이 문제 역시 펠방정식으로 풀어낼 수 있다.

이를 위해서 \(a-b=d\) (단, \(a>b\)) 라고 하자. 문제의 조건에 맞으려면 \(c\) 가 \(d\) 로 나누어 떨어져야 하므로 \(c=qd\) (단, \(q\) 는 정수)라고 할 수 있다. 이를 피타고라스 정리에 대입하면\[a^2 + (a-d)^2 = (qd)^2\] \[ 2a^2 -2ad + d^2 = q^2 d^2\] 양변에 \(2\) 를 곱해주면 \[4a^2 - 4ad + 2d^2 = 2q^2 d^2\] \[(2a-d)^2 +d^2 = 2q^2 d^2\] \(d\ne 0\) 이므로 양변을 \(d^2\) 으로 나누어 주면 \[ \left ( \dfrac{2a}{d} - 1 \right ) ^2 + 1 = 2q^2\] \((a, \;b,\;c)\) 가 원시 피타고라스 수라고 하면 \(a, \;b, \;c\)가 서로 소이고, 유클리드 호제법에 의하여 \(a\)와 \(d=a-b\) 도 서로소가 된다. 이런 상황에서 위 식이 성립하려면 \(\dfrac{2a}{d}-1\) 이 정수가 되어야 하고 결국 \(d=1\) 혹은 \(d=2\) 가 되어야 한다. 그런데 \(d=2\) 라면 위 식은 \((a-1)^2 +1 = 2q^2\) 이 되고 이것이 성립하려면 \(a\) 는 짝수이어야 한다. 이 경우 \(a\) 와 \(d\) 가 서로소라는 사실에 위배되므로 \(d \ne 2\) 이다. 따라서 \(d=1\) 이 되고 주어진 식은 $$(2a-1)^2+1=2q^2$$ 이 된다. 여기서 \( p=2a-1 \) 이라고 하면 펠방정식 $$p^2 - 2q^2 = -1$$ 를 얻을 수 있다. 이것 역시 66번에서 봤던 연분수 전개를 이용하여 정수해를 구해낼 수 있다. 단 \(d=1\) 이므로 직각삼각형 둘레의 길이가 \(p+q\) 가 되고, \(p+q<10^8\) 범위에서 생각하면 된다. 또한 우리가 구한 것이 원시 피타고라스 수를 가정했으므로 \(10^8\) 을 \(p+q\) 로 나눈 몫들을 더해나가면 답을 얻을 수 있다.

파이썬 코드는 다음과 같다.

count = 0
limit = 10 ** 8
(p, q) = (1, 1)
while p + q < limit:
    (p, q) = (p + 2 * q, p + q)
    if p ** 2 - 2 * q ** 2 == -1:
        count += limit // (p + q)

print(count)