Al Zimmermann's: Statue of Liberty

[Archimedes]

Наконец-то дошли руки посмотреть что же там в меньших степенях. А там оказывается много интересного. В том числе можно спрогнозировать где искать точные решения.

[jcmeyrignac]

I'll share some benchmarks.

My pure C program takes 22 seconds to exhaustively compute 83^16.
I rewrote the code in pure ASM (it took me 3 days), and it does the computation in 19 seconds.

royvanrijn в сообщении #1452459 писал(а):

Цитата:

porcoroso в сообщении #1452063 писал(а):

search for 83^16 is 30 secs and 86^16 is more than two minutes. So its not good enough for reaching the top four, they have something else ....

Thank you for information.
I suppose 25x speedup is enough argument to write a program in C.

Hey, my code now does 83^16 in 180 secs, still not the same... but not an automatic 25x speedup

[Archimedes]

Windows 10 - это большой вирус. Перезагрузила мне ночью компьютер со всеми работающими процессами. Почему я не остался на Windows 7?

[kotenok gav]

Archimedes
Именно для таких случаев стоит создавать файл, в котором хранится последнее перебранное решение.

[Herbert Kociemba]

jcmeyrignac в сообщении #1455011 писал(а):

My pure C program takes 22 seconds to exhaustively compute 83^16.

22 s to search for an error 0 solution (which does not exist) or to find the solution with the smallest error? The first search can be done faster.

[jcmeyrignac]

22 seconds for the smallest error on 83^16.

Herbert Kociemba в сообщении #1455281 писал(а):

jcmeyrignac в сообщении #1455011 писал(а):

My pure C program takes 22 seconds to exhaustively compute 83^16.

22 s to search for an error 0 solution (which does not exist) or to find the solution with the smallest error? The first search can be done faster.

[Herbert Kociemba]

jcmeyrignac в сообщении #1455368 писал(а):

22 seconds for the smallest error on 83^16.

My program takes several minutes for this task. Nevertheless I do not believe that this is the way to find an error 0 solution. Searching directly for an error 0 solution increases the search speed incredibly. To completely scan s^16 for s=83 takes << 1 ms with my program (generation of a table which is independent of the basis s not included).

[porcoroso]

Herbert Kociemba в сообщении #1455594 писал(а):

jcmeyrignac в сообщении #1455368 писал(а):

22 seconds for the smallest error on 83^16.

My program takes several minutes for this task. Nevertheless I do not believe that this is the way to find an error 0 solution. Searching directly for an error 0 solution increases the search speed incredibly. To completely scan s^16 for s=83 takes << 1 ms with my program (generation of a table which is independent of the basis s not included).

Well my program also searches for minimal error solution, as I still did not figure out how to effectively search for 0 solution in a better way than minimal one.
I more or less gave up, as I can'f find a good way to restrict the solution space using equations, or modulo relations , and even if one equations is known
like you showed mod 64 it does not help with normal backtracking search. A new approach is needed,but I cant seem to find it.

[Herbert Kociemba]

porcoroso в сообщении #1455645 писал(а):

and even if one equations is known
like you showed mod 64 it does not help with normal backtracking search. A new approach is needed,but I cant seem to find it.

Indeed I do not use the mod 64 approach in the current version of the program. Still I suspected that there might be an error since I could not believe that it is so fast. But I applied it also to 63^10, 68^11and 81^12 (the optimal solutions for s= 10, 11 , 12) and it found the solutions given in the OEIS:
https://oeis.org/A030052/a030052.txt
63^10 for example took 1 s and gave 3 error 0 solutions.

[dimkadimon]

Herbert Kociemba в сообщении #1455662 писал(а):

Indeed I do not use the mod 64 approach in the current version of the program.

Do you use any modulus equations at all? Can you give us a hint. I have pretty much given up on the problem...

[jcmeyrignac]

I guess a simple binary search is used.

[Herbert Kociemba]

dimkadimon в сообщении #1457294 писал(а):

