C++で数列 0, 2, 1, 3, 1, 5, 2, 7, 3… のN番目の項を求めるプログラム

この記事では、数値Nが与えられたときに、数列 0, 2, 1, 3, 1, 5, 2, 7, 3… のN番目の項をC++で求めるプログラムを紹介します。

問題の概要

今回扱う数列は次のとおりです。

0, 2, 1, 3, 1, 5, 2, 7, 3…（N番目の項を求める）

この数列のN番目の項を求めるには、まず数列の一般項（規則性）を見つけ出し、それをもとにN番目の項を計算します。

入出力の例

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

入力： N = 7

出力： 2

解き方のアプローチ

この問題を解くには、数列の一般項を導き出す必要があります。一見ランダムに見えるこの数列ですが、注意深く観察すると、実は2つの異なる数列が交互に並んでいることがわかります。この種の「混合数列」は最初は混乱しやすいのですが、構造に気づいてしまえば一般項を求めるのは簡単です。

具体的には、偶数番目の項と奇数番目の項に、それぞれ別の数列が隠れています。それぞれを分離して見てみましょう。

偶数番目の項の数列：0, 1, 1, 2, 3, …

奇数番目の項の数列：2, 3, 5, 7, …

こうして分けてみると、偶数番目の数列はフィボナッチ数列、奇数番目の数列は素数列であることが明確になります。

したがって、この数列の一般項は次のようにまとめられます。

• Nが奇数の場合： (N/2)番目のフィボナッチ数
• Nが偶数の場合： (N/2)番目の素数

解法の動作を示すプログラム

#include <iostream>
using namespace std;

// n番目の素数を求める関数
int findNthPrimeTerm(int n) {
   int primeCount = 0;
   for (int i = 2; ; i++) {
      int isPrime = 1;
      for (int j = 2; j <= (i / 2); j++) {
         if (i % j == 0) {
            isPrime = 0;
            break;
         }
      }
      if (isPrime)
         primeCount++;
      if (primeCount == n) {
         return i;
      }
   }
   return -1;
}

// n番目のフィボナッチ数を求める関数
int FibonacciNthTerm(int n) {
   int nthTerm = 1, last = 0;
   if (n == 0)
      return 0;
   else if (n == 1)
      return 1;
   else {
      for (int i = 2; i <= n; i++) {
         nthTerm += last;
         last = nthTerm - last;
      }
      return nthTerm;
   }
}

// N番目の項を求める関数
int findNthTerm(int N) {
   if (N % 2 == 0)
      return findNthPrimeTerm(N / 2);  // 偶数なら素数
   else
      return FibonacciNthTerm(N / 2);  // 奇数ならフィボナッチ数
}

int main() {
   int N = 13;
   cout << N << "番目の項の値は " << findNthTerm(N) << endl;
   N = 4;
   cout << N << "番目の項の値は " << findNthTerm(N);
   return 0;
}

出力結果

13番目の項の値は 8
4番目の項の値は 3

コードの解説

このプログラムは、次の3つの関数で構成されています。

findNthPrimeTerm()： 2から順に数値をチェックし、2からi/2までのいずれの数でも割り切れない数を素数としてカウントしていき、n番目の素数を返します。

FibonacciNthTerm()： ループによる反復計算でn番目のフィボナッチ数を求めます。再帰を使わないため、大きなnでも効率的に動作します。

findNthTerm()： Nを2で割った余りを判定し、偶数なら素数を求める関数、奇数ならフィボナッチ数を求める関数へ処理を振り分けます。

まとめ

一見すると規則性がわかりにくい数列でも、偶数番目と奇数番目に分けて観察することで、フィボナッチ数列と素数列が交互に並んだ「混合数列」であることが判明しました。この種の問題では、まず数列を分解してそれぞれの規則性を確認するのが有効なアプローチです。ぜひ本記事のサンプルコードを参考に、実際に動かして挙動を確かめてみてください。