「プロジェクトオイラー問30」の編集履歴(バックアップ)一覧はこちら
「プロジェクトオイラー問30」(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までを含んだ数を重複なく反辞書順に6個並べたリストを1セットとしてこれを5005個生成します。
このリストの5乗和を計算し、その数を各桁のリストに戻し辞書順に並べリストをリバースします。
リバースしたものとリストが同じになればそれの5乗和は答えの一つです。
そうするとBigO(5005)の定数倍で処理が完了します。
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]).
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]).