프로젝트 오일러 128번

A hexagonal tile with number \(1\) is surrounded by a ring of six hexagonal tiles, starting at "12 o'clock" and numbering the tiles \(2\) to \(7\) in an anti-clockwise direction.

New rings are added in the same fashion, with the next ring being numbered \(8\) to \(19\), \(20\) to \(37\), \(38\) to \(61\), and so on. The diagram below shows the first three rings.

By finding the difference between tile \(n\) and each of its six neighbors we shall define \({\rm PD}(n)\) to be the number of those differences which are prime.

For example, working clockwise around tile \(8\) the differences are \(12, \;29,\;11,\;6,\;1,\) and \(13\). So \({\rm PD}(8)=3\).

In the same way, the differences around tile \(17\) are \(1,\;17,\;16,\;1,\;11,\) and \(10\), hence \({\rm PD}(17)=2\).

It can be shown that the maximum value of \({\rm PD}(n)\) is \(3\).

If all of the tiles for which \({\rm PD}(n)=3\) are listed in ascending order to form a sequence, the \(10\)th tile would be \(271\).

Find the \(2000\)th tile in this sequence.

---

1이 적혀 있는 육각형 모양의 타일을 2에서 7까지 적힌 타일이 12시 방향을 시작으로 시계 반대 방향으로 링을 만들며 둘러 싸고 있다. 그 바깥쪽에 같은 방식으로 8에서 19가 적힌 타일이 또다른 링을 만들고 있으며, 그 바깥쪽에는 20에서 37까지의 타일이, 또 그 바깥쪽에는 38에서 61까지의 타일이 링을 만들며 둘러 싸고 있다. 위쪽 그림은 이과 같이 만들어지는 첫 번째에서 세 번째 까지의 링을 보여주고 있다.

이때 \({\rm PD}(n)\) 을 \(n\) 과 \(n\) 을 둘러싸고 있는 여섯 개의 수의 차 중 소수인 것의 개수를 나타내는 함수라고 정의하자. 예를 들어, 8을 둘러싸고 있는 여섯 개의 수는 20, 21, 9, 2, 19, 37 이고 이들 수와 8의 차는 가각 12, 13, 1, 6, 11, 29 이며 이들 중 소수는 13, 11, 29의 세 개이므로 \({\rm PD}(8)=3\) 이 된다. 같은 방식으로 17을 둘러싸고 있는 수들은 18, 7, 6, 16, 33, 34이고 이들 수와 17의 차는 각각 1, 10, 11, 1, 16, 17이며 이들 중 소수는 11, 17의 두 개이므로 \({\rm PD}(17)=2\)가 된다.

이런식으로 \({\rm PD}(n)\) 을 구하다보면 이 함수의 최댓값이 3이라는 것을 알 수 있다.

만약 \({\rm PD}(n)\) 이 3의 값을 갖는 \(n\) 들을 오름차순으로 나열한 수열을 생각한다면, 이 수열의 10번째 항은 271이 될 것이다.

이 수열의 2000번째 항을 구하시오.

이 문제를 처음 접했을 때, 어떤 한 숫자를 둘러싸고 있는 6개의 숫자를 찾아내는 것이 중요하다고 생각해서 그걸 나타낼 수 있는 방법을 생각했었다. 그래서 얻어낸 방법이 바로 몇 번째 링에 속하는 숫자인지, 그리고 그 링에서 몇 번째 변 (육각형이니까 6개의 변이 있다.) 위에 있는 숫자인지 혹은 몇 번째 꼭짓점에 있는 숫자인지를 알아내는 방법이었다. (변에 있는 경우와 꼭짓점에 있는 경우 둘러싸는 숫자들의 규칙이 달라지기 때문이다.)

각 링에 속하는 숫자들의 집합을 군수열로 생각하여 풀어보면 \(n\) 번째 링에는 \(3n^2 - 3n +2\) 를 시작으로 \(6n\) 개의 숫자들이 나열되게 된다. 또한 \(n\) 번째 링에서 꼭짓점들 사이의 거리는 \(n\) 이 되고 꼭짓점들 사이에는 \(n-1\) 개의 숫자가 나열된다. 이런한 규칙성 때문에 어떤 숫자 \(k\) 에 대해서 \(k\) 가 몇 번째 링에 속하는지에 대한 정보 \(n\) 과 (\(n\) 번째 링에 속한다고 할 때) \(k\)와 해당 링의 첫 번째 수인 \(3n^2 - 3n +2\) 와의 차를 \(n\) 으로 나눈 몫과 나머지만 있으면 정확하게 위치를 파악할 수 있다. 예를 들어, \(11\)의 경우 두 번째 링에 속하므로 \(n=2\) 가 되고, 두 번째 링의 첫 번째 숫자는 \(8\) 이므로 \(11-8\) 을 \(n=2\) 로 나눈 몫과 나머지는 각각 \(1, \;1\) 이 된다. 이렇게 되면 \((2, \;1,\; 1)\) 이라는 정보만으로 \(11\) 이 두 번째 링의 두 번째와 세 번째 꼭짓점 사이에 놓이는 첫 번째 숫자라는 것을 알 수 있다.

