프로젝트 오일러 51번

얼마전에 project euler 라는 사이트를 알게 되었고, 프로그래밍 연습도 할 겸 해서 한 문제씩 풀고 있다. 재미있게 여러 가지 연습을 해 볼 수 있어서 좋다고 생각한다. 대부분의 문제가 간단하게 풀리지만 어떤 경우는 오랜 시간 생각을 많이 해야만 풀리는 문제도 있는데, 51번 문제가 그러했다. 프로젝트 오일러 사이트에서 다른 사람들을 위해서 정답을 공개하지는 말라는 당부가 있었기에 여기서는 문제를 풀기 위한 힌트를 제공하려고 한다.

51번 문제는 다음과 같다.

By replacing the 1^st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3^rd and 4^th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

예를 통해서 문제를 설명하는게 편할것 같다.

56003, 56113, 56333, 56443, 56663, 56773, 56993

위 숫자들은 첫 번째 , 두 번째, 다섯 번째 자리가 각각 5, 6, 3으로 고정되어 있고, 세 번째, 네 번째 자리가 같은 숫자들로 이루어진 소수들이다. (56223, 56553, 56883 은 소수가 아니다) 즉, 세 번째 네 번째 자리가 0~9로 채워질 때, 소수가 되는 것이 7개가 되는 경우이다. 

이와 같이 일정 부분이 특정한 숫자로 고정되어 있고, 나머지 부분들은 0~9까지 같은 숫자들로 이루어져 있는 소수들을 8개 찾으려고 한다. 8개 소수 들 중 가장 작은 수를 찾아라. (위의 예에서 7개의 소수는 조건을 만족시키면서 7개의 소수를 만들 때 가장 작은 수들이고, 그 중 최솟값은 56003이 된다)

처음에는 이 문제가 그냥 무식하게 접근하여 하나씩 체크하면 되는 문제인지 알았다. 그러나 그렇게 접근하였더니 밤새도록 컴퓨터를 돌려도 결과가 나오지 않는 것이었다. 뭔가 다른 방법이 없을까 나름 오랫동안 고민을 하여 몇 가지 힌트가 될만한 단서들을 찾아내었고, 그걸 통해서 이 문제를 풀 수 있었다.

1. 0부터 9까지의 수가 반복되는 자리의 개수는 \(3, \; 6, \; 9, \; \cdots \) 즉 3의 배수가 된다.

우리는 어떤 숫자가 3의 배수가 되기 위해서는 그 수의 각 자리의 숫자의 합이 3의 배수가 되어야 한다는 것을 알고 있다.

0~9까지의 수가 반복되는 자리의 수가 \(n\) 개 라고 해 보자. 정수의 분류에 의해서 \(n=3k, \; n=3k+1, \; n=3k+2\) 중 어느 하나가 될 것이다. 이 \(n\) 개의 자리가 0~9의 숫자들로 채워진다면 이 자리에 오게 되는 숫자들의 합은 다음과 같을 것이다.

\(n=3k+1\) 인 경우	\(n=3k+2\) 인 경우
\(0 \times (3k+1)=0\)	\(0 \times (3k+2)=0\)
\(1 \times (3k+1)=3k+1\)	\(1 \times (3k+2)=3k+2\)
\(2 \times (3k+1)=3(2k)+2\)	\(2 \times (3k+2)=3(2k+1)+1\)
\(3 \times (3k+1)=3(3k+1)\)	\(3 \times (3k+2)=3(3k+2)\)
\(4 \times (3k+1)=3(4k+1)+1\)	\(4 \times (3k+2)=3(4k+2)+2\)
\(5 \times (3k+1)=3(5k+1)+2\)	\(5 \times (3k+2)=3(5k+3)+1\)
\(6 \times (3k+1)=3(6k+2)\)	\(6 \times (3k+2)=3(6k+4)\)
\(7 \times (3k+1)=3(7k+2)+1\)	\(7 \times (3k+2)=3(7k+4)+2\)
\(8 \times (3k+1)=3(8k+2)+2\)	\(8 \times (3k+2)=3(8k+5)+1\)
\(9 \times (3k+1)=3(9k+3)\)	\(9 \times (3k+2)=3(9k+6)\)

두 가지 모두 3의 배수, 3으로 나누어 1남는 수, 3으로 나누어 2 남는 수가 3개 이상씩 등장하는 것을 볼 수 있다. 이것은 고정된 자리에 오는 숫자들의 합을 3으로 나눈 나머지가 얼마이든지 최종적으로 만들어지는 수에는 3의 배수가 3개 이상 존재한다는 것을 보여준다. 즉, 소수가 최대 7개 까지가 생긴다는 것을 알 수 있다.

반면에 고정되지 않고 반복되는 자리에 오는 숫자들의 합이 3의 배수이고, 고정된 자리에 오는 숫자들의 합이 3의 배수가 아니라면 8개 이상의 소수가 만들어지는 것이 가능하다는 것을 알 수 있다.

따라서 고정되지 않고 반복되는 자리의 개수는 3의 배수가 되어야 마땅하다. 우리는 이러한 수 들의 무리 중에 가장 작은 수를 찾는 것이므로 0~9가 반복되는 자리의 개수는 3개 라고 가정하고 찾기 시작하는 것이다.

2. 마지막 자리(1의 자리)는 반드시 고정된 숫자가 오는 자리이다.

마지막 자리가 고정된 수가 오지 않고 0~9까지의 수가 오는 자리라면 1의 자리에 최소한 0, 2, 4, 8 이 놓이게 되는데, 이런 수들은 모두 짝수이므로 소수가 될 수가 없다. 10개의 수 중 이미 짝수가 6개 라면  8개의 소수를 만드는 것은 불가능하다.

이 두 가지 힌트를 가지고 문제를 접근하게 되면 좀 더 빠르게 문제를 해결할 수 있을 것이다.

먼저 고정되지 않고 반복되는 자리가 어디인지 결정하고 그 자리의 숫자들이 각각 0에서 9인 수들을 다 걸러낸다.

걸러낸 수들에서 나머지 고정된 자리의 숫자들이 같은 것끼리 모아 그 숫자가 8개 이상이 되는 것 중 가장 작은 수가 이 문제의 정답이다.

물론 각각의 숫자가 소수인지는 체크해야만 한다.