C++で数列「2、4、3、4、15…」のN番目の項を求めるプログラム

この記事では、整数Nが与えられたときに、C++を使って数列「2, 4, 3, 4, 15, …」のN番目の項を求めるプログラムを作成します。

問題の説明

対象となる数列は以下の通りです。

2, 4, 3, 4, 15, 0, 14, 16 ....（N項まで）

この数列の一般項（第n項）を表す公式を見つけ出し、それをもとに任意のN番目の値を計算するのが目的です。

まず、具体例を使って問題を確認しましょう。

• 入力：N = 9
• 出力：9

解決のアプローチ

この数列の値の増加傾向を観察すると、増加は線形的であり、平方数などの特別なパターンは含まれていません。しかし、値は他の要因にも依存していることがわかります。たとえば、6番目の項が「0」になっている点から、2や3による剰余演算（割り算の余り）が関係していそうです。

そこで、まず各項をNの値（1, 2, 3, …）で分解して整理してみます。

数列：1×(2), 2×(2), 3×(1), 4×(1), 5×(3), 6×(0), …

この分解結果を注意深く観察すると、括弧内の値はそれぞれ「Nを2で割った余り」と「Nを3で割った余り」の和になっていることがわかります。したがって、一般項の公式は次のように導き出せます。

T_n = N × ((N % 2) + (N % 3))

公式の検証

実際にいくつかの値で確認してみましょう。

• N = 1 のとき：1 × (1 + 1) = 2 ✓
• N = 2 のとき：2 × (0 + 2) = 4 ✓
• N = 3 のとき：3 × (1 + 0) = 3 ✓
• N = 5 のとき：5 × (1 + 2) = 15 ✓
• N = 6 のとき：6 × (0 + 0) = 0 ✓

すべての項が正しく求められていることが確認できました。

解法の実装プログラム

#include <iostream>
using namespace std;
int findNTerm(int N) {
    int nthTerm = ( N*((N%2) + (N%3)) );
    return nthTerm;
}
int main()
{
    int N = 10;
    cout<<N<<"th term of the series is "<<findNTerm(N);
    return 0;
}

出力結果：

10th term of the series is 10

このように、剰余演算を活用したシンプルな一行の式だけで、複雑に見える数列の任意の項をO(1)の計算量で効率よく求めることができます。