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

プロジェクトオイラー問１２５ - (2014/03/09 (日) 02:11:52) のソース

*Problem 125 「回文数の和」 †
回文数 595 は連続する平方数の和で表すことができるという面白い性質を持つ: 6^2+7^2+8^2+9^2+10^2+11^2+12^2

1000 未満で連続する平方数の和で表せる回文数はちょうど 11 あり, その合計は 4164 である. 正の整数の平方のみをこの問題では扱うため, 1=0^2+1^2 は含めないことに注意せよ.

回文数でありかつ連続する平方数の和で表せる, 10^8 未満のすべての数の合計を求めよ.



解法
とりあえず地道に計算しても求まります。
たぶんこの問題双曲線上の整数解を求めるもっと高度な解法がありそうです。
 
 
 is_palindromic(N):-
 	N>0,
 	number_codes(N,Codes),
 	reverse(Codes,Codes).
 
 search2(Sum,_,_):-Sum>=10^8,!,fail.
 search2(Sum,_,Sum):-
 	is_palindromic(Sum).
 search2(Sum,N,Result):-
	!,
 	Sum1 is Sum+N*N,
 	N1 is N+1,
 	search2(Sum1,N1,Result).
 
 search(Result):-
 	between(1,8000,N),
 	N2 is N+2,
 	N22 is N^2+(N+1)^2,
 	search2(N22,N2,Result).
 sum([],0):-!.
 sum([X|Xs],Result):-
 	!,
 	sum(Xs,Re),
 	Result is Re+X.
 
 main125:-
 	findall(N,search(N),List),
 	sort(List,List1),
 	sum(List1,Ans),
 	write(Ans).