JavaScriptで増加数列のn番目の要素を効率的に求める方法

問題の定義

本記事では、以下のように定義される「増加数列」の n 番目の要素を求めるアルゴリズムを考えていきます。

• seq(0) = 1 が数列の最初の要素です。
• 数列に含まれる各 x に対して、y = 2 * x + 1 および z = 3 * x + 1 の値も必ず数列に含まれます。
• 上記以外の数値は数列に含まれません。

このルールに従うと、数列の最初のいくつかの項は次のようになります。

[1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]

解法のアプローチ

この問題は、有名な「ハミング数（正則数）」の生成と同じ発想で解くことができます。ポイントは、2つのポインタ（インデックス）を使って次の候補値を比較しながら小さい方を順に数列へ追加していくことです。

• ポインタ x は「2 * 値 + 1」の生成元を追跡します。
• ポインタ y は「3 * 値 + 1」の生成元を追跡します。
• 両者の出力が同じ値になった場合は重複を避けるため、y だけ進めます。

こうすることで O(n) の時間計算量で、ソート済みの増加数列を重複なく構築できます。

実装コード

以下が実際の実装例です。

const num = 10;

const findNth = n => {
    let seq = [1], x = 0, y = 0;
    for (let i = 0; i < n; i++) {
        let nextX = 2 * seq[x] + 1, nextY = 3 * seq[y] + 1;
        if (nextX <= nextY) {
            seq.push(nextX);
            x++;
            // 両者が一致した場合は重複を避けるため y も進める
            if (nextX == nextY)
                y++;
        } else {
            seq.push(nextY);
            y++;
        }
    }
    return seq[n];
};

console.log(findNth(num));

出力結果

22

処理の流れの解説

num = 10 を渡した場合、関数は数列の先頭から 10 項分（インデックス 0〜10）を生成します。生成過程を追うと以下のようになります。

1. 初期状態：seq = [1]、x = 0、y = 0
2. 1 から 3（= 2×1+1）と 4（= 3×1+1）が候補となり、小さい方の 3 を追加
3. 以降も同様に候補を比較しながら 7, 9, 10, 13, 15, 19, 21, 22 の順に追加

最終的に seq[10] である 22 が返され、コンソールに出力されます。この手法により、毎回全体をソートし直すことなく、常に昇順の数列を維持したまま目的の項を取得できる点が大きなメリットです。