Issue
For example, if I want to find
1085912312763120759250776993188102125849391224162 = a^9+b^9+c^9+d
the code needs to brings
a=3456
b=78525
c=217423
d=215478
I do not need specific values, only that they comply with the fact that a, b and c have 6 digits at most and d is as small as possible.
Is there a quick way to find it?
I appreciate any help you can give me.
I have tried with nested loops but it is extremely slow and the code gets stuck.
Any help in VB or other code would be appreciated. I think the structure is more important than the language in this case
Imports System.Numerics
Public Class Form1
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Dim Value As BigInteger = BigInteger.Parse("1085912312763120759250776993188102125849391224162")
Dim powResult As BigInteger
Dim dResult As BigInteger
Dim a As Integer
Dim b As Integer
Dim c As Integer
Dim d As Integer
For i = 1 To 999999
For j = 1 To 999999
For k = 1 To 999999
powResult = BigInteger.Add(BigInteger.Add(BigInteger.Pow(i, 9), BigInteger.Pow(j, 9)), BigInteger.Pow(k, 9))
dResult = BigInteger.Subtract(Value, powResult)
If Len(dResult.ToString) <= 6 Then
a = i
b = j
c = k
d = dResult
RichTextBox1.Text = a & " , " & b & " , " & c & " , " & d
Exit For
Exit For
Exit For
End If
Next
Next
Next
End Sub
End Class
Solution
In case a,b,c,d
might be zero I got an Idea for fast and simple solution:
First something better than brute force search of a^9 + d = x
so that a
is maximal (that ensures minimal d
)…

let
d = 1085912312763120759250776993188102125849391224162

find max value
a
such thata^9 <= d
this is simple as we know 9th power will multiply the bitwidth of operand 9 times so the max value can be at most
a <= 2^(log2(d)/9)
Now just search all numbers from this number down to zero (decrementing) until its 9th power is less or equal tox
. This value will be oura
.Its still brute force search however from much better starting point so much less iterations are required.

We also need to update
d
so letd = d  a^9
Now just find b,c
in the same way (using smaller and smaller remainder d
)… these searches are not nested so they are fast …
b^9 <= d; d=b^9;
c^9 <= d; c=b^9;
To improve speed even more you can hardcode the 9th power using power by squaring …
This will be our initial solution (on mine setup it took ~200ms with 32*8 bits uints) with these results:
x = 1085912312763120759250776993188102125849391224162
1085912312763120759250776993188102125849391224162 (reference)
a = 217425
b = 65957
c = 22886
d = 39113777348346762582909125401671564
Now we want to minimize d
so simply decrement a
and search b
upwards until still a^9 + b^9 <= d
is lower. Then search c
as before and remember better solution. The a should be search downwards to meet b
in the middle but as both a
and b
have the same powers only few iterations might suffice (I used 50) from the first solution (but I have no proof of this its just my feeling). But still even if full range is used this has less complexity than yours as I have just 2 nested for
s instead of yours 3 and they all are with lower ranges…
Here small working C++ example (sorry do not code in BASIC for decades):
//
typedef uint<8> bigint;
//
bigint pow9(bigint &x)
{
bigint y;
y=x*x; // x^2
y*=y; // x^4
y*=y; // x^8
y*=x; // x^9
return y;
}
//
void compute()
{
bigint a,b,c,d,D,n;
bigint aa,bb,cc,dd,ae;
D="1085912312763120759250776993188102125849391224162";
// first solution so a is maximal
d=D;
for (a=1<<((d.bits()+8)/9);a>0;a) if (pow9(a)<=d) break; d=pow9(a);
for (b=1<<((d.bits()+8)/9);b>0;b) if (pow9(b)<=d) break; d=pow9(b);
for (c=1<<((d.bits()+8)/9);c>0;c) if (pow9(c)<=d) break; d=pow9(c);
// minimize d
aa=a; bb=b; cc=c; dd=d;
if (aa<50) ae=0; else ae=aa50;
for (a=aa1;a>ae;a) // a goes down few iterations
{
d=Dpow9(a);
for (n=1<<((d.bits()+8)/9),b++;b<n;b++) if (pow9(b)>=d) break; b; d=pow9(b); // b goes up
for (c=1<<((d.bits()+8)/9);c>0;c) if (pow9(c)<=d) break; d=pow9(c); // c must be search fully
if (d<dd) // remember better solution
{
aa=a; bb=b; cc=c; dd=d;
}
}
a=aa; b=bb; c=cc; d=dd; // a,b,c,d is the result
}
//
The function bits()
just returns number of occupied bits (similar to log2
but much faster). Here final results:
x = 1085912312763120759250776993188102125849391224162
1085912312763120759250776993188102125849391224162 (reference)
a = 217423
b = 78525
c = 3456
d = 215478
It took 1689.651 ms … As you can see this is much faster than yours however I am not sure with the number of search iterations while fine tuning a
is OK or it should be scaled by a/b
or even full range down to (a+b)/2
which will be much slower than this…
One last thing I did not bound a,b,c to 999999
so if you want it you just add if (a>999999) a=999999;
statement after any a=1<<((d.bits()+8)/9)
…
Answered By – Spektre
Answer Checked By – Jay B. (BugsFixing Admin)