⏱️
Project Eulerの初級問題#51"Prime Digit Replacements"をJavaScriptで解く

2025/10/23に公開
 はじめにProject Eulerは、プログラミングによって解くことを意図した数学的な問題を集めたウェブサイトです。初級問題の中でも少し難易度が高い問題の解き方について、忘れないように残しておきたいと思います。今回の問題は、#51 "Prime Digit Replacements" です。

https://projecteuler.net/problem=51

 問題Prime Digit Replacements (素数の桁置換)
2桁の数字 *3 の1桁目を置き換えると、9つの可能な値のうちの6個、すなわち 13、23、43、53、73、83 はすべて素数である。

56**3 の3桁目と4桁目を同じ数字に置き換えると、この5桁の数字は、生成された10個の数の中で7個の素数を持つ最初の例となり、56003、56113、56333、56443、56663、56773、56993 というファミリーが生成される。したがって、このファミリーの最初のメンバーである 56003 は、この性質を持つ最小の素数となる。

数の一部（必ずしも隣接する数字である必要はない）を同じ数字に置き換えることで、8個の素数のファミリーに属する最小の素数を見つけなさい。

 考察この問題は、単純に素数の数字を置き換える操作を、小さな素数から順に試していくことにより、解を見つけることができそうに思われます。しかし、置き換える数字の個数と位置に制約がないため、素数の桁数が増えると計算量が大幅に増大し、１分以内に問題を解くことができなくなります。そこで、以下の考察を行います。
数を構成する数字の和が3の倍数の場合、その数自体も3の倍数であり、素数ではない。従って、置き換える数字が1個の場合、生成された10個の数の中に3の倍数が少なくとも3個は含まれるため、8個の素数のファミリーはできない。
同様に置き換える数字が2個の場合も、8個の素数のファミリーはできない。従って、置き換える数字の個数は、3または3の倍数でなければならない。
置き換える前の数字を n とすると、置き換えた後の数字で n よりも大きいものは、9-n 種類存在する。小さな数から順に判定していくことを前提にすると、8個のファミリーを作るためには、n が 2 以下でなければならない。
7個の素数のファミリーができる最小の素数は56003であるため、8個の素数のファミリーができる最小の素数はこの数よりも大きい。

 解決方針上記の考察に基づいて、以下の解決方針を立てます。
大きな数が素数かどうかの判定には時間がかかるため、「エラトステネスのふるい」(https://ja.wikipedia.org/wiki/エラトステネスの篩) を用いて、ある上限値未満のすべての素数を抽出しておく。上限値は、考察4を参考にして仮に1,000,000に設定する。
抽出された5桁および6桁の素数について、小さいものから順に同じ数字 n:[0-2] が正確に3個含まれるかどうかを判定する。なお、同じ数字が3個2組または6個1組の場合は、数を構成する数字の和が3の倍数になり、素数でなくなるため考慮する必要はない。
同じ数字 n を n+1 から 9 まで順に置き換えていき、8個の素数になれば、置き換える前の数が解となる。
解が見つかるまで、上記2,3を繰り返す。なお、もし解が見つからなかった場合は、上記1,2を見直す。

 プログラム構成上記の解決方針に基づいて、以下の関数を作成します。なお、言語はJavaScript(Node.js)を使用します。

 getPrimes(nMax)1 以上 nMax 未満の整数について、素数ならばtrue、そうでなければfalseの値が格納された配列を生成する。引数は配列のサイズ、戻り値は生成した配列である。配列の生成にはエラトステネスのふるいを使用し、isPrime[n] で n が素数かどうかを判定できるようにする。
function getPrimes(nMax) {
    let isPrime = Array(nMax); // 素数判定配列
    isPrime.fill(true);
    isPrime[1] = false;
    for (let n = 2; n < nMax; n++) {
        if (isPrime[n]) {
            for (let m = n * 2; m < nMax; m += n) {
                isPrime[m] = false;
            }
        }
    }
    return isPrime;
}

 findThree(n)整数 n の各桁に同じ数字が正確に3個含まれているかどうかを判定する。ただし、数字は2以下(0,1,2の3種類)に限定する。引数は調べる整数、戻り値は3個含まれている数字があればその数、なければ-1である。例えば、findThree(10121) は 1、findThree(10221) は -1 を返却する。
function findThree(n) {
    let digits = Array(3); // 0,1,2の個数
    digits.fill(0);
    while (n > 0) {
        let m = n % 10;
        if (m <= 2) {
            digits[m]++;
        }
        n = Math.floor(n / 10);
    }
    for (let m = 0; m <= 2; m++) {
        if (digits[m] == 3) {
            return m;
        }
    }
    return -1;
}

 countMembers(p, m, isPrime)素数 p に含まれる数字 m を置き換えることによって生成可能な素数のファミリーのメンバー数をカウントする。引数は、素数、数字、getPrimes関数で作成した素数判定配列、戻り値はメンバー数である。例えば、countMembers(13, 1, isPrime) は 6、countMembers(56003, 0, isPrime) は 7 を返却する。
function countMembers(p, m, isPrime) {
    let count = 1; // メンバー数(自身を含む)
    let pString = String(p);
    for (let i = m + 1; i <= 9; i++) {
        let replaced = pString.replaceAll(String(m), String(i));
        if (isPrime[Number(replaced)]) {
            count++;
        }
    }
    return count;
}

 problem51()問題を解く。引数はなく、戻り値は素数のファミリーのうちメンバー数が8の最小メンバーの値である。
function problem51() {
    // 素数を抽出する
    let maxPrime = 1_000_000; // 素数の最大値
    let nMembers = 8; // メンバー数
    let isPrime = getPrimes(maxPrime); // 素数判定配列

    for (let d = 5; d <= 6; d++) { // 5桁と6桁の数が対象
        let minPrime = 10 ** (d - 1);
        for (let p = minPrime; p < minPrime * 10; p++) {
            if (isPrime[p]) { // 素数ならば
                let f = findThree(p);
                if (f >= 0) { // 0,1,2が3つあれば
                    if (countMembers(p, f, isPrime) == nMembers) {
                        return p; // 最小メンバー
                    }
                }
            }
        }
    }
}

 おわりに以下の文を実行すれば、コンソールに解が表示されます。幸い、6桁の範囲で素数が見つかりました。プログラムの実行時間は、ノートPC(Intel(R) Core(TM) i5-8250U CPU)で0.1秒未満でした。
console.log(problem51());

 関連記事Project Eulerの初心者向け問題をPythonで解く

https://zenn.dev/uinoue/articles/9979461e883245
はじめに

問題

考察

解決方針

プログラム構成

getPrimes(nMax)

findThree(n)

countMembers(p, m, isPrime)

problem51()

おわりに

関連記事

Discussion
