prolog勉強プロジェクトオイラー1～10 - c21coterie @ ウィキ

プロジェクトオイラーの問題を堀江伸一こと私がＰｒｏｌｏｇで解くページ。
プロジェクトオイラーの問題は問題番号が小さいものほど簡単で問題番号が大きいものは非常に難しくなります。
この辺は最初なので中学生プログラマでも挑戦できるレベルの問題が並ぶ。

Problem 1 「3と5の倍数」 †

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%201
1000未満の３か５の倍数になっている自然数の合計を答えよ

解法
数式で解くのが正しいけれどサイトの趣旨、数学の問題をプログラムで特に合わせて末尾再帰で記述。

mod_n(N,N):-
	member(R,[3,5]),
	N mod R=:=0,
	!.
mod_n(_,0):-!.

search(1000,Ans):-!,write(Ans).
search(N,Ans):-
	mod_n(N,Add),
	Ans1 is Ans+Add,
	N1 is N+1,
	search(N1,Ans1).

main1:-search(1,0).

problem 2 「偶数のフィボナッチ数」 †

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%202
問題
フィナボッチ数列の項の値が400万より小さい, 偶数値の項の総和を求めよ.

解法
まあ少しくらいの工夫はする。
マクローリン展開を使う方法は私には理解できなかった。

fina(_,_,F,Sum):-F>=4000000,write(Sum),!.
fina(A,B,F,Sum):-B1 is 2*A+3*B,
A1 is F,F1 is A1+2*B1,Sum1 is Sum+F,fina(A1,B1,F1,Sum1).

Problem 3 「最大の素因数」 †

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%203
13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.
解法
√まで求めればいいんだけどまあ小さい値で割り切れることはわかってるので特に気にしない。

soinn(1,N):-write(N),!.
soinn(N,A):-0=:= N mod A,!,N1 is N/A,soinn(N1,A).
soinn(N,A):-A1 is A+1,soinn(N,A1).

Problem 4 「最大の回文積」 †

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%204
左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.

解法
findallを使って手抜き。

kaibunn(C):-
between(100,999,N),
between(100,N,M),
C is N*M,
numrev(C,0,C1),C=:=C1.

main4:-findall(C,kaibunn(C),List),mymax(List,0,Max),write(Max).

Problem 5 「最小の倍数」 †

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%205
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

解法
普遍的に解けるように書いてもよかったのだけど。
手抜きで解いた。
正しくは1～20までの素数のリストを求め、その素数aがa^n<=20となるｎを求めてから計算する。

calc([],[],Ans):-!,write(Ans).
calc([X|Rest],[Y|Rest1],Ans):-Ans1 is Ans*(X^Y),calc(Rest,Rest1,Ans1).
main5:-Powers=[4,2,1,1, 1, 1,1 ,1],
Base =[2,3,5,7,11,13,17,19],
calc(Base,Powers,1).

Problem 6 「二乗和の差」 †

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%206
最初の10個の自然数について, その二乗の和は,
1^2 + 2^2 + ... + 10^2 = 385
最初の10個の自然数について, その和の二乗は,
(1 + 2 + ... + 10)^2 = 3025
これらの数の差は 3025 - 385 = 2640 となる.
同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ.

解法
うーんそのまま素直に実装するのが一番いいコードに思えるんだけど？
なにか賢い解き方があるのかな？
数式一行になるとか？

calc6(SumA,SumB,101):-!,
Ans is SumB*SumB-SumA,write(Ans).
calc6(SumA,SumB,N):-
SumA1 is SumA+N*N,
SumB1 is SumB+N,
N1 is N+1,
calc6(SumA1,SumB1,N1).

Problem 7 「10001番目の素数」 †

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%207
素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10001 番目の素数を求めよ.

解法
素数のリストを伸ばすだけの手抜き実装。
特徴遅い、、、

prime_check([X|Rest],N,[X|Re1],1):-N<X*X,!,append(Rest,[N],Re1).
prime_check([X|Rest],N,[X|Rest],0):-0=:=N mod X,!.
prime_check([X|Rest],N,[X|Result],Add):-prime_check(Rest,N,Result,Add).
search7(_,N,10001):-!,N1 is N-1,write(N1).
search7(PList,N,Count):-
N1 is N+1,
prime_check(PList,N,PList1,Add),
Count1 is Count+Add,
search7(PList1,N1,Count1).

Problem 8 「数字列中の最大の積」 †

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%208
1000桁の数字が与えられるので並んだ５桁の数字の積をとった時最大となる数を答えよ。

解法
Ｎに1000桁の数字を代入してＲｅｓultで答えが返ってくる。
賢い方法ってあるのかしら？

calc8(N,Ans,Ans):-N<10000,!.
calc8(N,Max,Result):-N1 is N mod 10,N2 is (N//10) mod 10,N3 is (N//100) mod 10,
                     N4 is (N//1000) mod 10,N5 is (N//10000) mod 10,
                     Temp is N1*N2*N3*N4*N5,(Max<Temp->Max1 is  Temp;Max1 is Max),NN is N//10,calc8(NN,Max1,Result).

Problem 9 「特別なピタゴラス数」 †

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%209
a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
これらの積 abc を計算しなさい.

解法
1000=k(*1)
を満たすｋ,m,nの組み合わせを見つける問題。
きちんと実装すると計算量は1000回以下になるが、まあ現状の500*24回でもそんなに悪くないと思う・

gcd(M,0,M):-!.
gcd(M,N,Result):-
	N1 is M mod N,
       gcd(N,N1,Result).
main9:-
between(2,24,M),
0=:=500 mod M,
between(1,500,R),
0=:=500 mod R,
Sum is 500 //R,
S is Sum // M,
N is S-M,
N<M,
0<N,
gcd(M,N,Re),
Re=:=1,
1=:=(M-N) mod 2,
A is R*(M*M-N*N),
B is R*2*M*N,
C is R*(M*M+N*N),
write([ans,A,B,C]).

Problem 10 「素数の和」 †

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2010
10以下の素数の和は 2 + 3 + 5 + 7 = 17 である.
200万以下の全ての素数の和を求めよ.

解法
200万以下の素数の合計を返す処理。
末尾再帰なら早くなるかと思ったら意外と速度が出ない。
どこが遅いんだろ？

create_nums(Num):-
	between(2,2000000,Num).
prime_rest(_,[],[]):-!.
prime_rest(P,[X|Rest],Result):-0=:=X mod P,!,prime_rest(P,Rest,Result).
prime_rest(P,[X|Rest],[X|Result]):-prime_rest(P,Rest,Result).

get_prime_list([P|Rest],PList):-P*P>2000000,!,sums(Rest,P,Sum1),sums(PList,Sum1,Sum2),write(Sum2).
get_prime_list([P|Rest],PList):-prime_rest(P,Rest,Rest1), 
get_prime_list(Rest1,[P|PList]).

sums([],Result,Result).
sums([X|Rest],Sum,Result):-Sum1 is Sum+X,sums(Rest,Sum1,Result).

main10:-findall(Num,create_nums(Num),NumList),get_prime_list(NumList,[]).

---

*1 m^2+n^2)+2mn+(m^2-n^2