「prolog勉強プロジェクトオイラー131～140」の編集履歴（バックアップ）一覧に戻る

prolog勉強プロジェクトオイラー131～140 - (2013/11/13 (水) 15:55:56) のソース

*Problem 139 「ピタゴラスタイル」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20139
ピタゴラス数を題材にした問題。
詳細はリンク先を参照のこと。
問２００くらいまでは結構普通に溶ける問題が多いと思うのでそこまではコードを掲載。
それ以上の問題は今後解き方や考え方だけ掲載しようと思ってる。


解法
取り合えず答えが見たかったので、Wikiに書いてある通りの原始ピタゴラス数の求め方で全探索。
取り立てて遅いというわけではないが工夫すれば答えは一瞬で出そうな気もする。
出てきた答えは不思議で単純な関係があったのでなぜこれが成り立つか考えてみる。
まずは(m^2+n^2) mod (m^2-n^2-2mn)=0
これを満たすｍ、ｎを考えるとよさそうである？
m^2+n^2=k(m-n)^2
m^2+n^2のｍとｎをまたピタゴラス数と考えて再帰的な視点で分析してみる。
A　m=e^2-f^2
B　n=2ef
C　(m^2+n^2)=k(m^2-n^2-2mn)
という式を立てると？



 sum([],0):-!.
 sum([[_,_,_,Perm]|Xs],Result):-sum(Xs,Re),Result is Re+Perm.
 
 gcd(0, B, B).
 gcd(A, B, G) :- A > 0, R is B mod A, gcd(R, A, G).
 
 big_swap(A,B,A,B):-A=<B,!.
 big_swap(A,B,B,A):-!.
 
 over(M,N):-
 	Z is 2*M*(M+N),
 	(Z>=10^8;M=<N).
 
 
 
 calc(M,N,[A1,B1,C1,Perm]):-
 	gcd(M,N,1),
 	1=:=(M-N) mod 2,
 	A  is M^2-N^2,
 	B  is 2*M*N,
 	C1 is M^2+N^2,
 	big_swap(A,B,A1,B1),
 	Sa is B1-A1,
 	0=:= C1 mod Sa,
 	All is A1+B1+C1,
 	Perm is (10^8-1)//All.
 
 
 roopN(M,N,_):-
 	over(M,N),!,fail.
 roopN(M,N,Result):-
 	calc(M,N,Result).
 roopN(M,N,Result):-
 	N1 is N+2,
  	roopN(M,N1,Result).
 
 roopM(M,Result):-
 	N is (M mod 2)+1,
 	roopN(M,N,Result).
 roopM(M,Result):-
 	M1 is M+1,
  	not(over(M1,1)),
 	!,
 	roopM(M1,Result).
 
 main139:-findall(Re,roopM(2,Re),ABC),
 	write(ABC),
 	sum(ABC,Ans),write(Ans).