project euler 44

その他

問題

五角数とはPn=n(3n-1)/2であらわされる数をいう。
あるPk,Pjについて、その和と差が五角数になるもののうち、差D=|Pk-Pj|の最小値を求める。

考え方

五角数の判定は、あるaが五角数ならば3n^2-n-2a=0の解nが整数になるはずなので、n=(1+sqrt(1+24a))/6を求めて、そのnで(小数計算が入るのでn+-1も合わせて)Pn==aになるかで判定した。

五角数の生成は簡単なので、10^5程度生成して、調べる。すると1つ見つかる。
P_{n+1}-P_nがその最小値になる(2*10^6ぐらい)まで回して、それより小さなDがないことを確認。