Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
communitycreator
project euler

Project Euler: Prime cube partnership

Hammad Qayyum

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 n3+n2pn^3 + n^2 * p is a perfect cube.

For example, when p=19,83+8219=123.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

To solve this problem, let’s start with the following equation:

In the equation above, kk is the perfect prime and pp is prime.

Now, let’s simplify this equation:




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

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

  • n=x3n = x^3
  • p+n=y3p + n = y^3

Both xx and yy belong to the integer set.

Also,

  • p+n=y3p + n = y^3
  • p=y3np = y^3 - n
  • p=y3x3p = y^3 - x^3
    So pp 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 yxy-x is a factor of pp, which means pp is divisible by yxy-x. However, if we want pp to be prime, then yxy-x must be equal to 1.

yx=1y - x = 1

This indicates that xx and yy 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 pp is below one million (1000000).
For i=577i = 577, we get p=57835773=100519p = 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 173173 as the number of primes with this property.

RELATED TAGS

python
communitycreator
project euler
RELATED COURSES

View all Courses

Keep Exploring