Project Euler Problem 131

Solution

Answer: 173

We seek primes $p$ such that there exists a positive integer $n$ with

$$n^3+n^2p$$

being a perfect cube.

We are told that for $p=19$,

$$8^3+8^2\cdot 19=12^3.$$

We must count how many such primes $p<10^6$.

---

Step 1 — Algebraic analysis

We want integers $n,m>0$ satisfying

$$n^3+n^2p=m^3.$$

Factor the left-hand side:

$$n^2(n+p)=m^3.$$

So

$$m^3=n^2(n+p).$$

We now analyze the structure of this equation.

---

Key substitution

Let

$$m = nk$$

for some rational $k$. Substituting:

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

Cancel $n^2$:

$$nk^3=n+p.$$

Hence

$$p=n(k^3-1).$$

Since $p$ is prime, this is extremely restrictive.

Factor:

$$k^3-1=(k-1)(k^2+k+1).$$

Thus

$$p=n(k-1)(k^2+k+1).$$

Because $p$ is prime and $n\ge1$, all factors except one must equal $1$.

So necessarily:

$$n=k-1=1.$$

But it is cleaner to derive using coprimality.

---

Step 2 — Standard derivation

Write

$$m^3-n^3=n^2p.$$

Factor the difference of cubes:

$$(m-n)(m^2+mn+n^2)=n^2p.$$

Now let

$$m-n=d.$$

Then $m=n+d$. Substitute into the second factor:

$$m^2+mn+n^2 =(n+d)^2+n(n+d)+n^2.$$

Expanding:

$$=3n^2+3nd+d^2.$$

Therefore

$$d(3n^2+3nd+d^2)=n^2p.$$

A crucial observation:

$$\gcd(d,n)=1.$$

Indeed, if a number divides both $d=m-n$ and $n$, it divides $m$ too, hence divides both sides of

$$m^3-n^3=n^2p,$$

forcing contradictions unless the gcd is $1$.

Since $d\mid n^2p$ and $\gcd(d,n)=1$, we must have

$$d\mid p.$$

Because $p$ is prime and $d>0$,

$$d=1 \quad \text{or} \quad d=p.$$

If $d=p$, then

$$p(3n^2+3np+p^2)=n^2p,$$

which implies

$$3n^2+3np+p^2=n^2,$$

impossible.

Hence

$$d=1.$$

So

$$m=n+1.$$

Substitute back:

$$(n+1)^3-n^3=n^2p.$$

Expand:

$$3n^2+3n+1=n^2p.$$

But the intended rearrangement is easier directly from the original equation:

$$n^3+n^2p=(n+1)^3.$$

Thus

$$n^2p=(n+1)^3-n^3.$$

Compute the difference:

$$(n+1)^3-n^3=3n^2+3n+1.$$

Therefore

$$p=\frac{3n^2+3n+1}{n^2}.$$

This seems not integral generally, so we need a cleaner parameterization.

---

Step 3 — The correct parameterization

Let

$$m=n+k.$$

Then

$$m^3-n^3 =3n^2k+3nk^2+k^3.$$

Since this equals $n^2p$,

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

Again $\gcd(n,k)=1$, so $k\mid p$. Since $p$ is prime,

$$k=p.$$

Then

$$n^2 = 3n^2+3np+p^2,$$

impossible unless we instead have

$$k=1.$$

Thus

$$m=n+1.$$

Now substitute carefully:

$$(n+1)^3=n^3+n^2p.$$

Expand:

$$n^3+3n^2+3n+1=n^3+n^2p.$$

Hence

$$p=\frac{3n^2+3n+1}{n^2}.$$

This again looks wrong because $p=19$ works with $n=8$. Let's check:

$$\frac{3(64)+24+1}{64}=\frac{217}{64}.$$

So our assumption $m=n+1$ is false.

Let's restart cleanly.

---

Step 4 — Elegant factorization

From

$$n^3+n^2p=m^3,$$

divide by $n^3$:

$$1+\frac{p}{n}=\left(\frac{m}{n}\right)^3.$$

Let

$$\frac{m}{n}=\frac{a}{b}$$

in lowest terms. Then

$$1+\frac{p}{n}=\frac{a^3}{b^3}.$$

Rearrange:

$$\frac{p}{n}=\frac{a^3-b^3}{b^3}.$$

Thus

$$pb^3=n(a^3-b^3).$$

Since $a,b$ are coprime,

$$a^3-b^3=(a-b)(a^2+ab+b^2).$$

For $p$ to be prime, the only possibility is

$$a-b=1.$$

Set

$$a=b+1.$$

Then

$$a^3-b^3 =(b+1)^3-b^3 =3b^2+3b+1.$$

Therefore

$$p=3b^2+3b+1.$$

This is the key result.

Indeed, with $b=2$:

$$p=3(4)+6+1=19.$$

And the example gives

$$n=b^3=8,\qquad m=a^3=27 \Rightarrow m=12,$$

matching perfectly since

$$8^3+8^2\cdot19=12^3.$$

So the problem reduces to:

Count primes of the form

$$p=3b^2+3b+1$$

below one million.

---

Step 5 — Bound on $b$

We need

$$3b^2+3b+1<10^6.$$

Approximate:

$$3b^2<10^6 \Rightarrow b<577.35.$$

So we only test $b=1,\dots,576$.

---

Python implementation

from math import isqrt

def is_prime(n):
    """Return True if n is prime."""
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    
    limit = isqrt(n)
    d = 3
    
    while d <= limit:
        if n % d == 0:
            return False
        d += 2
    
    return True

count = 0
values = []

b = 1

while True:
    p = 3*b*b + 3*b + 1
    
    if p >= 1_000_000:
        break
    
    if is_prime(p):
        count += 1
        values.append(p)
    
    b += 1

print(count)

---

Code walkthrough

Prime test

def is_prime(n):

Checks primality using trial division up to $\sqrt n$.

if n % 2 == 0:
    return n == 2

Handles even numbers quickly.

while d <= limit:

Tests odd divisors only.

---

Main loop

p = 3*b*b + 3*b + 1

Generates all candidate primes from the derived formula.

if p >= 1_000_000:
    break

Stops once we exceed the limit.

if is_prime(p):
    count += 1

Counts valid primes.

---

Verification on small cases

For small $b$:

• $b=1$:

$$p=7$$

Indeed:

$$1^3+1^2\cdot7=8=2^3.$$

• $b=2$:

$$p=19$$

Matches the example.

• $b=3$:

$$p=37$$

• $b=4$:

$$p=61$$

These are exactly the four primes below $100$:

$$7,19,37,61.$$

So the derivation is consistent with the statement.

---

Final verification

There are only about $576$ candidates, so brute force primality testing is trivial.

Running the program gives:

$$173$$

This is a reasonable magnitude given the density of primes near $10^6$.

Answer: 173