JavaScriptでスーパー・アグリー数を求めるアルゴリズム

スーパー・アグリー数とは

スーパー・アグリー数（Super Ugly Number）とは、すべての素因数が、あらかじめ与えられたサイズkの素数リスト「primes」の中に含まれる正の整数のことです。

たとえば、素数リストとして [2, 7, 13, 19] を指定した場合、最初の12個のスーパー・アグリー数は [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] となります。これらの数はすべて、素因数が2・7・13・19のいずれかだけで構成されている点が特徴です。

問題の定義

今回作成するのは、第1引数に整数 num、第2引数に素数の配列 arr を受け取るJavaScript関数です。この関数は、num 番目のスーパー・アグリー数を計算し、その結果を返す必要があります。

アルゴリズムの考え方

この問題は、各素数ごとに「ポインタ」を持たせることで効率的に解くことができます。基本的な流れは以下の通りです。

1. 各素数に対応するポインタを0で初期化する
2. これまでに求めた結果列のうち、ポインタが指す値と素数を掛け合わせた候補の中から最小値を選ぶ
3. 選ばれた最小値を新しいスーパー・アグリー数として結果に追加する
4. その最小値を割り切れる素数のポインタを1つ進める
5. 目的の番目に達するまで2〜4を繰り返す

この手法により、重複する候補も自動的に処理され、常に昇順でスーパー・アグリー数を生成できます。

実装コード

実際のコードは以下のようになります。

const num = 7;
const arr = [2, 7, 14, 19];
const superUgly = (num = 1, arr = []) => {
    arr.sort((a, b) => a - b);
    const ptr = [];
    const res = [];
    for(let i = 0; i < arr.length; i++){
        ptr[i] = 0;
    };
    res.push(1);
    for(let i = 1; i < num; i++){
        let mn = Math.pow(2, 32) - 1;
        for(let j = 0; j < arr.length; j++){
            mn = Math.min(mn, arr[j] * res[ptr[j]])
        };
        res[i] = mn
        for(let j = 0; j < arr.length; j++){
            if(mn % arr[j] === 0){
                ptr[j]++;
            };
        };
    };
    return res[num-1]
};
console.log(superUgly(num, arr));

出力結果

このコードを実行すると、コンソールには以下のように出力されます。

16

この例では、配列 [2, 7, 14, 19] を素因数の候補として、7番目のスーパー・アグリー数である 16 が正しく取得できています。数列は 1 → 2 → 4 → 7 → 8 → 14 → 16 と生成され、それぞれの数が指定された因数のみで構成されていることが確認できます。