ニューマン・コンウェイ数列の第n項までを出力する方法

ニューマン・コンウェイ数列とは

ニューマン・コンウェイ数列(Newman-Conway Sequence)は、以下のような整数列を生成するために用いられる数列です。

1 1 2 2 3 4 4 4 5 6 7 7 8 8 8 8 9 10 11 12

この数列は、漸化式によって定義される点が大きな特徴です。各項は、それ以前の項を再帰的に参照して求められます。

生成に使う漸化式

n番目のニューマン・コンウェイ数列を求めるための式は次のとおりです。

P(n) = P(P(n - 1)) + P(n - P(n - 1))
ただし、P(1) = P(2) = 1

初期条件として最初の2項が1であることが決まっており、3項目以降は上記の漸化式に従って順番に計算していきます。

アルゴリズム

ニューマン・コンウェイ数列を計算する手順は以下のようになります。

1. 変数 n の値を入力として受け取る(例：20)
2. 変数 i、配列 p[n+1] を用意し、p[1] = 1、p[2] = 1 を設定する
3. i = 3 から n になるまで繰り返し処理を行う
   • p[i] = p[p[i - 1]] + p[i - p[i - 1]] を計算して代入する
   • p[i] の値を出力する
4. ループ終了後に処理を完了する

C言語による実装例

以下は、C言語でニューマン・コンウェイ数列の第20項までを出力するプログラム例です。

#include<stdio.h>
int main() {
    int n = 20, i;
    int p[n + 1];
    p[1] = 1;
    p[2] = 1;
    printf("ニューマン・コンウェイ数列:");
    printf("%d %d ", p[1], p[2]);
    for (i = 3; i <= n; i++) {
       p[i] = p[p[i - 1]] + p[i - p[i - 1]];
       printf("%d ", p[i]);
    }
    return 0;
}

このプログラムでは、まず配列の先頭2要素に初期値1を代入し、その後for文で3項目以降を漸化式に基づいて順次計算しています。計算済みの項を配列に保存しておくことで、再帰的な参照を効率よく処理できる点がポイントです。

実行結果

上記のプログラムを実行すると、次の出力が得られます。

ニューマン・コンウェイ数列:1 1 2 2 3 4 4 4 5 6 7 7 8 8 8 8 9 10 11 12

まとめ

ニューマン・コンウェイ数列は、自分自身の値をインデックスとして再帰的に参照するユニークな漸化式で定義される整数列です。動的計画法の考え方を使い、計算した値を配列に格納しながら進めることで、シンプルなループ処理だけで効率的に任意のn項目までを求めることができます。