「prolog勉強プロジェクトオイラー71～80」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ。
問い71
http://projecteuler.net/problem=71
ファレイ数列の定義そのままです。
ファレイ数列が隙間を埋めていくというのは分かりますが、出てくる数字が既約というのは何だか不思議。
整数論は初歩の話でも面白いことがおおいですね、私の性根はこういう初等的な数学の話を知ることが好きなおとなしい人間だったりします。
farey(U0,D0,_,D1):-
T is D0+D1,
T>=1000000,
!,
write([U0,D0]).
farey(U0,D0,U1,D1):-
U2 is U0+U1,
D2 is D0+D1,
farey(U2,D2,U1,D1).
main71:-
farey(2,5,3,7).
*問い72 Counting fractions
この問題は一番素朴な方法は試し割でPhi関数を実装、これで十分早くメモリ使用量も抑えられます。
試し割は無駄な処理が入りますが試し割の無駄を省こうとすると素数リストが必要となり素数リスト関係の計算コストやメモリ使用量が上がります。
整数論に通じてない素朴な身としては試し割が一番シンプルでいいという結論になってしまいました。
なにやら高速に計算する関数があるようですが原理がよくわからないので飛ばしています。
is_prime(N):-
between(2,N,N1),
N2 is N1*N1,
(N<N2->!,true;
0=:=N mod N1,!,fail).
prime_list(N):-between(2,1100,N),is_prime(N).
calc(1000000,Ans,_):-!,write(Ans).
calc(N,Ans,Ps):-N1 is N+1,
calc_phi(N,Phi,Ps),
Ans1 is Ans + Phi,
calc(N1,Ans1,Ps).
main72:-findall(N,prime_list(N),Ps),
calc(1,0,Ps).
div(N,P,Result):-0=:=N mod P,!, N1 is N//P,div(N1,P,Result).
div(N,_,N):-!.
calc_phi(N,Result,[P|_]):-
P2 is P*P,
N<P2,
!,
(N>1 ->
Result is N-1;
Result is 1).
calc_phi(N,Result,[P|Ps]):-!,
div(N,P,N1),
calc_phi(N1,Re,Ps),
(N>N1->
Result is Re*(N//(N1*P))*(P-1);
Result is Re).
*問い73
遅いけどファレイ数列でとりあえず解。
もちょっとましな方法はありそう。
calc(D0,D1,_):-
D2 is D0+D1,
D2>12000,!,fail.
calc(D0,D1,D2):-
D2 is D0+D1.
calc(D0,D1,D3):-
D2 is D0+D1,
calc(D0,D2,D3).
calc(D0,D1,D3):-
D2 is D0+D1,
calc(D2,D1,D3).
test:-findall(N,calc(3,2,N),List),length(List,Len),write(Len).
プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ。
問い71
http://projecteuler.net/problem=71
ファレイ数列の定義そのままです。
ファレイ数列が隙間を埋めていくというのは分かりますが、出てくる数字が既約というのは何だか不思議。
整数論は初歩の話でも面白いことがおおいですね、私の性根はこういう初等的な数学の話を知ることが好きなおとなしい人間だったりします。
farey(U0,D0,_,D1):-
T is D0+D1,
T>=1000000,
!,
write([U0,D0]).
farey(U0,D0,U1,D1):-
U2 is U0+U1,
D2 is D0+D1,
farey(U2,D2,U1,D1).
main71:-
farey(2,5,3,7).
*問い72 Counting fractions
この問題は一番素朴な方法は試し割でPhi関数を実装、これだと遅いですがメモリ使用量は抑えられますしまあいいかなと。
試し割は無駄な処理が入りますが試し割の無駄を省こうとすると素数リストが必要となり素数リスト関係の計算コストやメモリ使用量が上がります。
整数論に通じてない素朴な身としては試し割が一番シンプルでいいという結論になってしまいました。
なにやら高速に計算する関数があるようですが原理がよくわからないので飛ばしています。
is_prime(N):-
between(2,N,N1),
N2 is N1*N1,
(N<N2->!,true;
0=:=N mod N1,!,fail).
prime_list(N):-between(2,1100,N),is_prime(N).
calc(1000000,Ans,_):-!,write(Ans).
calc(N,Ans,Ps):-N1 is N+1,
calc_phi(N,Phi,Ps),
Ans1 is Ans + Phi,
calc(N1,Ans1,Ps).
main72:-findall(N,prime_list(N),Ps),
calc(1,0,Ps).
div(N,P,Result):-0=:=N mod P,!, N1 is N//P,div(N1,P,Result).
div(N,_,N):-!.
calc_phi(N,Result,[P|_]):-
P2 is P*P,
N<P2,
!,
(N>1 ->
Result is N-1;
Result is 1).
calc_phi(N,Result,[P|Ps]):-!,
div(N,P,N1),
calc_phi(N1,Re,Ps),
(N>N1->
Result is Re*(N//(N1*P))*(P-1);
Result is Re).
*問い73
遅いけどファレイ数列でとりあえず解。
もちょっとましな方法はありそう。
calc(D0,D1,_):-
D2 is D0+D1,
D2>12000,!,fail.
calc(D0,D1,D2):-
D2 is D0+D1.
calc(D0,D1,D3):-
D2 is D0+D1,
calc(D0,D2,D3).
calc(D0,D1,D3):-
D2 is D0+D1,
calc(D2,D1,D3).
test:-findall(N,calc(3,2,N),List),length(List,Len),write(Len).
