C++で級数 1 + (1+3) + (1+3+5) + … + (1+3+5+…+(2n−1)) の合計を求める方法

問題概要

この問題では、整数 n が与えられ、以下の級数の合計を求めるプログラムを作成します。

1 + (1+3) + (1+3+5) + (1+3+5+7) + … + (1+3+5+7+…+(2n−1))

この級数をよく観察すると、i 番目の項は「最初の i 個の奇数の和」になっていることがわかります。

例題で理解を深めよう

入力：

n = 3

出力：

14

説明： (1) + (1+3) + (1+3+5) = 14

解法1：二重ループを使うシンプルなアプローチ

最も直感的な解決策は、二重ループ（ネストされたループ）を使い、各項の奇数を順番に合計変数へ加算していき、最後に合計を返す方法です。

サンプルコード

#include <iostream>
using namespace std;
int calcSeriesSum(int n) {
    int sum = 0, element = 1;
    for (int i = 1; i <= n; i++) {
        element = 1;
        for (int j = 1; j <= i; j++) {
            sum += element;
            element += 2;
        }
    }
    return sum;
}
int main() {
    int n = 12;
    cout<<"Sum of the series 1 + (1+3) + (1+3+5) + (1+3+5+7) + ... + (1+3+5+7+ ... + (2"<<n<<"-1)) is "<<calcSeriesSum(n);
    return 0;
}

実行結果

Sum of the series 1 + (1+3) + (1+3+5) + (1+3+5+7) + ... + (1+3+5+7+ ... + (2*12-1)) is 650

この方法は正しく動作しますが、二重ループを使用するため計算量が O(n²) となり、n が大きくなるほど非効率になります。

解法2：数学的公式を使う効率的なアプローチ

より効率的な方法は、級数の合計を求める一般公式を数学的に導出することです。

まず、最初の n 個の奇数の和（＝級数の各項に相当）について考えます。

1 + 3 + 5 + … + (2n−1) = n²

この性質を利用すると、級数全体の合計は次のように変形できます。

sum = (1) + (1+3) + (1+3+5) + … + (1+3+5+…+(2n−1))
sum = Σ (1+3+5+…+(2i−1))　（i = 1 ～ n）
sum = Σ i²
sum = n(n+1)(2n+1)/6

つまり、この級数は「最初の n 個の平方数の和」と等しく、有名な公式 n(n+1)(2n+1)/6 を使えば一度の計算で答えが求まります。

サンプルコード

#include <iostream>
using namespace std;
int calcSeriesSum(int n) {
    return ( n*(n + 1)*(2*n + 1) )/6;
}
int main() {
    int n = 9;
    cout<<"Sum of the series 1 + (1+3) + (1+3+5) + (1+3+5+7) + ... + (1+3+5+7+ ... + (2*"<<n<<"-1)) is "<<calcSeriesSum(n);
    return 0;
}

実行結果

Sum of the series 1 + (1+3) + (1+3+5) + (1+3+5+7) + ... + (1+3+5+7+ ... + (2*9-1)) is 285

まとめ

二重ループを使う方法は計算量 O(n²)、公式を使う方法は O(1) で計算できます。大きな n を扱う場合は、級数の数学的な性質を活かした公式ベースのアプローチが圧倒的に効率的です。