C++で実装するニューマン・シャンクス・ウィリアムズ素数の求め方

ニューマン・シャンクス・ウィリアムズ素数（NSW素数）は、数学者ニューマン、シャンクス、ウィリアムズによって研究された特別な数列に現れる素数の系列です。この数列は以下のように始まります。

1, 1, 3, 7, 17, 41...

このうち素数となる項が「NSW素数」と呼ばれます（例：7, 41, 239 など）。数列の各項を一般化すると、次の漸化式で定義することができます。

a0 = 1
a1 = 1
an = 2 × a(n-1) + a(n-2)

アルゴリズム

• 求めたい項の番号 n を初期化します。
• 数列の最初の2項として「1」と「1」を設定します。
• n の項に達するまでループ処理を行います。
  • 直前の2項を使って次の項を計算します。
  • 直前の2項の値を新しい値で更新します。
• 最終的に得られた項を返します。

C++での実装例

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
int getNthTerm(int n) {
    if(n == 0 || n == 1) {
        return 1;
    }
    int a = 1, b = 1;
    for(int i = 3; i <= n; ++i) {
        int c = 2 * b + a;
        a = b;
        b = c;
    }
    return b;
}
int main() {
    int n = 5;
    cout << getNthTerm(n) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

17