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)

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

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

◇　　　　　　◇　　　　　　◇

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

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 組ありました。

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

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

　演算回数＝所要時間＝候補 が 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 組のピタゴラス数が表示されて、その最後の行は

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

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

◇　　　　　　◇　　　　　　◇

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