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

プロジェクトオイラー問45 - (2014/02/15 (土) 20:52:33) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?Problem%2045#xd23edb5
*Problem 45 「三角数, 五角数, 六角数」 †
三角数, 五角数, 六角数は以下のように生成される.

三角数	Tn=n(n+1)/2	1, 3, 6, 10, 15, ...
五角数	Pn=n(3n-1)/2	1, 5, 12, 22, 35, ...
六角数	Hn=n(2n-1)	1, 6, 15, 28, 45, ...
T285 = P165 = H143 = 40755であることが分かる.

次の三角数かつ五角数かつ六角数な数を求めよ.





解法
5角数の数列P番目
6角数の数列H番目として
P番目のほうがH番目より小さいならPをP+1にインクリメント。
P番目のほうがH番目より大きいならHをH+1にインクリメント。
P番目とH番目が同じならそれが答え。
6角数は3角数の部分なので6角数だけ検査する。

Hを144 P166を初期値として探索を行う。
計算量は60000回くらい。

 hex(N,Result):-
 	Result is N*(2*N-1).
 penta(N,Result):-
 	Result is (N*(3*N-1))//2.
 
 search(H,P,H1):-
 	hex(H,H1),
 	penta(P,P1),
 	H1=:=P1,
 	!.
 search(H,P,Result):-
 	hex(H,H1),
  	penta(P,P1),
 	H1<P1,
 	!,
 	H2 is H+1,
 	search(H2,P,Result).
 search(H,P,Result):-
 	P1 is P+1,
 	search(H,P1,Result).
 main45:-
 	search(144,166,Ans),
 	write(Ans).