이런식으로 생각을 하고 문제를 풀다보니 여러 가지 문제점들이 발생하여 다음과 같이 네 가지 경우에 대해서 각각 따로 생각해 주어야 한다는 것을 알게 되었다. 이해를 돕기 위해서 두 번째 링을 예로 설명을 이어 가겠다. 

1. 첫 번째 꼭짓점을 제외한 나머지 꼭짓점에 놓이는 수일 경우

위 그림에서 나타내는 숫자들이 두 번째 링의 꼭짓점들에 놓이는 숫자들이다. (첫 번째 꼭짓점인 \(8\)은 따로 생각해야 하므로 일단 제외)

이 숫자들을 둘러싸는 숫자들은 바깥쪽 링에 \(3\)개, 동일한 링에 \(2\)개, 안쪽 링에 \(1\)개가 존재한다. 같은 링 안에 있는 숫자들은 각각 \(1\)씩 차이나는 숫자들이므로 이것들의 차가 소수가 될 수 없다. 따라서 우리의 관심은 바깥쪽과 안쪽 링에 있는 숫자들이다. 

숫자 \(10\)은 두 번째 링의 두 번째 꼭짓점에 놓이는 수이다. 그리고 이 수는 세 번째 링의 두 번째 꼭짓점에 놓이는 수 \(23\) 과 첫 번째 링의 두 번째 꼭짓점에 놓이는 수 \(3\) 으로 둘러싸여 있다. \(10\) 을 나타내는 방법이 두 번째 링의 첫 번째 숫자인 \(8\) 에 두 번째 링의 한 변의 길이인 \(2\) 의 \(1\) 배 만큼 더해진 숫자이므로 \(8 + (2 \times 1)\) 로 표현이 된다. 같은 방법으로 세 번째 링의 \(23\) 을 표현하면 세 번째 링의 첫 번쨰 숫자인 \(20\) 에 세 번째 링의 한 변의 길이인 \(3\)의 \(1\) 배 만큼 더해진 것이므로 \(20 + (3 \times 1)\) 이 되는 것이다. 첫 번째 링의 \(3\) 은 \( 2 + (1 \times 1)\) 이 된다.

따라서 \(10\)을 둘러싸고 있는 숫자 중 바깥쪽 링에 있는 숫자들은 \(23\)과 \(23\)의 좌우에 있는 숫자인 \(22,\; 24\) 가 되고, 안쪽 링에 있는 숫자는 \(3\) 이 된다. 설명이 무지하게 길지만 읽어보면 무슨 뜻인지는 알 수 있을 것이다.

이것을 일반화 시키면 다음과 같다. \(n\) 번째 링의 \(m\) 번째 꼭짓점에 있는 수를 나타내면 \(3n^2 -3n +2 + (n \times (m-1))\) 이고 이 숫자를 바깥쪽에서 둘러싸고 있는 수는 \(3(n+1)^2 - 3(n+1) +2 + ((n+1) \times(m-1))\)과 이 숫자의 좌우에 있는 수가 된다. 또한 안쪽에서 둘러싸고 있는 수는 \(3(n-1)^2 - 3(n-1) +2 +((n-1) \times (m-1))\) 이 된다.

이 경우 이들 네 수와의 차는 각각 \(6n+m-5,\; 6n+m-2, \; 6n+m-1,\; 6n+m\) 이 되는데 여기서 \(6n+m\) 이 짝수이든 홀수이든 관계없이 네 개의 수는 짝수 두 개와 홀 수 두 개로 이루어 지므로 절대로 소수가 \(3\)개 나올 수가 없다. (같은 링 안에서 둘러싸는 수 들은 그 차가 1이라 소수가 될 수 없고, 2를 제외한 소수는 모두 홀수이다.) 

결국 각 링의 꼭짓점에 위치한 수들에서는 조건을 만족시키는 경우가 발생하지 않으므로 조사할 필요가 없다.

  

2. 꼭짓점이 아닌 변 위에 놓이는 숫자들의 경우 (각 링의 마지막 수는 제외)

위 그림이 두 번째 링에서 꼭짓점이 아닌 변 위에 놓이는 숫자들을 나타낸다. 이때, \(19\) 는 두 번째 링의 마지막 숫자인데 이후에 따로 고려할 것이므로 일단 제외한다.

\(15\) 를 예로 들면 \(15 - 8 =7\) 을 꼭짓점 간 거리 \(2\) 로 나눈 몫 \(3\) 과 나머지 \(1\) 을 이용하여 다음과 같이 나타낼 수 있다. \(15 = 8 + (2 \times 3) + 1\)  이렇게 나타내는 것은 위에서 설명 하였으므로 대충 이해가 갈거라 생각한다.

