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


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