Project Euler 131: Determining primes, p, for which n^3 + n^2p is a perfect cube.

I am pretty sure the Problem 131 of Project Euler can be brute forced. However, if you start digging you will see that there is a really beautiful solution to the problem that reads

There are some prime values, p, for which there exists a positive integer, n, such that the expression n3 + n2p is a perfect cube.

For example, when p = 19, 83 + 82x19 = 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?

If we start out with the equation

where k is a perfect cube and p is prime, then we can rewrite this as

From this is follows that if k is an integer then both n and n+p needs to be perfect cubes as well.

Since both n and n + p are cubes we can denote them and  where (meaning they are integers). Then it follows from rearranging and inserting into the second equation that  . So p is the difference of two cubes.  This difference can be written as

Since we have the factor y-x in from of the larger equation, it is obvious that p must be divisible by y-x and therefore p can only be prime if y-x = 1. So we have that p must be the difference of two consecutive cubes. Therefore all we need to check in order to solve this problem is if

is prime for any number below 1.000.000. For i = 577 we get that .

So we only need to check 577 values of i, which is pretty quickly done with the code

int result = 0;
for (int i = 1; i < 577; i++) {
    if (IsPrime((i + 1) * (i + 1) * (i + 1) - i * i * i))
        result++;
}

I can do this in 0.3ms and I get the result

Number of primes with this property: 173

As I said there is a pretty nice solution to this. I used a while to derive this I am a bit doubtful if I am presenting it in a way that is easy to follow, so don’t hesitate to ask questions regarding the solutions or explanation.You can find the the source code here.

Posted by Kristian

4 comments

Jean-Marie Hachey

Table 1
Determination x and p for which x^3 + (x^2) p is a perfect cube.
(x: natural number, p: prime or composite number).

http://img692.imageshack.us/img692/2541/pe131tableone.jpg

Determination of the variables x, p and k in the equation:
x^3 + (x^2)p = k^3
(x: natural number; p: prime number or composite number)
Table 1 was generated in part from the equation:
(x+1)^3 – (x^3) = p
Determination of n:
Table 1 shows that n can be related to the rank of the line (x) at power 3.
So for 1, 2, 3, 4 and 5 we get: 1, 8, 27, 64 and 125 respectively.
Determination of p:
In the table, we see that p is equivalent to [(x+1)^3 – (x^3)].
Determination of k:
From the equation:
x^3 + (x^2) x p = k^3
Also, we note that k can be determined from the table by the relation:
k=(x^2) x (x+1) (For example, for the first primes we have k= 2 [i.e. (1^1) x 2] ; k=12,[i.e. (2^2) x 3]; etc…

___

Table 2
Variables in equation: [(n^3) + (n^2) x p = k^3]

http://img255.imageshack.us/img255/1748/pe131table2.jpg

_____

Sources:

1) Project Euler 131
Kristian’s algorithm
http://www.mathblog.dk/files/euler/Problem131.cs

2) Microsoft Visual C# 2010 Express

3) Microsoft Office Excel (2007)

Michael Foo Bar

Sorry, but I don’t understand the part where you conclude that n and n+p have to be cubes as well. Can you explain that a little bit more detailed? Assumed they were no cubes, you would have a fraction of two irrational numbers there, but that fraction could still be a rational or natural number. What am I missing?

It is a long time since I solved this, but I think this explanation holds.

If n+p and n are irrational numbers, in order for it to be a fraction or integer it would mean that we can factor out a perfect cube of both n and n+p and the same irrational leftover such that it cancels out.

In order to factor something out of p +n it must divide both p and n, and thus it must be p. And therefore n must be divisible by p.

In that case we can write (p+n)/n as (1+m)/m where n=pm, and m and m+1 are always co-primes, so we can’t factor a common thing out of them. Therefore we cannot make a fraction of perfect cubes (ending up being a fraction) and an irrational part. But rather we only have two irrational parts which are not the same and thus wont cancel out and become rational.

Quote “Since we have the factor y-x in from of the larger equation, it is obvious that p must be divisible by y-x and therefore p can only be prime if y-x = 1.”
I’ll explain it and use a,b to replace x,y.
I think this is incorrect.
//a3 – b3 = b2p
//a3 – b3 = (a – b)(a2+ ab + b2)
// p=(a-b)(a2+ab+b2)/b2=(a-b)[(a/b)2+a/b+1]
// given p is a prime number, a and b are positive integers
// if [(a/b)2+a/b+1] is an integer, it’s obviously larger than 1, so it has to be 2 because p is a prime number
// thus (a/b)2+a/b + 1 =2 -> say if a/b=x -> x2+x-1=0 (x must be a real number), delta=sqrt(5), the solution of x, however is not a real number,
// so [(a/b)2+a/b+1] is not 2 or any integer

Leave a Reply