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

「プロジェクトオイラー問30」の編集履歴(バックアップ)一覧はこちら

プロジェクトオイラー問30」の最新版変更点

追加された行は青色になります。

削除された行は赤色になります。

 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までを含んだ数を重複なく反辞書順に6個並べたリストを1セットとしてこれを5005個生成します。
 このリストの5乗和を計算し、その数を各桁のリストに戻し辞書順に並べリストをリバースします。
 リバースしたものとリストが同じになればそれの5乗和は答えの一つです。
 そうすると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]).