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

プロジェクトオイラー問３０ - (2014/02/14 (金) 10:11:43) のソース

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

*Problem 30 「各桁の5乗」 †
驚くべきことに, 各桁を4乗した数の和が元の数と一致する数は3つしかない.

1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4
ただし, 1=14は含まないものとする. この数たちの和は 1634 + 8208 + 9474 = 19316 である.


各桁を5乗した数の和が元の数と一致するような数の総和を求めよ.



解法
9^5*7<1000000以下なので7桁以上は検討する必要がありません。
0～9までを含んだ数を重複なく反辞書順に６個並べたリストを１セットとしてこれを5005個生成します。
このリストの５乗和を計算し、その数を各桁のリストに戻し辞書順に並べリストをリバースします。
リバースしたものとリストが同じになればそれの５乗和は答えの一つです。
そうするとBigO（5005）の定数倍で処理が完了します。
msortが少しもったいないかもしれません。

 perm(X,_,6,X):-!.
 perm(X,P,Keta,Result):-
 	Keta1 is Keta+1,
 	perm([P|X],P,Keta1,Result).
 perm(X,P,Keta,Result):-
 	P<9,
 	P1 is P+1,
 	perm(X,P1,Keta,Result).
 to5([],0):-!.
 to5([X|Xs],Result):-
 	to5(Xs,Re),
 	Result is Re+X^5.
 
 numToList(_,6,[]):-!.
 numToList(N,Keta,[X|Xs]):-
 	!,
 	N1 is N//10,
  	X  is N mod 10,
 	Keta1 is Keta+1,
 	numToList(N1,Keta1,Xs).
 
 all_check(Perms,Num):-
 	member(Perm,Perms),
 	to5(Perm,Num),
  	numToList(Num,0,List),
 	Num>1,
 	msort(List,List1),
 	reverse(List1,List2),
 	List2==Perm.
 sum([],0):-!.
 sum([X|Xs],Result):-
  	sum(Xs,Re),
 	Result is Re+X.
 
 main30:-
 	findall(P,perm([],0,0,P),Perms),
 	length(Perms,Len),
 	write([datesize,Len]),
 	findall(Num,all_check(Perms,Num),Nums),
  	write(Nums),
 	sum(Nums,Ans),
 	write([ans,Ans]).