※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。


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
よりx-nとy-nがn^2の約数となればよい。
n^2の約数の個数はnの約数の個数の求め方を少し変更すれば求まる。
x-nが定まればy-nは一つに定まるのでx-n<=Y-nとしても一般性を失わず。
1/nを満たす組み合わせは
n^2の約数の個数/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).