EKG 수열이란 다음과 같은 규칙을 만족하는 양의 정수들이 중복되지 않게 이루어져 있는 수열이다.

처음 두개의 항은 1과 2이다. EKG[n] 은 'EKG[n-1]과 1보다 큰 공약수를 갖는 자연수 중 지금까지 나오지 않은 가장 작은 자연수'이다.

그러므로 세번째 항은 4이고 그 다음 항은 6이다.

그리고 다음에는 3이 나오게 된다.

따라서 수열은 다음과 같이 완성된다.

1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11, 33, 27 ...

이 수열은 불규칙적인거 가진 것 처럼 보이지만 두 가지의 특징을 가지고 있다.

하나는 모든 자연수가 이 수열에 포함된다는 것이고 다른 하나는 모든 소수(prime number)는 오름차순으로 존재한다라는 것이다.

우리가 해야 할 것은 어떤 자연수 n이 주어졌을 때, n이 EKG 수열에서 몇 번째로 나타나는지를 구하는 것이다.

EKG 수열 timer 1s memory 128MB

EKG 수열 1s 128MB