【JavaScript】パドヴァン数列のn番目の要素を求める方法

パドヴァン数列とは

パドヴァン数列(Padovan Sequence)とは、次の初期値で定義される整数列 P(n) のことです。

P(0) = P(1) = P(2) = 1

そして、以下の漸化式に従って各項が決まります。

P(n) = P(n-2) + P(n-3)

この漸化式から導かれる最初のいくつかの値は次のとおりです。

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, …

フィボナッチ数列が直前の2項の和で定義されるのに対し、パドヴァン数列は「2つ前」と「3つ前」の項を足す点が特徴的です。建築家リチャード・パドヴァンの名前にちなんだこの数列は、隣接する3辺が正三角形をなす螺旋構造など、自然界やデザインの分野にも現れることで知られています。

問題

ここでは、数値 n を引数として受け取り、パドヴァン数列の n 番目の項を返す JavaScript 関数を作成します。

実装例

以下のコードをご覧ください。

const num = 32;
const padovan = (num = 1) => {
    let secondPrev = 1, pPrev = 1, pCurr = 1, pNext = 1;
    for (let i = 3; i <= num; i++){
        pNext = secondPrev + pPrev;
        secondPrev = pPrev;
        pPrev = pCurr;
        pCurr = pNext;
    };
    return pNext;
};
console.log(padovan(num));

コードの解説

この実装では、反復処理によって効率的に n 番目の項を求めています。

変数 secondPrev(2つ前の項)、pPrev(1つ前の項)、pCurr(現在の項)の3つの変数を使い、ループ内で毎回新しい項 pNext を計算しながら値をずらしていきます。初期値として最初の3項すべてに 1 を設定しているため、n が 0〜2 の場合はそのまま 1 が返されます。

時間計算量は O(n)、空間計算量は O(1) であり、再帰的な実装と比べて大きな n に対しても高速に動作するのがメリットです。

出力結果

5842

n = 32 を渡した場合、32番目の項である 5842 が出力されます。