「プロジェクトオイラー問139」の編集履歴（バックアップ）一覧はこちら
「プロジェクトオイラー問139」(2015/02/12 (木) 21:23:18) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20139
直角三角形を4つ集めて真ん中に正方形を作る問題
解法
三角形の直角をなす2辺をa,b,斜辺をｃとすると。
中にできる四角形はd=abs(a-b)
これがｃ mod d=0となればそれは条件を満たす。
ところで原始ピタゴラス数がこの条件を満たせばそのｋ倍もこの問題の条件を満たす。
満たさなければｋ倍も条件を満たさない。
後は力づく。
最新のパソコンで40秒も計算時間がかかる。
ところで真ん中の正方形の面積はｃ＾２-4ab/2と小学生な計算も可能。
こちらからのアプローチもできそうなんだけど式を見ててもよくわからない。
40秒は明らかに遅いのでもう少し何とかならないかと思う。
stopM(M):-stopMN(M,1).
stopMN(M,N):-L is 2*M*(M+N),10^8=<L.
gcd(0, B, G) :- G is abs(B).
gcd(A, B, G) :- A =\= 0, R is B mod A, gcd(R, A, G).
loopN(M,K):-
between(1,M,N),
(stopMN(M,N)->!,fail;true),
1=:=(M-N) mod 2,
gcd(M,N,G),
G=:=1,
L is 2*M*(M+N),
C is M*M+N*N,
A is M*M-N*N,
B is 2*M*N,
D is abs(A-B),
C mod D=:=0,
K is (10^8-1)//L.
loopM(K):-
between(1,10000,M),
(stopM(M)->!,fail;loopN(M,K)).
sum([],Sum,Sum):-!.
sum([E|Es],Sum,Result):-
Sum1 is Sum+E,
sum(Es,Sum1,Result).
main:-
findall(E,loopM(E),Es),
write(Es),
sum(Es,0,Ans),
write(Ans).
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20139
直角三角形を4つ集めて真ん中に正方形を作る問題
解法
三角形の直角をなす2辺をa,b,斜辺をｃとすると。
中にできる四角形はd=abs(a-b)
これがｃ mod d=0となればそれは条件を満たす。
ところで原始ピタゴラス数がこの条件を満たせばそのｋ倍もこの問題の条件を満たす。
満たさなければｋ倍も条件を満たさない。
後は原始ピタゴラス数を力づくで全検証。
最新のパソコンで40秒も計算時間がかかる。
ところで真ん中の正方形の面積はｃ＾２-4ab/2と小学生な計算も可能。
こちらからのアプローチもできそうなんだけど式を見ててもよくわからない。
40秒は明らかに遅いのでもう少し何とかならないかと思う。
stopM(M):-stopMN(M,1).
stopMN(M,N):-L is 2*M*(M+N),10^8=<L.
gcd(0, B, G) :- G is abs(B).
gcd(A, B, G) :- A =\= 0, R is B mod A, gcd(R, A, G).
loopN(M,K):-
between(1,M,N),
(stopMN(M,N)->!,fail;true),
1=:=(M-N) mod 2,
gcd(M,N,G),
G=:=1,
L is 2*M*(M+N),
C is M*M+N*N,
A is M*M-N*N,
B is 2*M*N,
D is abs(A-B),
C mod D=:=0,
K is (10^8-1)//L.
loopM(K):-
between(1,10000,M),
(stopM(M)->!,fail;loopN(M,K)).
sum([],Sum,Sum):-!.
sum([E|Es],Sum,Result):-
Sum1 is Sum+E,
sum(Es,Sum1,Result).
main:-
findall(E,loopM(E),Es),
write(Es),
sum(Es,0,Ans),
write(Ans).
