読者です 読者をやめる 読者になる 読者になる

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 75 / 1通りの整数直角三角形

ある長さの鉄線を折り曲げて3辺の長さが整数の直角三角形を作るとき,その方法が1通りしかないような最短の鉄線の長さは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) は3辺の長さが整数の直角三角形に折り曲げることができない。また,2つ以上の折り曲げ方があるものもある。120cmの長さの鉄線を用いた場合,3通りの折り曲げ方がある。

120 cm: (30,40,50), (20,48,52), (24,45,51)

Lを鉄線の長さとする。直角三角形を作るときに1通りの折り曲げ方しか存在しないような L ≤ 1,500,000 の総数を答えよ。

Problem 75 - Project Euler


ピタゴラス数の一般式を使って解きました。a^2+b^2=c^2 の解は次のように書けます。

a=k(m^2-n^2), b=2kmn, c=k(m^2+n^2)

m, n, kは自然数で,mとnは互いに素,m-nは正の奇数です。
周の長さは L=a+b+c=2km(m+n)。

k の範囲は m, n の値によって決まるので2段階にわけて数えます。

  • k=1の三角形のリストを作る(myList1)
  • k≧1の三角形のリストを作る(myList2)
  • Tally[ ] で myList2 から重複度1のものを抽出

こんなひねりのない解法でも3秒で終わるのが意外でした。