原始ピタゴラス数を捜す
原始ピタゴラス数
数学ガール フェルマーの最終定理 問題２－１ 原始ピタゴラス数は無限に存在するか を検討するため，原始ピタゴラス数を探索するプログラムを書いてみました。
ピタゴラス数とは三平方の定理に出てくる直角三角形の３辺a,b,cがいずれも整数である場合のa,b,cで、原始ピタゴラス数とは，1,b,cの最大公約数が１であるものをいいます。
コード
コードはシンプルです。
ためしに走らせてみるとN=1000で200msぐらい。
先にa,b,cの最大公約数の判定を入れると6670msくらいと非常に時間がかかるのでピタゴラス数かどうかの判定を先にもってきたのは正解です。
N=2000で1515msぐらい。
#include <bits/stdc++.h> using namespace std; int main(){ int N; cin>>N; for(int i=1;i<N;i++){ for(int j=i+1;j<N;j++){ for(int k=j+1;k<N;k++){ if(pow(i,2)+pow(j,2)==pow(k,2)){ if(gcd(gcd(i,j),k) !=1) continue; cout<<i<<" "<<j<<" "<<k<<endl; } } } } return 0; }
出力
出力はこんな感じ。
3 4 5 5 12 13 7 24 25 8 15 17 9 40 41 11 60 61 12 35 37 13 84 85 15 112 113 16 63 65 17 144 145 19 180 181 20 21 29 20 99 101 21 220 221 23 264 265 24 143 145 25 312 313 27 364 365 28 45 53 28 195 197 29 420 421 31 480 481 32 255 257 33 56 65 33 544 545 35 612 613 36 77 85 36 323 325 37 684 685 39 80 89 39 760 761 40 399 401 41 840 841 43 924 925 44 117 125 44 483 485 45 1012 1013 47 1104 1105 48 55 73 48 575 577 49 1200 1201
考察
出力のところをカウント数だけに変えて数えると N=100で16個 N=1000で158個 N=2000で319個 N=3000で477個となりました。
N=3000というと2億通りぐらい判定していますが５秒くらいで計算しちゃうのでコンピューターはすごいなと思います。
前記の計算結果からすると原始ピタゴラス数は無限にありそうです。
更に考察
出力の数字をじっと見ていると，bとcの差が１のものがたくさんあることに気づきました。
a=3 b=4 c=5 a=5 b=12 c=13 a=7 b=24 c=25 a=9 b=40 c=41
更によく見ると、aが奇数の場合、かならずb+1=cである原始ピタゴラス数の組み合わせがあります。
c^2-b^2=a^2
と変形し
(c+b)(c-b)=a^2
としてやると c-b=1の場合
c+b=a^2となります
奇数の二乗を常に、差が１である２つの整数の和で表せる、ということがいえれば原始ピタゴラス数は無数にある，といえそうです。
どうやら解法が見えてきました。
更に先へ
aは奇数なので整数nをつかって2*n+1と表せます。
c+b=a^2の左辺を変形して、
(2*n+1)^2=4*n^2+4*n+1
=4n(n+1)+1
となります。
2n(n+1)をb、2n(n+1)+1をcとすると、奇数の二乗は常に差が１である整数bとcの和で表せます。
奇数は無数にあるので、原始ピタゴラス数も無数にあることが証明できました。
