I broke the problem down into four tasks:

1. Generate primes in the range
2. Calculate sums of runs
3. Generate perfect powers in range of the sums
4. Find matches between the sums and the powers

For step 1 ended up using the Miller-Rabin test.
Instead of choosing random numbers (the way this algorithm usually
works) I used the basis {2, 7, and 61} because it's guaranteed to be
correct up to 4.7 billion (which is greater than 2³².)

Step 2 is more interesting than it sounds. Instead of storing the raw
prime numbers in a table and summing them up as needed, I processed the
primes into a prefix sum
table. To recover the original prime number at index i, use sum[i+1] -
sum[i]. That's inconvenient but you get something big in return. The sum
of any sequence of primes from index i to j is given by sum[j+1] -
sum[i]. That means replacing k additions with 1 subtraction inside the main loop.

It's fast to build a sorted table of
perfect powers using an integer ipow(m, x) function and a priority queue
to keep them sorted. Heck, I assigned 39 threads to step 1 and only one
thread to step 3 and it still finished first. Having a table of perfect powers means never having to take an nth root.

Step 4 is where the action is. On VoVanx86's
huge "hundred million" test, steps 1 through 3 take one second and step 4 takes about 22 minutes.

I wrote five different search strategies only to throw four of them
away when the other one emerged as the fastest on all inputs. I call
it the stride strategy where stride is defined as the set of all k-pairs with the same value of k. Each thread takes a stride starting with k=2. It examines all k-pairs in the stride from the beginning of the range to the end. The cool thing about this is
that the sums gradually grow larger as you move downrange. Since the
power table is also sorted, I keep a pointer into it and do short
linear searches (usually no more than 2 steps) for values that match the
current sum. The body of the inner loop processes one k-pair:

while (p->n < sum) ++p;
if (p->n == sum) file.printresult(left, right, p);
sum = *++right - *++left;

Where p points into the power table and left/right are pointers into the prefix sum table spaced k units apart. The stride strategy is O(n²) where n is the number of primes in the range.

That's about it other than threading issues such as load
balancing. There was one astonishing result: frequent barriers cause
the program to run faster! The stride strategy has excellent locality of reference as long as all of the threads run together as a pack. If one
thread falls behind (perhaps to output results) I begin to see some cache
thrashing. So I added a "metronome" counter to resynchronize the threads at constant intervals. The
optimum time between resyncs: 600 milliseconds. I was expecting it to be
closer to a minute.

- Rick LaMont

My solution wasn't anything particularly technically amazing, but here goes :)

I just used the Sieve of Eratosthenes in the end; I'd intended to try the Sieve of Atkin, but it was much more complicated and I spent my time optimising other areas. Up to numbers about 1G, my basic sieve was pretty fast, so I didn't worry about it much beyond that; it was just a vector, which seemed good for memory consumption. Unfortunately, testing very late in the day in the 2G-4G range showed that performance dropped exponentially around there, so I'm not too confident; it may be just to do with the ancient laptop I was running it on (I had a lot of connectivity problems and never successfully got onto the MTL), but that's likely a vain hope. I did throw in a bit of threading: a parallel_for, after first sieving the first 200 numbers to ensure a good starting point, which made it a little faster. This was at the last minute, so I hope it didn't break anything for highly-multithreaded code, though it was fine for me.

The sums of primes was the worst bit of my performance, as I didn't come up with a good way to handle the O(N^2) computation. I tried storing recently used results, but that made it worse, as there wasn't much repetition.

Calculating perfect powers turned out pretty well, and was what I ended up spending much of my time on. I worked on the theory that, for a number that's a perfect power, every prime factor must be present at least twice in the factorisation, and also appear the same number of times (or a multiple of the same number of times, such as 2^4 * 3^2 = 2^2 * 2^2 * 3^2) as all other prime factors. Once I got this working, it seemed pretty fast.

My threading for the sums and perfect powers was all together; another parallel_for set individual threads to calculate a sum and then do the perfect power processing on it.

It'll be interesting to see how it goes :)

Hi all,

Here my small write up for the second problem. I have to start saying that I think that with this problem I am pretty sure I didnt make a very good work. Anyway, here is my solution.

For the primes list I have implemented the sieve of Eratosthenes. Since this is part is not critical, as already noted Vovanx86 and Rick Lamont, I didnt worry very much about that.

I used a parallel_for in order to parallelize the computation. In the parallel for, the computation of all sums starting in a specific prime are calculated by the same thread, so in every iteration a thread makes an addiction and check if the total sum is a perfect power.

The most important part of the implementation is how to check if a number is a perfect power. I didnt have time for testing different algorithms, so I decided to use a trial division test based in that some open source math libraries use this method. The basic idea is that if the sum is divisible by the prime e, then we can calculate a number e^r who also divide the sum, and if the sum is a perfect p-th power, then p has to be divisible by r. If we dont find e, we can use this result to limit the number of tries when we are checking for the perfect power.

About the solution source: (Windows/Linux, intel compiler/MSVC, TBB)

Solution attached

I did this - boolean lookup for primes less than 65536 and for those higher a sieve utilizing a lookup of all primes below 65536 - this worked pretty good for me. Now during the totally parallized lookup of these numbers within range I popped in a counter that equals the exact amount of possible combinations of sums for the given range. This counter was then used to determine the amount of threads required for calculating and writing out in case a perfect sum was found, waiting on a file lock served as my mutex. The summation was straightforward and I skipped any sort of optimization here since each ran in parallel with al the rest. Checking for the perfect power attribute was dealt with as follows: determine the approximate root using the log formula - which can bee seen as a lookup I believe, then checking and adapting below and over to check if it is exact. Well that is it.