프로젝트 오일러 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\) 이 소수가 아님을 보이면 된다. 

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