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

Problem 110 「ディオファントス逆数 その2」 †

次の等式で x, y, n は正の整数である.

1/x + 1/y = 1/n

n = 1260 では 113 の異なる解があり, この n が解の個数が 100 を超える最小の値である.

解の数が 4,000,000 を超える最小の n を求めよ.

注: この問題は Problem 108 を非常に難しくしたケースである. 総当り法で解ける範囲を超えているので, 賢い解き方が求められる.



解説
まずは素朴に式変形をしてみる。
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=p1^a1*p2^a2*,,,pm^amとしますと
n^2の約数の個数は
k=(2a1+1)(2a2+1),,,(2am+1)個となります。
x-n<=y-nとしても一般性は失わないので
条件を満たすx、yの組はk/2+1個であると分かります。
しかし答えは
9350130049860600
とても大きな数で約数を求めていては間に合いません。
逆から考えます。

nを素因数の積として組み立てるとき
n=p1^a1*p2^a2*,,,pm^am
n^2の約数の個数はaiだけで決まります。
またp1<p2<,,<pmとしても一般性は失いません。

するとできるだけ小さなpに大きなaiを割り当てたほうが同じxyの組の個数が得られてもnは小さくなります。
よってa1>=a2>=,,,>=amとなります。
またpの数列が
2,5,7のように隙間ができるより。
2,3,5,7、、、のように隙間のない連続した素数の時のほうが同じ個数のxyの組が得られるのでも小さなnを作り出せます。
この発想に従いnを小さい順から生成すればBigO(20000)程度で答えが出ます。
nを小さいほうから生成するのには優先順位付きキューを使えばよいでしょう。



この発想でわたしは正答してるのでまあそんなに間違ってはないです。
問題は、問のタイトルがディオファントス逆数となってることで。
おそらく正しい解法はディオファントス方程式と絡めて解くのだと思います。
どなたかアドバイスがあれば嬉しいですね。