Python でピタゴラス数を書き出す

　a²＋b²＝c² を満たす自然数 a , b , c の組み合わせを ピタゴラス数 と言います。三角形の３辺の長さ (a,b,c) がこの式を満たすとき、その三角形は直角三角形になります。
　さて、Pythonでプログラムを作って「100以下のピタゴラス数」を全部書き出してみましょう。
　次のように３重ループを作って、a,b,c をそれぞれ 1 から 100 まで回せばとりあえず出てきます。

for a in range(1,100):
   for b in range(1,100):
       for c in range(1,100):
           if a*a+b*b==c*c:
                print(a,b,c)

　でも、このままではいくつかの難点があります。

①　(3,4,5) と順番が違うだけの (4,3,5) が出てくる。（合同な三角形）
②　(3,4,5) の整数倍 (6,8,10) などが出てくる。（相似な三角形）
③　表示される順番が不自然。(13,84,85) の後に (20,21,29) が出てくる。
④　大きい数まで出そうとすると時間がかかりすぎる。

　では、上のプログラムを書き換えて、どれでも良いので、解決してください。どれか１つだけでも良いので、改善してください。

◇　　　　　　◇　　　　　　◇

　①と③を解決するには、次のように書き換えれば良い。演算回数が減る分、多少は時間の節約にもなるでしょう。

for c in range(1,100):
   for b in range(1,c):
       for a in range(1,b):
           if a*a+b*b==c*c:
                print(a,b,c)

　次に②の解決を図りましょう。これがなかなか難しいのですが、頑張ってください。
　次のプログラムでは、ピタゴラス数を表示するのに加えて、小さい順に番号を振りながら、個数を数えました。

count=0
for c in range(1,100):
   for b in range(1,c):
       for a in range(1,b):
           if a*a+b*b==c*c:
               check=1
               for i in range(2,a):
                   if a%i==0 and b%i==0 and c%i==0:
                       check=0
               if check==1:
                   count=count+1
                   print(count,'   ',a,b,c)
print('fin')

　これを実行した結果は、次の通りです。あっという間に表示されます。全部で 16 組ありました。

1　 　3　4　5
2　 　5　12　13
3　 　8　15　17
　　　　　：
15　　39　80　89
16　　65　72　97
fin

　さて「100以下のピタゴラス数」なら上のプログラムですぐに出ますが、もっと大きい数まで、例えば「10,000以下のピタゴラス数」を表示しようとすると、上のプログラムでは時間がかかりすぎます。
　というのは、「○○以下のピタゴラス数」と言うときの○○に入る数がｎ倍になると、a,b,c に入れるパターンがそれぞれｎ倍になりますから、３文字の組み合わせで演算回数は n³ 倍になるのです。
　ですから「1,000まで」を表示するには「100まで」の場合の 10³＝千倍、「10,000まで」を表示するには「100まで」の場合の 100³＝百万倍の時間がかかると、ざっくり言えばそういうことになるわけです。

　それはそうと、上のプログラムのまま「1,000以下のピタゴラス数」を表示させてみたところ、ちょっとしたことに気がつきました、ピタゴラス数が現れる頻度です。「1,000以下のピタゴラス数」は全部で 158 組あったのですが、100ごとに区切って数えると結果は次の通りでした。

 範囲　　　 個数　　 増加分
~ 100 　　　16　　　 16
~ 200 　　　32　 　　16
~ 300 　　　47　 　　15
~ 400 　　　63　 　　16
~ 500 　　　80　 　　17
~ 600 　　　95　 　　15
~ 700 　　　112　　 　17
~ 800 　　　128　　 　16
~ 900 　　　140　 　　12
~ 1000 　　　158　 　　18

　演算回数＝所要時間＝候補 が 2³＝8 倍、3³＝27 倍、4³＝64 倍、… と３乗で増えていくのに、ピタゴラス数の出現回数は２倍、３倍、４倍とほぼ比例しているように見えるんですね。
　となると、俄然「10,000まで」やってみたくなりますね。時短プログラムを作って、うまくいったらついでに「ピタゴラス数の出現頻度」を調べたい。
　というわけで、やってみました。その結果、けっこう短い時間で「10,000まで」表示できて、「100個ごと」に区切って数えて、あわせて Python の勉強のためにグラフ化までやってみました。

import matplotlib.pyplot as plt
n=10000
count=[]
for i in range(int(n/100)):
   count.append(0)
for c in range(1,n):
   for b in range(1,c):
       a=int((c*c-b*b)**(1/2))
       if a<b:
           if a*a+b*b==c*c:
               i=2
               while i<a and (a%i!=0 or b%i!=0 or c%i!=0):
                   i=i+1
               if i==a:
                   j=int(c/100)
                   count[j]=count[j]+1
                   print(a,b,c)
sum=0
for i in range(int(n/100)):
   sum=sum+count[i]
   plt.scatter(i*100,sum)
   print(i*100,'~',(i+1)*100,'　　　',count[i],'   ',sum)
plt.show()

　その結果、全部で 1593 組のピタゴラス数が表示されて、その最後の行は

2772　9605　9997

でした。
　また、上限「100ごと」に区切って数えた「ピタゴラス数の出現頻度」は次の通りで、ほぼ直線状になりました。

　繰り返しますが、「1,000まで」のピタゴラス数を調べるには「100まで」の場合と比べて演算回数≒所要時間は 10³＝千倍もかかるのに、その出現回数はたったの10倍で、「10,000まで」のピタゴラス数を調べるには「100まで」の場合と比べて演算回数≒所要時間は 100³＝百万倍もかかるのに、その出現回数はやっぱり100倍。実際のところ「100まで」で 16 個、「1,000まで」で 158 個、「10,000まで」で 1593 個でした。
　私としては意外な結果なのですが、皆さんはどうお感じでしょうか。

◇　　　　　　◇　　　　　　◇

〜 Python で２重ループ・３重ループ 〜
▷ Python が九九81匹　　　　　　　
▷ Python で素因数分解する　　　　
▷ Python でピタゴラス数を書き出す