C++で数列 1, 17, 98, 354, … の n 番目の項を求める方法

今回扱う数列は「1, 17, 98, 354, …」です。この数列を注意深く観察すると、n 番目の項が「4乗の累積和」で表されていることがわかります。具体的なパターンを見てみましょう。

1   = 1^4
17  = 1^4 + 2^4
98  = 1^4 + 2^4 + 3^4
354 = 1^4 + 2^4 + 3^4 + 4^4
...

つまり、n 番目の項は「1 から n までの各整数の4乗をすべて足し合わせた値」になります。

アルゴリズム

• 求めたい項番号 n を用意します。
• 結果を格納する変数を 0 で初期化します。
• 1 から n まで繰り返すループを作成します。
  • 現在の数の4乗を結果に加算していきます。
• 最終的な結果を出力します。

この方法の計算量は O(n) とシンプルです。なお、4乗和の閉形式の公式を使えば O(1) で求めることもできますが、ここでは理解しやすさを優先してループによる実装を紹介します。

C++での実装

上記のアルゴリズムをC++で実装すると、次のようになります。

#include <bits/stdc++.h>

using namespace std;

int getNthTerm(int n) {
    int nthTerm = 0;
    for (int i = 1; i <= n; i++) {
        nthTerm += i * i * i * i;
    }
    return nthTerm;
}

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

実行結果

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

4676

この例では n = 7 としているため、「1^4 + 2^4 + … + 7^4 = 4676」が正しく計算できていることが確認できます。