PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 110 / ディオファントス逆数2

次の等式で 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 を求めよ。

Problem 110 - Project Euler


第108問の類題です。解の個数が 1000 個から 4*10^6 個へ大幅に増えています。

variee.hatenadiary.com

与式を (x-n)(y-n)=n^2 と変形して n^2 の約数の個数を調べます。n=4 の例から x≦y がわかるので,重複も含めて約数は 8*10^6+1 個以上必要です。

n が k 種類の素数を1個ずつ含む場合を考えると,n^2 は各素数を2個ずつ含みます。約数の個数の条件は

 (2+1)^k \geqq 8\cdot 10^6+1

これをみたす k の最小値は15なので,使う素数は15個以下です。実際にはこれは効率が悪く,14個以下の素数を使うかわりに2や3を使う回数を増やします。

同様に n がいろいろな素数を2個ずつ含む場合を考えると,

 (4+1)^k \geqq 8\cdot 10^6+1\quad \therefore k\geqq 10

上の場合と同じく,11個以上の素数を使うかわりに2や3を使う回数を増やせばよいとわかります。

これで n の形が限定できました。小さい方から順に11個の素数をかけたもの(下のコード中の a)の倍数です。

答えは a の
 46620=2^2\cdot 3^2\cdot 5\cdot 7\cdot 37
倍でした。足し算するだけなのであっという間に終わります。

参考までに答えの素因数分解も載せておきます。

 \begin{align}
&9350130049860600\\
&=2^3\cdot 3^3\cdot 5^2\cdot 7^2\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23\cdot 29\cdot 31\cdot 37
\end{align}