※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。



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 の最小値を求めよ.




解法
http://d.hatena.ne.jp/inamori/20100214/p2
三平方の定理と結びつける解法を攻めてみたけれど効率が悪かった。
効率的な解法を思いつかなかったのでリンク先の解説を参考にコードを記述。
リンク先の考え方は非常にわかりやすい。


is_penta(P):-
	T is floor(sqrt(1+24*P)),
	T*T=:=(1+24*P),
	(T+1) mod 6=:=0.

penta(N,Result):-!,
	Result is (N*(3*N-1))//2.

divs(N,P,N,0):-N mod P>0,!.
divs(N,P,ResultN,ResultC):-
	N1 is N//P,
	divs(N1,P,ResultN,ReC),
	ResultC is ReC+1.

count_fact(N,P,[[N,1]]):-
	N<P*P,
	N>1,
	!.
count_fact(N,P,[]):-
	N<P*P,
	!.

count_fact(N,P,[[P,C]|Result]):-
	N mod P=:=0,
	!,
	divs(N,P,N1,C),
	P1 is P+1,
	count_fact(N1,P1,Result).
count_fact(N,P,Result):-
	!,
	P1 is P+1,
	count_fact(N,P1,Result).

union_sum([],[],[]):-!.
union_sum(Xs,[],Xs):-!.
union_sum([],Ys,Ys):-!.
union_sum([[P,C1]|Xs],[[P,C2]|Ys],[[P,C3]|Result]):-
	!,
	C3 is C1+C2,
	union_sum(Xs,Ys,Result).
union_sum([[P1,C1]|Xs],[[P2,C2]|Ys],[[P1,C1]|Result]):-
	P1<P2,
	!,
	union_sum(Xs,[[P2,C2]|Ys],Result).
union_sum(Xs,[[P2,C2]|Ys],[[P2,C2]|Result]):-
	!,
	union_sum(Xs,Ys,Result).

yakusu([],Num,Num):-!.
yakusu([[P,C]|Rest],Num,Result):-
	between(0,C,R),
	Num1 is Num*(P^R),
	yakusu(Rest,Num1,Result).

search2(P,[Pj,Pk]):-
	count_fact(P,2,Fact1),
	P1 is 3*P-1,
	count_fact(P1,2,Fact2),
	union_sum(Fact1,Fact2,Fact3),
	yakusu(Fact3,1,Y1),
	Y2 is (P*(3*P-1))//Y1,
	T1 is 3*Y1+Y2+1,
	T1 mod 6=:=0,
	J is T1//6,
	J>0,
	S1 is -3*Y1+Y2+1,
	S1 mod 6=:=0,
 	K is S1 //6,
	K>0,
	J>K,
	penta(J,Pj),
	penta(K,Pk).


search(P,Result):-
	search2(P,[Pj,Pk]),
	PA is Pj+Pk,
	is_penta(PA),
	penta(P,Result),
	!.

search(P,Result):-
	P1 is P+1,
	search(P1,Result).