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

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[];
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[i] + powers[j] + powers[k];
if (number > target) break;
}
}
}

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. Posted by Kristian Guy

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); ff

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. Erebos1337

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;

for(int t : primes) {
long triple = t*t*t;

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;
}
}
}
} cesium62

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

Instead of taking aquare root of 5 million and then applying brute force, it will be better if you try a loop(of fourth power) which goes from 2 to fourthroot(5 million – 24) and then in a nested loop which will go from 5 million – fourthpower(of the iterator value of first loop) and then add in this loop to the global sum variable squareroot(5milion – fourthpower(index of first loop) – cube(index of second loop)). This will require only two loops and time will be much lesser. Jean-Marie Hachey

PE87:

1229^2 + 101^3 + 83^4 = 49 999 063
This is the 1 097 326th number in the series.

Little challenge:
1 097 343 numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power.
What are the three primes giving that last number if raised at power 2, 3 and 4 respectively ?

Sources:
1) Kristian’s code for PE87
https://www.mathblog.dk/files/euler/Problem87.cs
2) Microsoft Visual C# 2010 Express
3) Microsoft Excel