프로젝트 오일러 131번

There are some prime values, $p$, for which there exists a positive integer, $n$, such that the expression $n^3 + n^2 p$ is a perfect cube.

For example, when $p=19, \; 8^3 + 8^2 \times 19 = 12^3$.

What is perhaps most surprising is that for each prime with this property the value of $n$ is unique, and there are only four such primes below one-hundred.

How many primes below one million have this remarkable property?

---

소수 $p$ 에 대하여 $n^3 + n^2 p$ 가 어떤 수의 세제곱이 되는 자연수 $n$ 이 존재하는 경우가 있다. 예를 들어, $p=19$ 일 때, $n=8$ 이면 $8^3 + 7^2 \times 19=12 ^3$ 이 된다.

놀라운 것은 만약 어떤 소수 $p$ 에 대하여 위 조건을 만족하는 자연수 $n$ 이 존재한다면 유일하게 하나 존재한다는 것이다. $100$ 미만의 소수에 대해서 이런 조건을 만족하는 자연수 $n$ 이 존재하는 경우는 단 $4$ 개 뿐이다.

$10 ^ 6$ 미만의 소수 중 위 조건을 만족하는 자연수 $n$ 이 존재하는 소수는 몇 개나 될까?

$n^3 + n^2 p = k^3$ 이라고 해 보자. 좌변을 $n^2$ 으로 묶어주면

$n^2 (n + p) = k^3$ 

이렇게 되면 두 가지 중 하나로 생각할 수 있다.

   1. $(n+p)=nm^3$, ($m$ 은 자연수) $\to$ 그래야 $k=nm$ 이 된다.

   2. $n=a^3$ 이고 $(n+p)= b^3$ ($a, \;b$ 는 자연수) $\to$ 그래야 $k=ab$ 가 된다.

첫 번째 경우는 $1 + \dfrac{p}{n} = m^3$ 이 되는데, 우변이 자연수 이므로 좌변도 자연수여야 한다. 따라서 $\dfrac{p}{n}$ 이 자연수가 되어야 하고, $n$ 은 $p$ 의 약수 중 하나여야 한다. 그런데 $p$ 가 소수이므로 $n=1$ 또는 $n=p$ 가 되어야 하는데, $n=1$ 인 경우는 두 번째 경우에서 $a=1$ 인 경우로 보면 되니까 일단 패스.. $n=p$ 이면 $2 = m^3$ 이 되어 $m$ 이 자연수라는 조건에 위배된다. 따라서 첫 번째 경우는 그냥 패스~~~

두 번째 경우는 결국 $a^3 +p = b^3$ 이 되는데, 정리하면

$\begin{split} p &= b^3 - a^3 \\ &= (b-a) \left ( b^2 +ab+a^2 \right ) \end{split}$

이 때, $p$ 가 소수이므로 $b-a =1 , \; b^2 +ab + a^2 = p$ 이거나 $b-a = p, \; b^2 +ab + a^2 =1$ 이어야 한다. 그렇지만 $a, \;b$ 가 모두 자연수 이므로 $b^2 + ab + a^2$ 은 절대로 $1$ 이 될 수 없다. 따라서 $b-a=1, \; b^2 +ab +a^2 =p$ 가 된다.

결과적으로 $b=a+1,\; p=3a^2 + 3a + 1$ 이 된다.

따라서 $3a^2 +3a +1 < 10^6$ 을 만족하는 구간에서 자연수 $a$ 값들을 변화시켜 가며, $3a^2 + 3a +1$ 이 소수인 경우만 카운트 하면 문제의 답을 쉽게 구할 수 있다