Project Euler [Problem 39]

いちおう続くぜ

やるぜ

問題

Integer right triangles

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?

私訳

整直角三角形

p を3辺の長さが {a,b,c} である直角三角形の周とすると, p = 120 に対してはちょうど3つの解がある。

{20,48,52}, {24,45,51}, {30,40,50}

p ≤ 1000 の範囲で, 解の個数が最大になる p はいくつか?

解答方針

p を 1..1000 でループすることは確定だ。 問題は p = a + b + c && a²+b² = c² のときに、 p に対して a, b, c の組を如何に効率よく網羅的に探すかだ。

p に対して a, b, c いずれかを与えたら残りふたつが導出できるのが望ましい。

そこで、 c を与えることにする。というのも、a と b は対称だからだ。 なお、解答例を見ると a <= b という制限がかけられていることがわかる。 とはいえ、制限がなければ a と b は入れ替えられる（が c は入れ替えられない）。

そこで p = a + b + c を変形してみる。

p-c = a+b, (p-c)² = (a+b)² = a²+b²+2ab = c² + 2ab (p-c)²-c² = 2ab p(p-2c) = 2ab

こうなるとだいぶ見通しがたつ。 1. a, b, c はすべて整数なので、p は偶数でなければならない。 2. c < p/2 でなければならない 3. c が最小になるのは、a = b のときのはずなので、そのとき実数なら c = p/(2+sqrt(2)) したがって p/(2+sqrt(2)) < c < p/2 4. さらに、p-c = K, p(p-2c) = L と置いて、a について解くと K = a+b = a+L/2a, a²-Ka+L/2 = 0 ∴ a = (K-sqrt(K²-2L))/2 となる 5. 整理すれば a = (p-c) - sqrt(c²+2pc-p²), b = (p-c) + sqrt(c²+2pc-p²), となる

あとは計算するだけ……。

2023/03/16 追記 いや。式変形できるじゃん。 (p-c)²-c² = 2ab なのだから (b-a)² = a²-2ab+b² = c² + c² - (p-c)² = 2c²-(p-c)² b-a = sqrt(2c²-(p-c)²) これが整数でなければその時点でアウト。 整数なら a+b と b-a が得られているので、a, b も得られる。