JavaScriptで残りの数の合計が2つの数の積に等しくなるペアを見つける方法

問題の概要

1から任意の整数 num までの連続した数列を考えます。この中から2つの数(それぞれ m と n と呼びます)を選び、次の条件を満たす組み合わせを見つけます。

sum(1 to num) - (m + n) = m * n

つまり、「選んだ2つの数を除いた残りの数の合計」が「選んだ2つの数の積」と等しくなるようなペアです。最終的に、条件を満たすすべての組み合わせを配列として返します。

具体例

入力が次の場合を考えてみましょう。

const num = 10;

このときの出力は次のようになります。

const output = [
    [7, 6]
];

理由はシンプルで、1から10までの合計が 55 であり、

55 - (6 + 7) = 6 * 7 = 42

という等式が成立するためです。つまり、6 と 7 を取り除いた残りの数の合計(42)が、6 × 7 の積(42)と一致します。

実装コード

この問題は次のように解くことができます。

const num = 10;
const pickNumbers = num => {
    const sum = (num) * (num + 1) * (.5);
    const results = [];
    for (let n = 1; n <= num; n++) {
        let first = sum - n;
        let second = n + 1;
        if (first % second === 0) {
            let m = first / second;
            if (m < num && m !== n && results.every(group => group[0] + group[1] !== m + n)){
                results.push([m, n]);
            }
        }
    }
    return results;
}
console.log(pickNumbers(10));

コードの解説

このアルゴリズムのポイントは以下の3点です。

• 合計の高速な計算: 等差数列の和の公式 n(n+1)/2 を利用することで、1から num までの合計をループなし(O(1))で求めています。
• m を一意に導出する変形: 条件式 sum − (m + n) = m × n を m について解くと、m = (sum − n) / (n + 1) となります。これにより、n を1つ決めれば対応する m がすぐに計算でき、全ペアを総当たりする必要がなくなります。
• 妥当性チェック: m が整数であること(first % second === 0)、num 未満であること、n と異なること、さらに同じペアの重複登録を防ぐ確認を行ったうえで、結果に追加しています。

実行結果

コンソールには次のように出力されます。

[
    [7, 6]
]

すべてのペアを二重ループで調べる O(num²) のアプローチと比べ、この方法はループが1回で済むため、大きな num に対しても効率的に動作します。数式を事前に変形しておくことで探索範囲を大きく絞れる、数学的な工夫が活きた良い例といえるでしょう。