Project Euler Problem 131

# Statement

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, 83 + 8219 = 123.

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?

# Solution

(1)
\begin{eqnarray} n^3 + n^2 p & = & y^3 \\ n^2 (n + p) & = & y^3 \\ \end{eqnarray}

As p is prime then the only way that $n^2 (n + p)$ is a cube is that both $n^2$ and $(n + p)$ are cubes. So p is the difference of 2 cubes:

(2)
\begin{eqnarray} a^3 - b^3 & = & p \\ (a - b) (a^2 + ab + b^2) & = & p \\ \end{eqnarray}

The only way that p can be prime is if $a - b = 1$, so p must be the difference of two consecutive cubes. We only need to check which of those are primes until the difference is greater than 1 million.

from CommonFunctions import find_primes_less_than
from itertools import count, takewhile

primes = find_primes_less_than(int(1000000 ** 0.5))

def is_prime(n):
limit = n ** 0.5
for p in primes:
if p > limit:
return True
if n % p == 0:
return False
return True

if __name__ == '__main__':
result = sum(1 for i in
takewhile(
lambda x: x < 1000000,
((i + 1) ** 3 - i ** 3 for i in count(1))
)
if is_prime(i)
)
print("The result is:", result)