Al Zimmermann's: Statue of Liberty

[kotenok gav]

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

Sorry, but these solutions don't have a place in the database.

Why? They are (3,1,3) and (7,1,15).

[jcmeyrignac]

kotenok gav в сообщении #1449420 писал(а):

Why? They are (3,1,3) and (7,1,15).

About third and seventh powers, I'm only collecting (3,1,2), (7,1,7) or (7,1,6).

[kotenok gav]

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

About third and seventh powers, I'm only collecting (3,1,2), (7,1,7) or (7,1,6).

Ok. Is there a list of all known solutions?

[Archimedes]

"Известные решения" - это, в некотором смысле, самые простейшие приближения решений.
И пока, если судить по таблице результатов, более сложные решения нашли только для N от 16 до 20.
У меня есть приближения только для 16 и 17.

[dimkadimon]

Мдааа неделя жесткой работы и никаких улучшений :(

Перепробовал разные виды метода отжига. Задача дьявольски сложная. Самое лучшее что я нашел для $n=16$ это разница в 1,453,965,920, а надо побить разницу 42,981,184.

Теперь думаю как можно обойтись без больших чисел? Самое лучшее что придумал это использовать логарифмы и правило $\log(a+b) = \log(a) + \log(1+b/a)$. Но не знаю что делать дальше.

[Herbert Kociemba]

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

Мдааа неделя жесткой работы и никаких улучшений :(

Теперь думаю как можно обойтись без больших чисел? Самое лучшее что придумал это использовать логарифмы и правило $\log(a+b) = \log(a) + \log(1+b/a)$. Но не знаю что делать дальше.

For n=16 and n=17 I find solutions which are better than the trivial solution just by exhausting s^n with k^n with k<n, starting with k=n-1 and working down to k=1.
I work with Delphi and use an arbitrary precision integer package. It works well for really big numbers. So within a few minutes I get for example

10000^10=>{9999, 5011, 2576, 1387, 840, 494, 325, 234, 159, 119, 100, 80, 68, 58, 52, 48, 45, 38, 32, 28, 27, 26, 25, 19, 18, 16, 15, 12, 11, 9, 8, 7, 5, 4, 2, 1}
100000^10=>{99999, 39810, 16333, 5195, 2646, 1125, 664, 341, 214, 172, 134, 104, 86, 76, 66, 60, 52, 45, 43, 37, 32, 30, 28, 27, 23, 22, 20, 18, 15, 14, 11, 9, 8, 7, 4, 3, 2, 1}
100000^10=>{99999, 39810, 16333, 5195, 2646, 1125, 664, 340, 244, 197, 148, 113, 52, 46, 41, 36, 33, 30, 28, 27, 26, 25, 24, 23, 21, 20, 19, 18, 15, 14, 13, 12, 10, 7, 4}

with an error of 0.

So I do not believe that it is necessary to work with reals and the log function.

[dimkadimon]

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

For n=16 and n=17 I find solutions which are better than the trivial solution just by exhausting s^n with k^n with k<n, starting with k=n-1 and working down to k=1.

I couldn't get this to work. I must be missing something... oh you mean exhaustively trying every combination of those value?

-- 02.04.2020, 07:40 --

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

I work with Delphi and use an arbitrary precision integer package. It works well for really big numbers.

I am using Java's BigInteger. It works, but it is really slow compared to int/long.

[jcmeyrignac]

You can visualize the problem as cutting a pie with different slices sizes.

There are several ways to do that.
If you need some ideas, you can check my (old) assembly language implementations in http://euler.free.fr/programs/old/Sources.zip

Also, you should read the literature about ESLP.
For example, computing solutions for 6th power can be done by using moduli, for example 7^6, etc.

[Herbert Kociemba]

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

I couldn't get this to work. I must be missing something... oh you mean exhaustively trying every combination of those value?

In principle yes, recursively, starting from the high values. But of course you can prune the tree. Adding the next number can lead to a value which is too big or too small to continue successfully. Meanwhile I found within about 12 h a better than trivial solution for n=18 now with E=62.064.869, this should have increased my score by tremendous 0.0047.

Thanks jcmeyrignac for your hints! I completely understand that you cannot and should not be too specific here. Took me a couple of minutes with Google to reveal what ESLP stands for in this context....

[dimkadimon]

Вау уже нашли восемь оптимальных решений! Я думал что это будет невозможно!

[Archimedes]

Да, эти три человека знают что-то, чего не знаем мы. :)

А у меня печалька - обидная описка в программе отбрасывала половину решений. Минус 2-е суток.

[Herbert Kociemba]

Eventally we should not try to find approximate solutions but only the optimal solution. Then you can indeed use moduli. For example x^16 mod 64 is only 0 (x even) or 1 (x odd). Then for example 100^16 can only be the sum of only even x^16 or of some even x^16 and exactly 64 odd x^16.

[dimkadimon]

Archimedes в сообщении #1450848 писал(а):

А у меня печалька - обидная описка в программе отбрасывала половину решений. Минус 2-е суток.

Жалко конечно, но хорошо что вы ошибку заметили. 2 дня из нескольких месяцев это не так много.

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

Eventally we should not try to find approximate solutions but only the optimal solution. Then you can indeed use moduli. For example x^16 mod 64 is only 0 (x even) or 1 (x odd). Then for example 100^16 can only be the sum of only even x^16 or of some even x^16 and exactly 64 odd x^16.

Herbert you are spot on here. I think this will be the way to go. In fact finding optimal solutions could end up being easier than finding good non-optimal solutions, as there are more constraints.

[jcmeyrignac]

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

Herbert you are spot on here. I think this will be the way to go. In fact finding optimal solutions could end up being easier than finding good non-optimal solutions, as there are more constraints.

Not necessarily.
The modulo constraints are useful for optimal solutions, but other approaches for solving this problem exist (I won't describe them, since I'm also competing).
If you want to focus on optimal solutions, then yes, you should use the modular constraints. There are several others, at least for N=16 (like the first term should be of the same parity as the left term, etc), and no constraint exists for N=17!
If you want to get a good score, modular constraints are useless.

[Archimedes]

"Покрутил" немного идею Херберта. Здесь встаёт вопрос как быстро отсеивать лишние варианты, чтобы их опять не стало 2^N.

А пока сделал оптимизацию алгоритма, запихав низ таблицы сумм в индексированный массив 2^25, из которого находится ближайшие верхнее и нижнее приближения решения. Получилось ускорение в 4 раза. Только оперативной памяти программа стала использовать больше. Но можно ценой небольшого замедления исправить это, уменьшив массив до 2^24. Например, 74^16 просчитывается старым алгоритмом за 173 сек., 2^24 - за 39 сек., 2^25 - за 35 сек.
Как ни странно, если увеличить массив до 2^26, то программа работает медленнее - 42 сек. Скорее всего данные перестают помещаться в ОЗУ и компьютер теряет время на своп.