project euler 9 解説

1000のピタゴラス数

ピタゴラス数とは、 互いに素な自然数が

a² + b² = c² を満たす数の組である。

このとき,

a + b + c = 1000

となるような組み合わせを求めよ、(このabcの積を求めよ)というのが問いである。

解説

まずピタゴラス数にどんなものがあるかを考える。

例えば、

3,4,5 という組み合わせである。これは

3² + 4² = 9 + 16 = 25 = 5²

となることから明白である。

他にも、 5, 12, 13 という組み合わせなどがある。

では具体的にどういう手法で求めるかというと

整数 m, n ( m > n > 0 ) があるとき、

(m²-n², 2mn, m²+n²) はピタゴラス数になるという定理がある。これをこのブログの中ではピタゴラス式と呼称する。(正式な名前を知りません)

ということは、 a + b + c = 1000 にそれぞれ代入して２次方程式を解けばよい。

m² - n² + 2mn + m² + n² = 1000

2 m² + 2mn = 1000

m² + mn = 500

√500 > m > n ということがわかる(m > n > 0 より)

√500 はだいたい22なので、それ以下の数字で考える。

平方根の計算ができなくても、25² = 625からそれよりは小さいと考える。

というわけで、mに20を代入してみる。

400 + 20n = 500

となり、n=5 で成り立つ

m = 20, n = 5 で成り立つことがわかった。

そこで、ピタゴラス式に当てはめ、

m² - n² = 375

2mn = 200

m² + n² = 425

つまり、

a=200, b = 375, c = 425, abc = 31875000

多分もっとスマートなやり方もある。とりあえず臨時で友人に説明する用

おわりだよ〜

---

追記(2019/3/13 22:36)

ひどくない？