ピタゴラス数

よく知られているように、直角三角形の斜辺の長さをc、他の2辺の長さをabとすると、

a2 + b2 = c2

これがピタゴラスの定理です。
この辺の長さが自然数のとき、辺の長さの組をピタゴラス数(Pythagorean triple)と呼びます。また、辺の長さが互いに素であるとき、原始ピタゴラス数(primitive Pythagorean triple)と呼びます。例えば、(3, 4, 5)は原始ピタゴラス数ですが、(6, 8, 10)は原始ピタゴラス数ではありません。


原始ピタゴラス数の求め方は、よく使われるテクニックですので、解説します。

a2 + b2 = c2

の両辺をc2で割り、a / c -> x, b / c -> yと置き換えると、

x2 + y2 = 1

となります。これは単位円を表します。この単位円上の有理数座標の点を求めればいいわけです(第1象限だけでよい)。

上は、(0, 1)から傾き-k(0 < k < 1)で直線を引っ張った図です。この直線と単位円の(0, 1)以外の交点が有理数なら、k有理数になります。逆に、k有理数だとすると、

y = -kx + 1

を単位円を表す式に代入して、

 x = \frac{2k}{1 + k^2} \quad y = \frac{1 - k^2}{1 + k^2}

有理数になります。k = n / mと置き換えると、

 x = \frac{2mn}{m^2 + n^2} \quad y = \frac{m^2 - n^2}{m^2 + n^2}

分母を払うと、

a = 2mn b = m2 - n2 c = m2 + n2

となります。
さて、この組が互いに素なる条件を考えましょう。m,nが互いに素でないならa,b,cも互いに素でないですが、裏は成り立ちません。aの式に2がついているからです。ですから、m,nが偶奇で場合分けをします。

m n m2-n2 m2+n2
偶数 偶数 偶数 偶数
偶数 奇数 奇数 奇数
奇数 偶数 奇数 奇数
奇数 奇数 偶数 偶数

m + nが奇数になればいいことがわかります。
結局、ピタゴラス数は次のように表されます。

a = 2lmn b = l(m2 - n2) c = l(m2 + n2)
m > n
mnは互いに素
m + nは奇数

最後に周囲の長さが100以下のピタゴラス数を列挙しましょう。


from fractions import gcd

def gen_pythagoras(N):
for m in range(2, int((N * 0.5) ** 0.5) + 1):
for n in range(1, m):
if gcd(m, n) != 1:
continue
a = 2 * m * n
b = m * m - n * n
c = m * m + n * n
if a > b:
a, b = b, a
s = a + b + c
for l in range(1, N / s + 1):
yield l * a, l * b, l * c

N = 100
for a, b, c in gen_pythagoras(N):
print a, b, c