PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 139 / ピタゴラスタイル

(a, b, c)で各辺の長さが整数の直角三角形の三辺を表す。一辺の長さが c の正方形中に先ほどの三角形を4つ配置することが可能である。

たとえば (3, 4, 5) 三角形は 5×5 の正方形に4つ配置される。このとき, 中央部に 1×1 の穴が空いている。また, 5×5 の正方形は25個の 1×1 の正方形で敷き詰めることができる。

f:id:variee:20170602180407g:plain

しかし,(5, 12, 13) 三角形を使った場合は穴のサイズが 7×7 になり,7×7の正方形では 13×13 の正方形を敷き詰めることができない。

10^8 未満の周囲長を持つ直角三角形を考え,上のような敷き詰め方を許す直角三角形の数を答えよ。

Problem 139 - Project Euler

解法1:ピタゴラス数の一般形

直角三角形の3辺の長さ a, b, c は互いに素な場合,次のように表せます。

 a=m^2-n^2,\, b=2mn,\, c=m^2+n^2

m, n は互いに素な自然数で,m-n は奇数です。

敷き詰め可能な条件は c が |a-b| で割り切れることで,これも m, n で表せます。

また,(a, b, c) が条件をみたすとして,3辺の長さが ka, kb, kc の三角形は
[(10^8-1)/(a+b+c)]個
できます。a, b, c は互いに素でない場合はこの方法で処理できます。

これで計算してみたところ,約3分かかりました。

解法2:ペル型方程式

1分を切るため,もう少し数学的につめ考えることにします。3辺の長さを
a, b, c (a, b, c は互いに素で a< b< c) とおくと
 a^2+b^2=c^2

b-a=k とおいて b を消去します。
 2a^2+2ak+k^2=c^2

k が c の約数ならば,k は a の約数でもあることがわかります。
定義から a, b は互いに素なので,a と k=b-a も互いに素。
k=b-a=1 です。

b=a+1 を a^2+b^2=c^2 に代入すると
 2a^2+2a+1=c^2

これはペル型方程式なので,Reduce コマンドで一般解を求めることができます。その答えを使うと 0.002秒。1分を余裕で切れました。

ちなみに互いに素な (a, b, c) は11個しかありませんでした。