JavaScriptで2つのn桁の数の積から作られる最大の回文数を求める方法

まず「9009」という数字について考えてみましょう。この数には特別な性質があります。それは、2桁の数同士の掛け算(91 × 99)によって作られる最大の回文数だということです。

今回の課題は、桁数 n を引数として受け取り、n桁の数同士の積の中で最も大きな回文数を見つけて返すJavaScript関数を作成することです。

解法のアプローチ

この問題は総当たりで全ての組み合わせを調べることも可能ですが、効率的に解くために以下の方針を採用します。

• n桁の最大値(例：n = 3 なら 999)と最小値(例：100)を求める。
• 最大値の二乗から降順に候補となる数を調べていく。
• 各候補について回文数かどうかを判定する。
• 回文数が見つかったら、その平方根以上の範囲に n桁の因数が存在するかを確認する。
• 条件を満たす最初の数が見つかった時点で、それが答えとなる。

回文数の判定は、数値を逆順に並べ替えて元の数と一致するかどうかを比較するシンプルな方法で行います。

サンプルコード

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

const largestPalindromic = num => {
    let i, n, m, d, max, sup, limit, number = 0;
    // n桁の最大値(999...9)を作成
    for (i = 1; i < num; i += 1) {
        number = 10 * number + 9;
    };
    max = number;
    sup = 10 * number + 9;
    // 回文数かどうかを判定する関数
    const isPalindromic = n => {
        let p = 0, q = n, r;
        while (n > 0) {
            r = n % 10;
            p = 10 * p + r;
            n = Math.floor(n / 10);
        };
        return p === q;
    };
    // 最大値の二乗から降順に探索
    for (n = sup * sup, m = max * max; n > m; n -= 1) {
        if (isPalindromic(n)) {
            limit = Math.ceil(Math.sqrt(n));
            d = sup;
            while (d >= limit) {
                if (n % d === 0 && n / d > max) {
                    return n;
                }
                d -= 1;
            }
        }
    };
}
console.log(largestPalindromic(3));

実行結果

コンソールには以下の出力が表示されます。

906609

3桁の場合、913 × 993 の積である 906609 が、2つの3桁の数の積から作られる最大の回文数となります。このアプローチにより、全ての組み合わせを試すよりも大幅に計算量を抑えながら、正しい答えを効率的に求めることができます。