2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5 ... 7  След.
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение30.03.2020, 03:59 


21/05/16
4292
Аделаида
jcmeyrignac в сообщении #1449315 писал(а):
Sorry, but these solutions don't have a place in the database.

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

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение30.03.2020, 09:47 


20/01/13
62
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).

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение30.03.2020, 10:00 


21/05/16
4292
Аделаида
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?

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение31.03.2020, 20:34 


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

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение01.04.2020, 09:47 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Мдааа неделя жесткой работы и никаких улучшений :(

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

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

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение01.04.2020, 12:24 
Аватара пользователя


25/08/12
171
Germany
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.

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение02.04.2020, 01:52 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
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.

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение02.04.2020, 02:45 


20/01/13
62
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.

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение02.04.2020, 11:43 
Аватара пользователя


25/08/12
171
Germany
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....

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение03.04.2020, 12:51 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Вау уже нашли восемь оптимальных решений! Я думал что это будет невозможно!

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение03.04.2020, 15:54 


07/06/16
45
Омск
Да, эти три человека знают что-то, чего не знаем мы. :)

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

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение03.04.2020, 17:07 
Аватара пользователя


25/08/12
171
Germany
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.

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение04.04.2020, 02:58 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
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.

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение04.04.2020, 17:31 


20/01/13
62
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.

 Профиль  
                  
 
 Re: Al Zimmermann's: Statue of Liberty
Сообщение06.04.2020, 06:48 


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 96 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 7  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group