Problem 44 「五角数」 † 五角数は Pn = n(3n-1)/2 で生成される. 最初の10項は 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ... である. P4 + P7 = 22 + 70 = 92 = P8 である. しかし差 70 - 22 = 48 は五角数ではない. 五角数のペア Pj と Pk について, 差と和が五角数になるものを考える. 差を D = |Pk - Pj| と書く. 差 D の最小値を求めよ. 解法 5角数のM個めAとM個めまでの5角数の一つ一つをEとして A+EとA-Eが5角数ならそれを暫定の答えとする。 見つかっても見つからなくてもAを数列の次の数にして同じことを繰り返す。 A-Aの3つ前が見つかっている最小差分以上になれば計算停止。 5角数の値を直接取り扱わず差分だけの世界で計算すると早くなりそうなのですが。 ちょっと考え付かない状態です。 penta(N,N5):-N5 is (N*(3*N-1))//2. is_penta(N5):- A is 24*N5+1, B is floor(sqrt(A)), A=:=B^2, (B + 1) mod 6=:=0. calc_stop(0,_,_):-!. calc_stop(_,_,-1):-!,fail. calc_stop(N,M5,NowMin):- !, penta(N,N5), D is M5-N5, D>=NowMin. loop2(N,M5,NowMin,NowMin):- calc_stop(N,M5,NowMin), !. loop2(N,M5,_,Result):- penta(N,N5), M5AddN5 is M5+N5, is_penta(M5AddN5), M5DellN5 is M5-N5, is_penta(M5DellN5), !, Result is M5DellN5. loop2(N,M5,NowMin,Result):- !, N1 is N-1, loop2(N1,M5,NowMin,Result). loop1(M,NowMin,NowMin):- M>3, NowMin > -1, M1 is M-3, penta(M, MA), penta(M1,MB), MA-MB>=NowMin, !, write([M,MA]). loop1(M,NowMin,Result):- !, N is M-1, penta(M,M5), loop2(N,M5,NowMin,NowMin1), M1 is M+1, loop1(M1,NowMin1,Result). main44:- loop1(2,-1,Ans), write(Ans).