Related Tags

python
communitycreator
project euler

Project Euler: Prime cube partnership

Problem statement

The Project Euler prime cube partnership problem states:

"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 * 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?"

Problem source: https://mnageswar.blogspot.com/-

Solution

In the equation above, $k$ is the perfect prime and $p$ is prime.

Now, let’s simplify this equation:

From the calculation above, we can conclude that if $k$ is an integer, then $n$ and $n + p$ must be perfect cubes because both terms are under the cube root formula.

Now, if both $n$ and $n+p$ are perfect cubes, then we can replace both of them with new terms, as shown below:

• $n = x^3$
• $p + n = y^3$

Both $x$ and $y$ belong to the integer set.

Also,

• $p + n = y^3$
• $p = y^3 - n$
• $p = y^3 - x^3$
So $p$ is the difference between 2 cubes.

The difference between cube formulas can also be written as follows:

From the equation above, we can see that the term $y-x$ is a factor of $p$, which means $p$ is divisible by $y-x$. However, if we want $p$ to be prime, then $y-x$ must be equal to 1.

$y - x = 1$

This indicates that $x$ and $y$ are two consecutive numbers because their difference is 1.

We can rewrite the equation above as follows:

Now, we only need to check the following equation for which value of $p$ is below one million (1000000).
For $i = 577$, we get $p = 578 ^3 - 577 ^3 = 100519$, which is greater than 1 million.

Code

To write the code, we only need to check the values up to 577 because values greater than 577 do not satisfy the equation.

We can find the solution with the following code:

#include <iostream>
using namespace std;

bool isprime(int number) {
bool ans = true;
if (number == 0 || number == 1) {
ans = false;
}
else {
for (int i = 2; i <= number / 2; ++i) {
if (number % i == 0) {
ans = false;
break;
}
}
}
return ans;
}

int main() {
int res = 0;
for (int i = 1; i < 577; i++) {
int cube1 = (i + 1) * (i + 1) * (i + 1);
int cube2 = i * i * i;
if (isprime( cube1  - cube2))
res++;
}
cout << res << endl;

return 0;
}

The code above gives the answer $173$ as the number of primes with this property.

RELATED TAGS

python
communitycreator
project euler

CONTRIBUTOR

RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time