プロジェクトオイラー問14

Problem 14 「最長のコラッツ数列」 †

正の整数に以下の式で繰り返し生成する数列を定義する.

n → n/2 (n が偶数)

n → 3n + 1 (n が奇数)

13からはじめるとこの数列は以下のようになる.

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題)

さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか.

注意: 数列の途中で100万以上になってもよい

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

解法

逆向きに考えてみますとNからスタートする場合。

(Ｎ-1) mod 3=0かつA=（Ｎ-1）/３が奇数ならＡから開始したほうが長い数列が得られます。
Ａはさらに小さな数へと向かうといつかは1以下になるので、Ａをご先祖はどこかで１００万以上から来ないといけません。
２で割った数がＡになるわけです。
よってスタート地点となるＮは50万～99万9999となります。

配列があれば手軽にメモ化して計算量を抑えられますがＰｒｏｌｏｇ言語は破壊的代入がないので地道に計算することになります。
Ｐｒｏｌｏｇでメモ化を実現しようとしたらトライ木の実装が必要でコードが膨らみます。



max(A,B,B):-A<B,!.
max(A,_,A):-!.

no_back3(N):-(N-1) mod 3=:=0,N1 is ((N-1)//3),N1 mod 2=:=1,!,fail.
no_back3(_):-!.

collatz(N,N1):-N mod 2=:=0,!,N1 is N//2.
collatz(N,N1):-!,N1 is 3*N+1.

chain(1,Len,Len):-!.
chain(N,Len,Result):-
      !,
      collatz(N,N1),
      Len1 is Len+1,
      chain(N1,Len1,Result).

searchN(1000000,Ans):-!,write(Ans).
searchN(N,[AnsLen,_]):-
      no_back3(N),
      chain(N,1,Len),
      max(AnsLen,Len,AnsLen1),
      AnsLen<AnsLen1,
      !,
      N1 is N+1,
      searchN(N1,[AnsLen1,N]).
searchN(N,Ans):-
      !,
      N1 is N+1,
      searchN(N1,Ans).

main14:-

      searchN(500000,[0,0]).


















実装しやすい形でＴｒｙ木を記述してみた。
が全く速度が出ない。
単なるメモリの無駄になってるのだがどこにコードのミスがあるかよくわからない状態。


max(A,B,B):-A<B,!.
max(A,_,A):-!.

no_back3(N):-(N-1) mod 3=:=0,N1 is ((N-1)//3),N1 mod 2=:=1,!,fail.
no_back3(_):-!.

collatz(N,N1):-N mod 2=:=0,!,N1 is N//2.
collatz(N,N1):-!,N1 is 3*N+1.

chain(Tree,N,Len,Tree):-
      search_try_w(Tree,N,Len),
      -1<Len,
      !.
chain(Tree,N,ReLen1,ReTree1):-
      !,
      collatz(N,N1),
      chain(Tree,N1,ReLen,ReTree),
      ReLen1 is ReLen+1,
      updata_try_w(ReTree,N,ReLen1,ReTree1).

searchN(_,1000000,Ans):-!,write(Ans).
searchN(Tree,N,Ans):-
      not(no_back3(N)),
      !,
      N1 is N+1,
      searchN(Tree,N1,Ans).

searchN(Tree,N,[AnsLen,AnsN]):-
      !,
      chain(Tree,N,Len,Tree1),
      max(AnsLen,Len,AnsLen1),
      (AnsLen < AnsLen1 -> AnsN1 is N;AnsN1 is AnsN),
      N1 is N+1,
      searchN(Tree1,N1,[AnsLen1,AnsN1]).


updata_e(0,Add,[_|Rest],[Add|Rest]):-!.
updata_e(N,Add,[E|Rest],[E|Result]):-
      !,
      N1 is N-1,
      updata_e(N1,Add,Rest,Result).

search_try(Val,_,Val):-
      integer(Val),
      !.
search_try(Tree,[],Result):-
      !,
      nth0(0,Tree,Tree1),
      search_try(Tree1,[],Result).
search_try(Tree,[X|Xs],Result):-
      !,
      P is X-48,
      nth0(P,Tree,Tree1),
      search_try(Tree1,Xs,Result).

search_try_w(_,N,-1):-
      1000000 =< N,
      !.
search_try_w(Tree,N,Result):-
      !,
      number_codes(N,List),
      reverse(List,List1),
      search_try(Tree,List1,Result).

updata_try(Val,_,Len,Len):-integer(Val),!.
updata_try([Top|Tree],[],Len,[Result|Tree]):-
      !,
      updata_try(Top,[],Len,Result).
updata_try(Tree,[X|Xs],Len,Result):-
      !,
      P is X-48,
      nth0(P,Tree,Tree1),
      updata_try(Tree1,Xs,Len,Re),
      updata_e(P,Re,Tree,Result).

updata_try_w(Tree,N,_,Tree):-
      1000000=<N,
      !.

updata_try_w(Tree,N,Len,Result):-
      !,
      number_codes(N,List),
      reverse(List,List1),
      updata_try(Tree,List1,Len,Result).


creata_try(6,-1):-
      !,
      between(0,9,_).
creata_try(Keta,Result):-
      Keta1 is Keta+1,
      between(0,9,_),
      findall(Re,creata_try(Keta1,Re),Result).

main14:-
      findall(R,creata_try(1,R),Tree),
      updata_try_w(Tree,1,1,Tree1),

      searchN(Tree1,500000,[0,0]).