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

問題概要

本記事では、整数 n が与えられたとき、級数 1² + 3² + 5² + … + (2n−1)² の総和を求める方法を解説します。この級数は「最初の n 個の奇数の平方の和」を表しており、競技プログラミングや学習の題材としてよく登場します。

入力例と出力例

入力:

n = 5

出力:

165

計算過程:

sum = 1² + 3² + 5² + 7² + 9²
    = 1 + 9 + 25 + 49 + 81
    = 165

それでは、この問題を解くための2つのアプローチを順に見ていきましょう。

方法1: ループを使った基本的な解法

最もシンプルな方法は、for ループで 1 から n まで順番に各奇数 (2i−1) の平方を計算し、合計に加算していくアプローチです。計算量は O(n) となります。

サンプルコード

#include <iostream>
using namespace std;

int calcSumOfSeries(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += (2 * i - 1) * (2 * i - 1);
    return sum;
}

int main() {
    int n = 5;
    cout << "級数（n = " << n << "）の総和は " << calcSumOfSeries(n);
    return 0;
}

実行結果

級数（n = 5）の総和は 165

この方法は直感的で理解しやすい反面、n が大きくなるとループ回数が増え、実行時間が線形に増加します。

方法2: 数式を使った効率的な解法

実は、この級数の総和には数学的に導出された閉じた形の公式が存在します。公式を利用すれば、ループ不要で O(1) の定数時間で答えを求められます。

総和の公式は次の通りです。

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

この公式は「最初の n 個の奇数の平方和」を表す標準的な式で、偶数の平方和の公式 (2n(2n−1)(2n+1)/3 の半分) から導くこともできます。

サンプルコード

#include <iostream>
using namespace std;

int calcSumOfSeries(int n) {
    return (n * (2 * n - 1) * (2 * n + 1)) / 3;
}

int main() {
    int n = 5;
    cout << "級数（n = " << n << "）の総和は " << calcSumOfSeries(n);
    return 0;
}

実行結果

級数（n = 5）の総和は 165

検算してみると、n = 5 のとき 5 × 9 × 11 / 3 = 495 / 3 = 165 となり、ループによる結果と一致します。

まとめ

級数 1² + 3² + 5² + … + (2n−1)² の総和を求めるには、次の2つの方法があります。

ループによる解法: 各奇数の平方を順に加算する。実装は簡単だが計算量は O(n)。
公式による解法: n(2n−1)(2n+1)/3 を使う。計算量は O(1) で、大きな n に対しても高速。

実務やコンテストでは、公式を使った O(1) の解法が効率的です。ただし、n が非常に大きい場合は int 型のオーバーフローに注意し、必要に応じて long long 型などを使用しましょう。