【C++】数列 1, 6, 15, 28, 45, … のN番目の項を求めるプログラム

問題概要

この問題では、整数値 N が与えられます。求めるのは、数列「1, 6, 15, 28, 45, …」の N番目の項 を計算するプログラムです。

この数列には、「各要素は、その前後の要素の平均値より2小さい」という面白い性質があります。

具体例を見て、問題を理解しましょう。

入力

N = 5

出力

45

解法アプローチ

数列 1, 6, 15, 28, 45, … を詳しく観察すると、隣接する項同士の差は「5, 9, 13, 17, …」となっており、これ自体が公差4の等差数列になっています。このような2階等差数列の一般項は、二次式で表すことができます。

実際、この数列は六角数（ヘキサゴナル数）と呼ばれるもので、N番目の項は次の公式で求められます。

TN = 2*N*N - N

検証してみると、N=1 のとき 2×1−1=1、N=2 のとき 2×4−2=6、N=5 のとき 2×25−5=45 となり、正しく数列と一致します。

また、大きな N に対してオーバーフローを防ぐため、計算結果を大きな素数（10⁹+9）で剰余算しています。

この解法の動作を示すプログラムが以下の通りです。

実装例

#include <iostream>
using namespace std;
#define mod 1000000009
int calcNthTerm(long n) {
    return (((2 * n * n) % mod) - n + mod) % mod;
}
int main(){
    long N = 19;
    cout<<N<<"th Term of the series is "<<calcNthTerm(N);
    return 0;
}

出力

19th Term of the series is 703

このように、数列の規則性を見抜いて一般項を導出すれば、ループを使わず O(1) の計算量で任意のN番目の項を即座に求められます。