1
$\begingroup$

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
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – MarcoB
    Dec 6 '21 at 14:21
  • $\begingroup$ @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 $\endgroup$ Dec 6 '21 at 14:41
  • $\begingroup$ 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. $\endgroup$
    – MarcoB
    Dec 6 '21 at 16:21
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.