PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 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 108 - Project Euler


約数の個数の問題ということで,問題12と似た解答になりました。

variee.hatenadiary.com

与式は (x-n)(y-n)=n^2 と変形できるので n^2 を素因数分解すれば解けますが,「n^2 の約数が1001個以上」で解いてみたら不正解……

確認のため n=4 で実験してみました。4^2=2^4 の約数は 4+1=5 個。普通に x, y を求めるとこうなります。

(x-4, y-4)=(16,1), (8,2), (4, 4), (2, 8), (1, 16)

しかし,問題文では解は3個です。「x, y, n は正の整数」としれっと書いてありますが,実は x ≦ y という条件が隠れています。重複を含めると,n^2 の約数は2001個以上必要です。これで解けました。