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

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

Written by on 12 January 2013

Topics: Project Euler

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.

4 Comments For This Post I'd Love to Hear Yours!

  1. Jean-Marie Hachey says:

    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)

  2. Michael Foo Bar says:

    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?

  3. Kristian says:

    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.

  4. Ke Yang says:

    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 Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.