It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.
12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)
In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.
120 cm: (30,40,50), (20,48,52), (24,45,51)
Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?
12cm는 선을 구부려서 만들 수 있는 세 변이 모두 정수인 직각삼각형 둘레의 최소값이다. 그리고, 더 많은 예가 있다:
12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)
이와 대비되게, 20cm 길이로는 변이 정수인 직각삼각형을 만들 수 없으며, 어떤 길이로는 1개 이상의 직각삼각형을 만들 수 있다. 예를 들어, 120cm로는 세가지의 변이 정수인 직각삼각형을 만들 수 있다.
120 cm: (30,40,50), (20,48,52), (24,45,51)
L이 선의 길이이고 L이 150만 이하일 때, 1개의 직각삼각형만 만들 수 있는 L은 몇 개 있는가?
--------------------------------------------------------------------------
75번 문제인 것을 보면 좀 더 슬기롭게 해결하기를 요구하는 것 같은데, 문제와 관련되어 아는 공식은 피타고라스 정리 밖에 없으므로, 세 변의 길이가 L이고(a+b+c=L), 짧은 두 변 제곱의 합이 긴 변 제곱과 같다는(a2+b2=c2) 두가지를 이용해 문제를 해결하기로 했다.
실행시간이 너무 많이 걸려, L, a 기준으로 문제에서 제시한 공식을 다시 정리해서 c=(a2+(L-a)2)/2(L-a), b=L-a-c를 구하는 형태로 바꿔보았다. 이 경우에 L은 짝수인 경우에만 계산하도록 해서 시간도 조금 단축시킬 수 있었다. a값이 가장 큰 경우가 a와 b의 값이 같은 때이고, 이 경우 세 변의 합 L=(2+√2)a이며, a=L/(2+√2)a가 된다.
이렇게 범위를 가능한 줄여봤지만 L이 커지면서, a범위도 따라 커져서 실행시간은 여전히 만족스럽지 못했다. L이 10,000 커질때마다 실행시간이 15~20초씩 이전보다 늘어나고 있어 대략 50시간 정도 필요한 것으로 계산되었다.
어쩔수 없이 수학이론의 힘을 빌렸는데, m>n, m+n은 홀수, m과 n의 최대공약수는 1이라는 특성을 가지고 있으며, a=2mn, b=m2-n2, c=m2+n2라는 공식이 있었다. 실제로 계산해보니 여기서 두 수의 값에 따라 제일 짧은 변이 a, b 중에 있을 수 있고, m=2, n=1일때 a=4, b=3, c=5(둘레 12)라는 직각삼각형을 구했으면, 전체 길이가 150만 이하일때까지 계속 곱해서 같은 비례를 가지는 직각삼각형을 모두 구해야 한다.
이렇게 구한 직각삼각형을 대상으로 둘레가 같으면서 a, b, c가 다른 경우를 제외하는 과정을 거치면 되는데, 참고로 150만 이하의 직각삼각형 조합이 백만개가 넘기 때문에 같은 값이 없을 때 리스트에 추가하는 것 보다는 집합을 이용하는 것이 속도가 월등히 빠르게 나왔다.