이 경우도 마찬가지로 동일한 링에서 둘러싸는 숫자들은 그 차가 각각 1이므로 소수가 아니다. 따라서 관심의 대상은 바깥쪽 링에서 둘러싸는 숫자 \(2\) 개와 안쪽 링에서 둘러싸는 숫자 \(2\) 개다. 바깥쪽에서 \(15\) 를 둘러싸는 숫자들은 세 번째 링의 첫 번째 숫자인 \(20\) 과 몫 \(3\), 나머지 \(1\) 로 다음과 같이 나타낼 수있다. \(20 +(\3 \times 3) +1\) 과 이보다 \(1\) 큰 수이다. 또한 안쪽에서 둘러싸는 두 개의 수는 첫 번째 링의 첫 번째 수 \(2\)와 몫 \(3\), 나머지 \(1\) 을 이용하여 나타낸 \(2 + (1 \times 3) + 1\) 과 이보다 \(1\) 작은 수이다. 

이것을 일반적으로 나타내면 다음과 같다. 

\(n\) 번째 링의 \(m\) 번째 꼭짓점에서 \(r\) 만큼 더 간 수 \(3n^2 - 3n +2 +(n \times (m-1)) + r\) 을 바깥쪽과 안쪽에서 둘러싸는 수는 \(3(n+1)^2 - 3(n+1) +2 + ((n+1) \times (m-1)) + r\) 과 그보다 \(1\) 큰 수, 그리고 \(3(n-1)^2 - 3(n-1) +2 +((n-1) \times (m-1)) +r\) 과 그 본다 \(1\) 작은 수이다.

결국 이들 네 수와의 차는 \(6n+m-5, \; 6n+m-4, \;6n+m-1, \; 6n+m\) 이 되는데, 이 경우도 \(6n+m\) 이 홀수이든 짝수이든 관계없이 네 개의 수는 짝수 \(2\) 개와 홀수 \(2\) 개가 나오므로 절대로 \(3\) 개의 소수를 만들 수는 없다. 

따라서 각 링의 마지막 수를 제외한 변 위에 놓이는 수들은 조사할 필요가 없다.

3. 각 링의 첫 번째 꼭짓점에 오는 숫자들의 경우

위 그림은 두 번째링의 첫 번째 숫자인 \(8\) 을 보여주고 있다.

이 경우는 바깥쪽 링의 첫 번째 수와 두 번째 수 그리고 마지막 수로 둘러싸여 있다. 또한 같은 링에서 \(1\) 큰 수와 마지막 수로 둘러싸여 있으며, 안쪽 링의 첫 번째 수로 둘러싸여 있다.

이를 일반적으로 표현하면 다음과 같다. \(n\) 번째 링의 첫 번째 수 \(3n^2 - 3n +2\) 를 둘러싸고 있는 숫자들은 바깥쪽링의 \(3(n+1)^2 -3(n+1) +2\), \(3(n+1)^2 -3(n+1) +3\), \(3(n+2)^2 -3(n+2)+1\), 같은 링의 \(3n^2+3n+3\), \(3(n+1)^2-3(n+1)+1\), 그리고 안쪽 링의 \(3(n-1)^2 -3(n-1)+2\) 가 된다. 

이들 수와의 차는 각각 \(6n, \;6n+1, \; 6n-1, \;12n+5,\; 6n-6\) 이므로 홀수가 세 개가 되어 소수가 세 개가 될 가능성이 있다. 

따라서 각 링의 첫번째 수들은 반드시 조건을 만족하는지 조사해야 한다.

4. 각 링의 마지막에 오는 숫자들의 경우 

위 그림은 두 번째 링의 마지막 숫자인 \(19\)를 보여주고 있다.

이제 대충 보는 눈이 생겼을 것이므로 바로 일반적인 경우를 생각해 보겠다.

\(n\) 번째 링의 마지막 수 \(3(n+1)^2 - 3(n+1) +1\) 을 둘러싸는 수 중 차가 1인 바로 직전 수를 제외한 나머지 다섯 개의 수는 \(3n^2 -3n +2\), \(3n^2 -3n +1\), \(3(n-1)^2 -3(n-1)+2\), \(3(n+2)^2 -3(n+2) +1\), \(3(n+2)^2 -3(n+2)\) 가 된다. 이 수들과의 차는 \(6n+6\), \(6n+5\), \(6n-1\), \(6n\), \(12n-7\) 로 홀수가 세 개 이므로 소수가 세 개일 가능성이 있다. 따라서 이 경우도 조건을 만족하는지 조사해야 한다. 

뭔가 엄청난 문제를 푼 것 같지만, 결론은 각 링의 첫 번째 숫자와 마지막 숫자만 조사해보면 이 문제의 답을 구할 수 있게 된다. 물론 이 사실을 알기 위해서는 생각을 좀 해봐야 할 것이다. 또한 이 문제를 풀기 위해서는 계차수열과 군수열에 관한 기본적인 개념이 있어야 할 것으로 판단된다.