The primes contain arbitrarily long arithmetic progressions(BOJ: 27907번)

문제

그린-타오 정리(Green–Tao theorem)[1]는 소수 집합이 임의 길이의 등차수열을 포함한다는 정리로, 2004년에 Ben Green과 Terence Tao가 증명했다. 실제로는 이보다 조금 더 강력한 다음 명제를 증명한다:

소수 집합의 부분집합인 $A$가 $\limsup\limits_{N\to\infty}\frac{A\cap[1,N]}{N}>0$을 을 만족한다면, 모든 양의 정수 $k$에 대해 $A$가 길이 $k$인 등차수열을 무한히 많이 포함한다. 특히 $A$를 소수 집합 전체로 놓으면 소수 집합이 임의 길이의 등차수열을 포함한다.

그린-타오 정리는 세메레디의 정리(Szemerédi's theorem)[2]의 확장이라고 할 수 있다. 세메레디의 정리는 다음과 같다:

자연수 집합의 부분집합인 $A$가 $\limsup\limits_{N\to\infty}\frac{A\cap[1,N]}{N}>0$ 을 만족한다면, 모든 양의 정수 $k$에 대해 $A$가 길이 $k$인 등차수열을 무한히 많이 포함한다.
그린-타오 정리를 세메레디의 정리로부터 바로 유도할 수는 없다. 소수의 집합은 자연수에 대해 밀도가 $0$이기 때문이다. 하지만 세메레디의 정리를 확장하여 자연수 집합을 유사 난수와 관련된 특정 조건을 만족하는 집합으로 확장할 수 있고, 이 조건을 만족하면서 소수 집합을 조밀 집합(dense subset)으로 갖는 집합을 구성하여 그린-타오 정리를 증명하게 된다.

하지만 그린-타오 정리는 실제로 임의 길이의 소수 등차수열을 어떻게 구성하는지는 알려주지 않는다. 이 문제에서는 임의 길이의 소수 등차수열을 직접 구성해야 한다.

[1] Green, Ben, and Terence Tao. "The primes contain arbitrarily long arithmetic progressions." Annals of mathematics (2008): 481-547.

[2] Szemerédi, Endre. "On sets of integers containing no k elements in arithmetic progression." Acta Arith 27.299-345 (1975): 21.

입력

첫째 줄에 자연수 $n$이 주어진다.

출력

첫째 줄에 길이가 $n$이고 $3825123056546413051$이하의 소수로만 이루어진 등차수열을 출력한다. 만약 그러한 등차수열이 없으면 대신 -1을 출력한다.

제한

• $2\le n\le30$

서브태스크

번호	배점	제한
1	7	$n \le 3$
2	900	$n \le 10$
3	27000	추가 제약 조건 없음

예제 입력 1

3

예제 출력

43 37 31

노트

소수는 $1$보다 크면서, 1과 자기 자신만을 약수로 가지는 양의 정수다.

풀이

구데기컵은 별의 별 이상한 문제를 내는 곳으로 유명합니다. 근데 웬일로 정상적인 문제에 실버V라는 레이팅이 붙어 있길래 풀어보았습니다.
허나 정답을 보니 상당히 구데기스러웠습니다.
일단, 그린-타오 정리는 이 문제에서 상관이 없습니다. 그러니까, 그린-타오 정리를 이용하여 소수의 등차수열을 구하는 것은 가능하지 않습니다. 2023년 4월 30일까지 발견된 긴 소수 등차수열은 길이가 $27$인 등차수열이라고 합니다. 그렇다는 것은 이 문제에 함정이 있다는 것입니다. 사실은, 이문제는 소수 등차수열을 구하는 문제가 아니라, 공차가 $0$인 소수 수열을 출력하는 문제입니다.