# Parallel Mathematica-code that runs too slow when running PowerRepresentations[] function

Well, I am a student in elementary number theory and trying to find natural numbers that can be written as the sum of integers to the power of an integer. The code I am using now is the following:

Clear["Global*"];
a =;
b =;
\[Alpha] =;
\[Beta] =;
k =;
SetSharedVariable[pr];
pr = {};
ParallelDo[
If[Length[
Select[PowersRepresentations[n, a, b],
DuplicateFreeQ[#] && ! MemberQ[#, 0] &]] >= k,
AppendTo[pr, n]], {n, \[Alpha], \[Beta]}];
Sort[pr]


This code is pretty fast for smaller values of $$a,b,\alpha,\beta$$ and $$k$$. But for larger values this code becomes really slow. Is there a way to improve the code? Thanks for any help and advice.

The code I am trying to run right now is:

Clear["Global*"];
a = 3;
b = 5;
\[Alpha] = 6000000;
\[Beta] = 7000000;
k = 6;
SetSharedVariable[pr];
pr = {};
ParallelDo[
If[Length[
Select[PowersRepresentations[n, a, b],
DuplicateFreeQ[#] && ! MemberQ[#, 0] &]] >= k,
AppendTo[pr, n]], {n, \[Alpha], \[Beta]}];
Sort[pr]


I also tried the following code but also that code is way too slow:

Clear["Global*"];
a = 3;
b = 5;
\[Alpha] = 6000000;
\[Beta] = 7000000;
k = 6;
ParallelTable[
If[TrueQ[Length[
Select[PowersRepresentations[n, a, b],
DuplicateFreeQ[#] && ! MemberQ[#, 0] &]] >= k], n,
Nothing], {n, \[Alpha], \[Beta]}] //. {} -> Nothing

• Have you figured out where the bottleneck is? If it is in the calculation of PowerRepresentations for larger values, parallelization probably won't help much. Dec 6 '21 at 14:21
• @MarcoB I assume that that is the bottleneck. I do not know a way to get around that, do you know a fast method? Or can you point me in the right direction? Thanks Dec 6 '21 at 14:41
• I don't know of a faster method, but I think the question is really algorithmic at this point. I think your approach to create all power representations and then select the ones that meet your criteria is very resource-intensive and unlikely to scale well. Parallelizing may help if you have access to a LARGE number of computing cores (and an appropriate Mathematica license). But consider looking for an alternative approach (e.g. constructing only those numbers that have your desired properties instead). That would a good question for the math forum, I think. Dec 6 '21 at 16:21

Would a generative approach be acceptable? In the example above you see triplets of numbers ($$a=3$$) for which the sum of their fifth powers ($$b=5$$) is equal to a number in the 6-7 million range.

You could generate all triplets of numbers in an appropriate range (determining which would require some experimenting), then calculate the number that would result from the sum of their fifth powers, and select those triplets that give you numbers in the range you want:

Select[
{{##}, #1^b + #2^b + #3^b} & @@@
Tuples[Range[0, 100], 3],
6000000 <= Last@# <= 7000000 &
]

{
{{0, 0, 23}, 6436343}, {{0, 1, 23}, 6436344}, {{0, 2, 23}, 6436375},
{{0, 3, 23}, 6436586}, {{0, 4, 23}, 6437367}, {{0, 5, 23}, 6439468},
{{0, 6, 23}, 6444119}, {{0, 7, 23}, 6453150}, ...
...                    {{23, 14, 6}, 6981943}, {{23, 14, 7}, 6990974}
}


This is far faster than your approach, but how exhaustive the search is depends on the Range you choose inside Tuples`. I just increased the upper bound of the range until the number of results didn't change and the highest returned value was close to the upper bound of your search window, then added a bit more just to be sure.