「プロジェクトオイラー解説問9」の編集履歴(バックアップ)一覧に戻る

プロジェクトオイラー解説問9 - (2014/01/09 (木) 16:23:36) のソース

*Problem 9 「特別なピタゴラス数」 †
ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a < b < c で以下の式を満たす数の組である.

a^2 + b^2 = c^2
例えば, 3^2 + 4^2 = 9 + 16 = 25 = 5^2 である.

a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
これらの積 abc を計算しなさい.


----
**解法
ピタゴラス数の3つ組は原始ピタゴラス数という概念によって計算されます。
m,nは自然数で互いに素,m-nが奇数でm>nである時
a^2+b^2=c^2として。
- a=m^2-n^2
- b=2mn
- c=m^2+n^2
という関係式であらわされます。
実はa^2+b^2=c^2をみたす整数組(a,b,c)は
k(m^2-n^2)+k(2mn)=k(m^2+n^2)
ですべての(a,b,c)を表現できるのです。
kの意味は
(a,b,c)=(3,4,5)
(a,b,c)=(6,8,10) k=2の場合
(a,b,c)=(9,12,15) k=3の場合
,,,
と直角三角形をk倍に相似拡大することに当たります。
m,nで表現されるのは整数比であらわされる一番小さい異質な直角三角形を生成します。

(a,b,c)=(3,4,5)を相似縮小すると整数比が保てませんね。
これがk倍のもととなるので原始というわけです。


よって,m、nを小さいほうからためします。
a+b+cが1000を超えない。
つまり
a+b+c=(m^2-n^2)+2mn+(m^2+n^2)
これはm、nが大きくなると1000を超えてしまうのでa+b+cが1000以下の個数は有限です。

このすべてを検討しそのk倍が1000を超えないものもすべて検討します。
a+b+cが1000になるものあればそれが答えです。

原始ピタゴラス数に関する話はネットやWikiにたくさん資料があるので。
詳細な話は検索してください。