【Project Euler】Problem 44: 五角数

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

問題 44. 五角数

原文 Problem 44: Pentagon numbers

問題の要約：2つの五角数$P_j$,$P_k$のその和と差がやはり五角数になるものでその$D=|P_k-P_j|$が最小となる$D$を求めよ

五角数は五角数(Wikipedia)によると、一般項は以下の式で表され、逆関数は2番目の式になります。

\begin{align}
P_n &= n(3n-1)/2 \\

n &= (1 \pm \sqrt{1+24P_n})/6
\end{align}

これをもとに$D=|P_k-P_j|$が最小ということなのでjを小さい順、kを大きい順に探して最初に見つかったものを答えとしました。、

import itertools
def Pt(n):
  return n*(3*n-1)//2
def isPt(x):
	f = (1 + (1+24*x)**(1/2))/6
	return f - int(f) == 0
  
def search():
  for k in itertools.count(1):
    for j in range(k,0,-1):
      if isPt(Pt(k)-Pt(j)): 
        if isPt(Pt(k)+Pt(j)):
          print(j, k, Pt(j),Pt(k),Pt(k)-Pt(j), Pt(k)+Pt(j))
          return Pt(k)-Pt(j)

print(f"Answer: {search()}") 

（開発環境：Google Colab）