2월의 퍼즐에 참여해주신 모든 분들께 감사드립니다!
어려운 퍼즐이었음에도 불구하고 정답과 함께 좋은 풀이를 보내주신 이대근님께 Horizon에서 준비한 선물을 전달드릴 예정입니다.
2의 거듭제곱을 차례로 구하여 보면, 한 자리 수인 1, 2, 4, 8은 모두 2의 거듭제곱이 품은 수가 되어야 한다. 다음 차례인 16은 1을 포함하고 있고, 32는 2를 포함하고 있고, 64는 4를 포함하고 있다. 이렇게 생각하면, 128, 256, 512, 1028, 2048, 4096, 8192, 16384, 32768은 모두 1, 2, 4, 8 가운데 하나를 품고 있다.
그 다음 거듭제곱수인 \(2^{16} = 65536\)은 1, 2, 4, 8 가운데 어느 것도 품고 있지 않으므로, 65536 자신이 2의 거듭제곱이 품은 수가 되어야 한다. 그 다음으로 1, 2, 4, 8을 품지 않은 2의 거듭제곱수는 아직까지 발견되고 있지 않아서, 아마도 더 이상 다른 수는 필요하지 않을 것으로 보인다.
이 문제는 J. Shallit의 논문 Minimal Primes, J. Recreational Math. 30 (2000), 113-117에서 처음 제시된 것으로 자연수의 어떤 무한집합 \(S\)에 대해서도, \(S\)의 적당한 유한 부분집합 \(M\)이 존재하여, \(S\)의 어떤 원소도 \(M\)의 원소 가운데 하나를 품고 있음이 증명되어 있다. \(S\)가 소수의 집합인 경우 \(M\)은 26개의 소수로 이루어진 집합이고 이것을 `극소 소수minimal primes‘라 불렀다. Shallit은 극소 소수 외에도 극소 합성수를 구하였고, 극소 2의 거듭제곱수가 1, 2, 4, 8, 65536일 것으로 추측하였다.
비록 이 추측이 증명되지는 않았지만 이 퍼즐이 묻고 있는 것이 바로 Shallit의 추측이므로 정답은
1, 2, 4, 8, 65536
이다.
