次の等式で 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
解の数が 4,000,000 を超える最小の n を求めよ。
第108問の類題です。解の個数が 1000 個から 4*10^6 個へ大幅に増えています。
与式を (x-n)(y-n)=n^2 と変形して n^2 の約数の個数を調べます。n=4 の例から x≦y がわかるので，重複も含めて約数は 8*10^6+1 個以上必要です。
n が k 種類の素数を1個ずつ含む場合を考えると，n^2 は各素数を2個ずつ含みます。約数の個数の条件は
これをみたす k の最小値は15なので，使う素数は15個以下です。実際にはこれは効率が悪く，14個以下の素数を使うかわりに2や3を使う回数を増やします。
同様に n がいろいろな素数を2個ずつ含む場合を考えると，
上の場合と同じく，11個以上の素数を使うかわりに2や3を使う回数を増やせばよいとわかります。
これで n の形が限定できました。小さい方から順に11個の素数をかけたもの（下のコード中の a）の倍数です。
答えは a の
倍でした。足し算するだけなのであっという間に終わります。
参考までに答えの素因数分解も載せておきます。