【Project Euler】Problem 75: 唯一の整数直角三角形

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 75. 唯一の整数直角三角形

原文 Problem 75: Singular integer right triangles

問題の要約：$L \le 15 \times 10^5$の針金を折って各辺が整数の直角三角形を作った時、一通りしかできないような$L$の数を求めよ

例えば120は以下のように3通りの直角三角形が作れます。

120: (30,40,50), (20,48,52), (24,45,51)

まず基本ピタゴラス数の生成ですが「Problem 9: 特別なピタゴラス数」で作ったpythを使います。

後は$15 \times 10^5$の配列を作って基本ピタゴラス数の倍数の数をカウントアップしていき、最後にカウントが1だったものの数を数えます。

また「Problem 39: 整数の直角三角形」でも述べた通りpythは必ずしも$L$の小さい順には生成しないのでnMax*2まで生成する必要があります。

nMax = 15*10**5
numPytha = [0]*(nMax+1)  # count up perimeter of right triangles 
for abc in pyth():
  L = sum(abc)
  if L > nMax*2: break  # need to check twice of max (re: Problem 39)
  for m in itertools.count(1):
    if  L*m > nMax: break
    numPytha[L*m] += 1

print(f"Answer: {numPytha.count(1)}")

（開発環境：Google Colab）