人気ブログランキング | 話題のタグを見る

ピタゴラス数の作り方

3*3 + 4*4 = 5*5 のように平方数が自然数になる自然数の組をピタゴラス数という。ピタゴラス数は次の公式で見つけることができる。

(m^2 - n^2)^2 + 4*m^2*n^2 = (m^2 + n^2)^2

上の公式から、(m^2-n^2, 2*m*n, m^2+n^2) の3つ組みがピタゴラス数だ。この m と n に網羅的に自然数を当てはめていけば、ピタゴラス数を列挙することができる。これを Haskell でやってみよう。

まず2つの自然数の組みを網羅的に発生する方法を考える。これは、Haskell の内包的定義を使えば簡単にできる。

Hugs> take 10 [(m, n)| m <- [1..], n <- [1..m]]
[(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)]

これを上の公式に入れてやると、ピタゴラス数らしきものができる。

Hugs> take 10 [(m*m-n*n, 2*m*n, m*m+n*n)| m <- [1..], n <- [1..m]]
[(0,2,2),(3,4,5),(0,8,8),(8,6,10),(5,12,13),(0,18,18),(15,8,17),(12,16,20),(7,24,25),(0,32,32)]

しかし、数値のひとつが0になるものや、互いに素でない3つ組みは除外したいので、filter でふるい落とすことにする。

Hugs> take 10 $ filter (\(x,y,z) -> (gcd (gcd x y) z) == 1) [(m*m - n*n, 2*m*n, m*m+n*n)| m <- [2..], n <- [1..m], m /= n]
[(3,4,5),(5,12,13),(15,8,17),(7,24,25),(21,20,29),(9,40,41),(35,12,37),(11,60,61),(45,28,53),(33,56,65)]

検算してみる。

Hugs> 33*33 + 56*56 - 65*65
0

33, 56, 65 などというピタゴラス数は知らなかったので満足。Haskell は整数論と特に相性がいいようだ。初歩的な数論の問題を Haskell で解くと、Haskell を使いこなすときのコツのようなものを感じることができる。
by tnomura9 | 2011-06-07 07:14 | Haskell | Comments(0)
<< シーザー暗号を作ってみた ユークリッドの互除法 >>