Project Euler 87: Investigating numbers that can be expressed as the sum of a prime square, cube, and fourth power?

Project Euler 87: Investigating numbers that can be expressed as the sum of a prime square, cube, and fourth power?

Written by on 10 March 2012

Topics: Project Euler

Problem 87 of Project Euler is a cute little problem that reads

The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:

28 = 22 + 23 + 24
33 = 32 + 23 + 24
49 = 52 + 23 + 24
47 = 22 + 33 + 24

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

It was rather easy to solve this problem with brute force, so I took that as a first approach. All you need is primes up to and then you are set. I don’t really think it requires much of an explanation. I haven’t tried to beautify the code at all, so I am pretty sure it could be optimized and and made more readable

long[] primes = ESieve(2, 7071);
long[][] powers = new long[3][];
int target = 50000000;

List templist = new List(primes);
for (int j = 0; j < 3; j++) {
    for (int i = 0; i < primes.Length; i++) {
        templist[i] *= primes[i];
    }
    powers[j] = templist.ToArray();
}

SortedSet numbers = new SortedSet();
for (int i = 0; i < primes.Length; i++) {
    for (int j = 0; j < primes.Length; j++) {
        for (int k = 0; k < primes.Length; k++) {
            long number = powers[0][i] + powers[1][j] + powers[2][k];
            if (number > target) break;
            numbers.Add(number);
        }
    }
}

I used a SortedSet, since it not allow to add identical items. So I can only add it, if it does not exist. That means it is easy to only count things once. This code gives me

There are 1097343 numbers
Solution took 949,39 ms

which is by no means a fast solution.

Wrapping up

I have been thinking a lot about this problem and whether there is analysis that can be performed to speed up the code, but I haven’t been able to find a clever solution to the problem at all.

The code can be found here. And now for the big question – How did you solve it?

I had huge problems finding a fitting image for the blog post today. But I ended up with the lovely picture of a collection of Rubik’s cubes which is shared by Gerwin Sturm who shared it under the creative commons license.

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

  1. Guy says:

    I’m wondering whether computing the limit for each loop index could reduce significantly the execution time, for instance:

    int x = primes[i];
    int x2 = x * x;
    int jLimit = (int)Math.Pow(target - x2, 1.0 / 3.0);

    and:


    int y = primes[j];
    int y3 = y * y * y;
    int kLimit = (int)Math.Pow(target - x2 - y3, 1.0 / 4.0);

  2. ff says:

    Perhaps you can just give up the sorted set, and use a hash set instead? it would cut the running time off to at least half.

  3. Erebos1337 says:

    My first attempt was to use a HashSet, just like you did.
    My execution time was around 1000ms.

    After that I tried a boolean[] to memorize if I had found a number already.

    Then I incremented the counter only,
    if I didn’t find the number before, and mark it.

    Even though I needed 50 Mio. entries (of booleans) in that array,
    the execution time went down to around 80 ms.

    Here is my code in Java, not containing prime generation etc. :

    int count = 0;
    boolean[] nums = new boolean[(int) (limit+1)];

    for(int q : primes) {
    long quad = q*q*q*q;
    if(quad>=limit) break;

    for(int t : primes) {
    long triple = t*t*t;
    if(quad+triple>=limit) break;

    long div = limit – quad – triple;
    int divSqrt = (int)Math.sqrt(div);

    long sum = quad + triple;

    for(int s : primes) {
    if(s > divSqrt) break;

    int num = (int)(sum+s*s);
    if(!nums[num]) {
    count++;
    nums[num] = true;
    }
    }
    }
    }

  4. cesium62 says:

    if (number > target) break;
    The problem calls for numbers *below* 50,000,000.

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.