PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 66 / ディオファントス方程式

次の形式の2次のディオファントス方程式を考えよう。
x^2 - Dy^2 = 1

たとえば D=13 のとき,x を最小にする解は
649^22 - 13×180^22 = 1 である。

D が平方数のとき,正整数のなかに解は存在しないと考えられる。

D={2, 3, 5, 6, 7} に対して x を最小にする解は次のようになる。

  • 3^2 - 2×2^2 = 1
  • 2^2 - 3×1^2 = 1
  • 9^2 - 5×4^2 = 1
  • 5^2 - 6×2^2 = 1
  • 8^2 - 7×3^2 = 1

D ≤ 7 に対して x を最小にする解を考えると,D=5 のとき x は最大である。

D ≤ 1000 に対する x を最小にする解で x が最大になるような D の値を見つけよ。

Problem 66 - Project Euler


素直なペル方程式の問題でした。普通に最小解の最大値を求めるだけ。最小解の求め方は wikipedia に書いてあります。
ペル方程式 - Wikipedia

ちなみに最小解の最大値は38桁の数でした。
16421658242965910275055840472270471049