프로젝트 오일러 146번

The smallest positive integer $n$ for which the numbers $n^2 +1$, $n^2 +3$, $n^2+7$, $n^2+9$, $n^2+13$, and $n^2+27$ are consecutive primes is $10$. The sum of all such integers $n$ below one-million is $1242490$.

What is the sum of all such integers $n$ below $150$ million?

---

 $n^2 +1$, $n^2 +3$, $n^2+7$, $n^2+9$, $n^2+13$, $n^2+27$ 이 연속적인 소수가 되는 최소의 자연수 $n$ 은 $10$ 이다. $10^6$ 미만의 수 중 위의 조건을 만족하는 자연수들의 총합은 $1242490$ 이다.

$15 \times 10^7$ 미만의 수 중 위 조건을 만족하는 모든 자연수들의 총합은 얼마일까?

소수 $m$ 에 대하여 $n=mk+r$ 라고 하자. (단, $k$ 는 정수, $r=0,\; 1,\; 2,\; \cdots, \; m-1$)

$n^2 = m^2k^2 + 2mkr + r^2$ 이므로 $n^2 +1$, $n^2 +3$, $n^2+7$, $n^2+9$, $n^2+13$, $n^2+27$ 중 $m$ 으로 나누어 떨어지는 놈이 있으면 그 놈은 소수가 아니게 된다. 따라서 $r$ 의 값을 변화시키면서 $n^2 +1$, $n^2 +3$, $n^2+7$, $n^2+9$, $n^2+13$, $n^2+27$ 들 중 하나라도 소수가 아닌 것이 나오게 하는 것들을 제외한다. 예를 들어, $m=3$ 이라고 하면 $n$ 은 $3k,\; 3k+1, \; 3k+2$ 중 어느 하나로 표현될 것이다. $n=3k$ 이라면 $n^2+3$ 이 $3$ 의 배수가 되기 때문에 $n^2+3$이 소수라는 조건에 위배된다. $n=3k+1$ 이라면 $n^2 +1$, $n^2 +3$, $n^2+7$, $n^2+9$, $n^2+13$, $n^2+27$ 중 어느 것도 $3$의 배수가 되지 않으므로 살려두고, $n=3k+2$ 일 때도 어느 것도 $3$ 의 배수가 되지 않으므로 살려둔다. 따라서 우리는 $n=3k+1, \; n=3k+2$ 인 경우들만 확인하면 된다. 즉, $n^2$ 을 $3$ 으로 나누었을 때 나머지가 $1$ 인 $n$ 들에 대해서만 조사하면 된다. 

이런 식으로 소수들에 대해서 조사해야할 것들만 조사하면 

$m=2$ 인 경우는 $n^2$ 을 $2$로 나눈 나머지가 $0$ 인 경우만을,

$m=3$ 인 경우는 $n^2$ 을 $3$ 으로 나눈 나머지가 $1$ 인 경우만을,

$m=5$ 인 경우는 $n^2$ 을 $5$ 로 나눈 나머지가 $0$ 인 경우만을,

$m=7$ 인 경우는 $n^2$ 을 $7$ 로 나눈 나머지가 $2$ 인 경우만을,

$m=11$ 인 경우는 $n^2$ 을 $11$ 로 나눈 나머지가 $0, \;1, \; 3, \; 5$ 인 경우만을,

$\vdots$

조사하면 된다. 즉, $n$ 값을 변화시키면서 위에 해당하지 않는 경우는 조사하지 않고 통과하면 되는 것이다. 위의 결과로 본다면 $n$ 은 $2$ 의 배수이면서, 동시에 $5$ 의 배수이어야 하므로 $10$ 의 배수가 된다. 따라서 $10$ 의 배수들 중, $n$ 이 $2, \;5$ 를 제외한 나머지 소수들에 대한 조건을 만족시킬 때만 조사하면 되는 것이다.

문제는 소수 $m$ 을 어디까지 고려해야 하는 것인데, 이 부분에 대해서는 시행 착오를 거치면서 직접 알아보는 것이 좋겠다. 몇 개를 고려하는지에 따라 답이 나오는 속도가 달라진다.

또한 $n^2 +1$, $n^2 +3$, $n^2+7$, $n^2+9$, $n^2+13$, $n^2+27$ 가 연속적인 소수여야 한다는 조건을 확인해야 하는데, 그러기 위해서는 위의 수들이 소수임을 보여야 하며 동시에 $n^2+5$, $n^2+11$, $n^2+15$, $n^2 + 17$, $n^2+19$, $n^2+21$, $n^2+23$, $n^2+25$ 가 소수가 아님을 보이면 된다.

그런데 이미 $n^2$ 이(5\) 의 배수임을 알고 있기 때문에 $n^2+5$, $n^+15$, $n^2+25$ 는 소수가 아님을 알 수 있다. 또한 $n^2$ 을 $3$ 으로 나눈 나머지가 $1$ 이라는 것을 알고 있기 때문에 $n^2+11$, $n^2+17$, $n^2+23$ 은 $3$ 의 배수가 되어 소수가 아님을 알 수 있다. 결국 우리가 보여야할 것은 $n^2+19$, $n^2+21$ 이 소수가 아님을 보이면 된다. 

시간이 좀 걸리기는 하지만 답은 나온다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ ㅠㅠ