Do you use any modulus equations at all? Can you give us a hint. I have pretty much given up on the problem...

What I did is a forward and backward. I recognized, that essentially what I did is a mod 64 method done a bit different, so I returned to it. I additionally use mod 17. But all this still does not help me to find an exact solution so I also have almost given up. Nevertheless I can share a few more details which show the kind of approach. For example the solution for s=220 must have at least 69 summands.
We have x^16= 1 mod 17 for all x which are not divisible by 17, a consequence of Fermat's little theorem. We also have x^16= 1 mod 64 for all x not divisible by 2.
Because 220^16= 1 mod 17 and 220^16= 0 mod 64, we must have exactly

1+i*17 bases in our sum which are are not divisible by 17 and
0+64*j bases which are not divisible by 2.

If the number of bases is less than 64 then j=0, all bases would have to be even. But then, because 220 is also even we could divide the solution by 2^16 and would get a solution with less than 64 bases for 110^16. With the same argument this can be reduced to a solution to 55^16, which does not exist.
So we have at least 64 bases. The smallest i for which this possible is i=4, so we have at least 69 bases which are not divisible by 17 in the sum which adds up to 220^16.
Of course this also allows pruning if you search for a solution for 220 beginning with large bases working down to small bases. If for example your partial sum is 23 mod 64, the part still to do must be 41 mod 64 which means, you have still have to add at least 41 uneven bases. Then you know that this is impossible if you only have for example the numbers 1..80 left.
But even with using these ideas for pruning my current program seems not good enough to find a solution for s=220.

[jcmeyrignac]

One more trick: you can only work on the odd terms first, and the even terms last.

Herbert Kociemba в сообщении #1457340 писал(а):

dimkadimon в сообщении #1457294 писал(а):

Do you use any modulus equations at all? Can you give us a hint. I have pretty much given up on the problem...

What I did is a forward and backward. I recognized, that essentially what I did is a mod 64 method done a bit different, so I returned to it. I additionally use mod 17. But all this still does not help me to find an exact solution so I also have almost given up. Nevertheless I can share a few more details which show the kind of approach. For example the solution for s=220 must have at least 69 summands.
We have x^16= 1 mod 17 for all x which are not divisible by 17, a consequence of Fermat's little theorem. We also have x^16= 1 mod 64 for all x not divisible by 2.
Because 220^16= 1 mod 17 and 220^16= 0 mod 64, we must have exactly

1+i*17 bases in our sum which are are not divisible by 17 and
0+64*j bases which are not divisible by 2.

If the number of bases is less than 64 then j=0, all bases would have to be even. But then, because 220 is also even we could divide the solution by 2^16 and would get a solution with less than 64 bases for 110^16. With the same argument this can be reduced to a solution to 55^16, which does not exist.
So we have at least 64 bases. The smallest i for which this possible is i=4, so we have at least 69 bases which are not divisible by 17 in the sum which adds up to 220^16.
Of course this also allows pruning if you search for a solution for 220 beginning with large bases working down to small bases. If for example your partial sum is 23 mod 64, the part still to do must be 41 mod 64 which means, you have still have to add at least 41 uneven bases. Then you know that this is impossible if you only have for example the numbers 1..80 left.
But even with using these ideas for pruning my current program seems not good enough to find a solution for s=220.

[dimkadimon]

Herbert thank you for your informative post. It is very useful and I have learned a lot from it. It has given me some new hope.

220 is only the lowest solution found. But perhaps there are other values that are easier to find with these methods? At this stage I would be happy with ANY solution, no matter how large.

[Herbert Kociemba]

Yes, there must be a method which gets easier for large s. Jarek takes s=1.513.151.757 for n=31. I wonder how many parts the sum has. Thousends? Millions? A billion?

Also thanks to Jean-Charles for his tip. This also gives me some new idea where to go. Within a few hours I now can completely check s^16 up to 151^16 and no solution exists. But this still is not enough.