 # 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) {

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