C++で数列 1、11、55、239、991、… のN番目の項を求める方法

本記事では、数列 1, 11, 55, 239, 991, … のN番目の項をC++で求める方法を解説します。

この数列をよく観察すると、各項は次の一般項（公式）で表せることがわかります。

n番目の項 = 4ⁿ − 2ⁿ − 1

実際に確認してみましょう。

• n = 1 のとき： 4¹ − 2¹ − 1 = 4 − 2 − 1 = 1
• n = 2 のとき： 4² − 2² − 1 = 16 − 4 − 1 = 11
• n = 3 のとき： 4³ − 2³ − 1 = 64 − 8 − 1 = 55

このように、公式が数列のすべての項と一致していることが確認できます。

アルゴリズム

• 項数 N を初期化します。
• 数列の一般項の公式を使って N 番目の項を計算します。
• 計算結果を出力します。

C++での実装

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

#include <bits/stdc++.h>
using namespace std;

int getNthTerm(int n) {
    int num = pow(4, n) - pow(2, n) - 1;
    return num;
}

int main() {
    int n = 7;
    cout << getNthTerm(n) << endl;
    return 0;
}

出力結果

上記のコードを実行すると、以下の結果が出力されます。

16255

n = 7 の場合、4⁷ − 2⁷ − 1 = 16384 − 128 − 1 = 16255 となり、正しく計算できていることがわかります。

まとめ

数列 1, 11, 55, 239, 991, … のN番目の項は、一般項 4ⁿ − 2ⁿ − 1 を使うことで、O(1) の計算量で求められます。べき乗の計算には標準ライブラリの pow 関数を利用するのが簡単で便利です。