プロジェクトオイラー問１０８ - c21coterie @ ウィキ

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).