PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 223 / だいたい直角三角形1

三辺(a≤b≤c)がすべて整数の三角形で,三辺が次の式をみたしているものを"わずかに鋭角(barely acute)"と呼ぶ。

 a^2+b^2=c^2+1

周辺の長さが 25,000,000 以下のわずかに鋭角な三角形はいくつあるか。

Problem 223 - Project Euler

Solve で整数解を求める

まず,検算用を兼ねて絶対に間違えようのない方法で解きました。Solve で整数解を求めています。計算時間は 156 分。


素因数分解の利用

a^2-1=c^2-b^2 を利用します。

 (a+1)(a-1)=(c+b)(c-b)

a^2-1 = xy (x≦y)と素因数分解できたとします。c-b=x, c+b=y から

 c=(x+y)/2,\, b=(y-x)/2

これらが a≦b≦c などをみたす条件を考えます。

  • b, c が整数になる条件は x, y の偶奇が一致すること
  • 三角不等式 c-b < a < b+c から x< a< y
  • 周の長さの条件から a+y< 25*10^6
  • a≦b より a≦(y-x)/2(b≦c は自動的に成立する)

a^2-1 の約数の中でこれらの条件をみたすものを数えました。80分。


並列化

時間短縮のため,For ループの中身を関数化して ParallelSum をとるように書き直しました。

また,a の範囲を少しせばめています。
a+b+c≦p と c=√(a^2+b^2+1)から

 a+b+\sqrt{a^2+b^2+1}\leqq p

 \therefore 2a+\sqrt{2a^2+1}\leqq p

これを整理すると a≦p/(2+√2) を得ます。

計算時間は23分です。割りと満足しました。