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)

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License