「プロジェクトオイラー問１０８」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問１０８」(2014/03/07 (金) 03:10:11) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

http://odz.sakura.ne.jp/projecteuler/index.php?Problem%20108

*Problem 108 「ディオファントス逆数 その1」 †
次の等式で x, y, n は正の整数である.

1/x + 1/y = 1/n

n = 4 では 3 つの異なる解がある.

1/5 + 1/20 = 1/4

1/6 + 1/12 = 1/4

1/8 + 1/8 = 1/4

解の数が 1000 を超える最小の n を求めよ.

注: この問題は Problem 110 の易しいケースである. こちらを先に解く事を強く勧める.


解法
素朴な解法でもなんとかなる範囲の問題です。
1/x+1/y=1/n
(x+y)/xy=1/n
nx+ny=xy
(x-n)(y-n)=n^2
よりｘ-ｎとｙ-ｎがn＾２の約数となればよい。
ｎ＾２の約数の個数はｎの約数の個数の求め方を少し変更すれば求まる。
ｘ-ｎが定まればｙ-ｎは一つに定まるのでｘ-ｎ＜＝Ｙ-ｎとしても一般性を失わず。
1/ｎを満たす組み合わせは
n^2の約数の個数/２+1となります。


 divs(N,D,Count,N,Result):-N mod D>0,!,Result is 2*Count+1.
 divs(N,D,Count,ResultN,ResultCount):-
 	!,
 	N1 is N//D,
 	Count1 is Count+1,
 	divs(N1,D,Count1,ResultN,ResultCount).
 
 yakusu_count_double(1,_,Count,Count):-!.
 yakusu_count_double(N,D,Count,Result):-
 	N<D*D,
 	!,
 	Result is Count*3.
 yakusu_count_double(N,D,Count,Result):-
 	!,
 	divs(N,D,0,N1,Perm),
 	Count1 is Count*Perm,
 	D1 is D+1,
 	yakusu_count_double(N1,D1,Count1,Result).
 
 search(N):-
 	yakusu_count_double(N,2,1,Perm),
 	Perm//2+1>1000,
 	!,
 	write(N).
 search(N):-
 	!,
 	N1 is N+1,
 	search(N1).
 main108:-
 	search(2).