「プロジェクトオイラー問４４」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問４４ - (2014/02/17 (月) 13:31:45) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2044


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).