プロジェクトオイラー Problem 74 「桁の階乗による連鎖」 †

Problem 74 「桁の階乗による連鎖」 †

145は各桁の階乗の和が145と自分自身に一致することで有名である.

1! + 4! + 5! = 1 + 24 + 120 = 145

169の性質はあまり知られていない. これは169に戻る数の中で最長の列を成す. このように他の数を経て自分自身に戻るループは3つしか存在しない.

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

どのような数からスタートしてもループに入ることが示せる.

例を見てみよう.

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

69から始めた場合, 列は5つの循環しない項を持つ. また100万未満の数から始めた場合最長の循環しない項は60個であることが知られている.

100万未満の数から開始する列の中で, 60個の循環しない項を持つものはいくつあるか?

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

解法
数字の中身を辞書順に並べ変えたものを一纏めにして検討します。
3345,3354,3435,3453,3534,3543,4335,4353,4533,5334,5343,5433,
などは全部次の数が同じになります。

ということでこれを辞書順の3345で代表させて長さを調べます。
辞書順で昇順になってるものだけ生成してから検討します。

最後に長さ60であることが判明したら、それの並べ替え数を計算して集計してアセプトです。
昇順なら20000個程度の数字を検討するだけで答えが出ます。





コード実行結果
100万までの場合
10 ?- time(main74).
402
% 17,362,257 inferences, 2.500 CPU in 2.494 seconds (100% CPU, 6944903 Lips)


1000万までの場合
11 ?- time(main74).
11322
% 43,154,394 inferences, 6.281 CPU in 6.281 seconds (100% CPU, 6870351 Lips)

メモ化のための配列や木を使ってないことを考えたらまあまあの速度だと思います。









以下この問いのＰｒｏｌｏｇ言語による記述


sum([],0):-!.
sum([X|Xs],Result):-
      !,
      sum(Xs,Re),
      Result is Re+X.

to_num([],[]):-!.
to_num([X|Xs],[Y|Result]):-
      !,
      Y is X-48,
      to_num(Xs,Result).

fact(0,1):-!.
fact(N,Result):-
      !,
      N1 is N-1,
      fact(N1,Re),
      Result is Re*N.

factC(48,1):-!.
factC(N,Result):-
      !,
      N1 is N-1,
      factC(N1,Re),
      Result is Re*(N-48).

calc_next(List,Result):-
      findall(F,(member(E,List),factC(E,F)),List1),
      sum(List1,Num),
      number_codes(Num,Result).



count([],[N,Count],[[N,Count]]):-!.
count([N|Rest],[N,Count],Result):-
      !,
      Count1 is Count+1,
      count(Rest,[N,Count1],Result).
count([N|Rest],[N1,Count],[[N1,Count]|Result]):-
      !,
      count(Rest,[N,1],Result).

count_w([Top|List],Result):-
      count(List,[Top,1],Result).

calc_perm3([],Perm,Perm):-!.
calc_perm3([[_,X]|Xs],Perm,Result):-
      !,
      fact(X,F),
      Perm1 is Perm//F,
      calc_perm3(Xs,Perm1,Result).

calc_perm2(Counts,AllPerm,Result):-
      between(1,9,N),
      select([N,Count],Counts,Counts1),
      Count1 is Count-1,
      calc_perm3([[N,Count1]|Counts1],AllPerm,Result)
      .


calc_perm(List,Result):-
      !,
      length(List,Len),
      Len1 is Len-1,
      fact(Len1,AllPerm),
      to_num(List,List1),
      count_w(List1,Counts),
      findall(P,calc_perm2(Counts,AllPerm,P),Perms),
      sum(Perms,Result).

seed(_,48,6):-!,fail.
seed([],_,6):-!.
seed([],Down,Keta):-Keta>0,Down>48.
seed([Down1|Result],Down,Keta):-
      !,
      between(Down,57,Down1),
      Keta1 is Keta+1,
      seed(Result,Down1,Keta1).

calc(List,Len,Old):-
      number_codes(Num,List),
      member(Num,Old),
      !,
      Len=:=60.
calc(List,Len,[_,Old2,Old3]):-
      !,
      number_codes(Num,List),
      Len1 is Len+1,
      calc_next(List,List1),
      calc(List1,Len1,[Old2,Old3,Num]).


search(Perm):-
      seed(List,48,0),
      calc(List,0,[-1,-1,-1]),
      calc_perm(List,Perm).

main74:-
      findall(E,search(E),List),
      sum(List,Sum),
      write(Sum).