뉴먼-콘웨이 수열(Newman-Conway Sequence)의 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

즉, 첫 번째 항과 두 번째 항은 1로 고정되며, 세 번째 항부터는 위 점화식을 이용해 순차적으로 계산됩니다.

알고리즘

뉴먼-콘웨이 수열의 n번째 항까지 출력하는 절차는 다음과 같습니다.

START
Step 1 -> 변수 n 입력 (예: 20)
Step 2 -> 변수 i와 배열 p[n+1] 선언 후, p[1] = 1, p[2] = 1로 초기화
Step 3 -> i = 3부터 i <= n까지 반복
   p[i] = p[p[i - 1]] + p[i - p[i - 1]] 계산
   p[i] 출력
Step 4 -> 반복 종료
STOP

이 방식은 이미 계산된 값을 배열에 저장해 두고 참조하기 때문에, 전체 시간 복잡도는 O(n)으로 매우 효율적입니다.

C 언어 구현 예제

#include<stdio.h>
int main() {
   int n = 20, i;
   int p[n + 1];
   p[1] = 1;
   p[2] = 1;
   printf("Newman-Conway Sequence is :");
   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;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 출력 결과를 확인할 수 있습니다.

Newman-Conway Sequence is :1 1 2 2 3 4 4 4 5 6 7 7 8 8 8 8 9 10 11 12

출력 결과에서 볼 수 있듯이, 뉴먼-콘웨이 수열은 특정 값이 연속해서 여러 번 나타나는 패턴을 보입니다. 이러한 특성 때문에 조합론 및 수열 분석 분야에서 다양하게 활용됩니다.