- 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。
問題 39. 整数の直角三角形
原文 Problem 39: Integer right triangles
問題の要約：整数の直角三角形の周囲の和pとするとp<1000で最も多いpを求めよ
整数の直角三角形すなわちピタゴラス数の生成は「Problem 9: 特別なピタゴラス数」で作ったpythを使います。生成された基本ピタゴラス数の周囲の和pの1000以下の倍数をすべて配列に入れ、これをCounterに入力して数えて最も多いものをmost_commonメソッドで取り出します。ただし要注意なのはpythは必ずしも周囲の和pの小さい順には生成しないのでp=1000で止めると、その後に1000より小さいものが出てくる可能性があるということです。
from collections import Counter
N, p, peris = 1000, 0, []
pgen = pyth()
while p < N*2: # need up to twice of the bound
p = sum(next(pgen))
for i in range(1,(N//p)+1): # Multiples up to N
peris.append(p*i)
print(f"Answer: {Counter(peris).most_common()[0][0]}") # extract most common number
そこでpをいくつまで生成すればいいか考えてみました。
pythでpを$10^6$まで生成して、p以前のの最大値pmaxとの比率p/pmaxの最小値rを求めます。数が大きくなっていくと0.5に収束していくようです。したがって1000以下のpをすべて生成するためには2倍の2000になるまでという条件で良さそうです。たぶん証明すれば出来るのでしょうが、誰か出来たら教えてください。
pgen = pyth()
p, pmax, r = 0, 1, 1
while p < 10**6:
p = sum(next(pgen))
if p>pmax: pmax=p
if (p/pmax) < r: r = (p/pmax)
print(f"Minimum s/smax ratio = {r}")
#Minimum s/smax ratio = 0.5035145516710452
（開発環境：Google Colab）