JavaScriptでディオファントス方程式 x² − 4y² = n のすべての解を求める方法

問題

数値 n を引数として受け取るJavaScript関数を作成する必要があります。この関数は、次のディオファントス方程式を満たすすべての整数 x と y の組み合わせを見つけ出します。

x² − 4y² = n

そして、条件を満たすペア [x, y] をすべて配列として返します。

解法のアプローチ

この方程式は、因数分解の公式を利用すると効率的に解くことができます。

x² − 4y² = (x + 2y)(x − 2y) = n

つまり、n の約数ペアを順に調べ、そこから x と y を逆算する方法が有効です。具体的には次の関係式が成り立ちます。

• a = x − 2y、b = x + 2y とおくと、a × b = n
• x = (a + b) / 2
• y = (b − a) / 4

このため、a を 1 から √n まで順に走査し、b = n / a が整数になるかを確認します。さらに x と y がどちらも整数になる場合のみ、そのペアを結果に追加します。計算量は約 O(√n) に抑えられるため、大きな数値でも高速に処理できるのが特徴です。

コード例

以下が実際のコードです。

const num = 90005;
const findSolution = (num = 1) => {
  const res = [];
  let a, b, x, y;
  for (a = 1; a <= Math.sqrt(num); a++) {
    if (Number.isInteger(b = num / a)) {
      if (Number.isInteger(x = (b + a) / 2)) {
        if (Number.isInteger(y = (b - a) / 4)) {
          res.push([x, y]);
        }
      }
    }
  }
  return res;
};
console.log(findSolution(num));

出力結果

[ [ 45003, 22501 ], [ 9003, 4499 ], [ 981, 467 ], [ 309, 37 ] ]

コードの解説

このコードでは、Number.isInteger() を使って各段階で値が整数であるかを厳密にチェックしています。まず b = num / a が整数でなければ a は約数ではないため除外し、次に x = (b + a) / 2、最後に y = (b − a) / 4 が整数であることを確認します。これらの条件をすべて満たす場合のみ、ペア [x, y] を結果配列に格納します。

なお、y の計算で 4 で割っているのは、b − a = 4y という関係が成り立つためです。この条件チェックにより、整数解のみを確実に抽出できます。