2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 12  След.
 
 Re: Al Zimmermann: Primorial Soup
Сообщение15.10.2017, 02:21 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
lel0lel в сообщении #1255644 писал(а):
удивительно медленно работает алгоритм! Cпасибо за ответ.

Да да я и сам удивился. Многие задачи можно решить такими перестановками, но видимо не эту. Поэтому эта задача мне очень нравится.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение16.10.2017, 15:03 


04/10/17

153
dimkadimon в сообщении #1255740 писал(а):
lel0lel в сообщении #1255644 писал(а):
удивительно медленно работает алгоритм! Cпасибо за ответ.

Да да я и сам удивился. Многие задачи можно решить такими перестановками, но видимо не эту. Поэтому эта задача мне очень нравится.

Но именно матричное представление является хорошей подсказкой для разработки быстрого алгоритма!

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение16.10.2017, 16:19 
Заслуженный участник


04/03/09
911
as73251 в сообщении #1254452 писал(а):
Отличные результаты вплоть до числа узлов 12 (всплывающая подсказка для Hans-Werner & Matthias Paulsen показывает ровно 9.00) говорят о том, что на практике этот диапазон с ростом числа узлов становится настолько узким, что позволяет добиться таких прекрасных результатов.

В плане отношения ширины диапазона к энергии - да, он сужается. Но количество наборов простых чисел, у которых произведение попадает в диапазон, растет, и заметно, примерно на полпорядка-порядок при увеличении $n$ на единичку. Мой алгоритм сильно зависит от этого количества(например, для 12 потребовалось примерно в 1000 раз больше времени, чем для 11, при увеличении количества наборов всего втрое), так что для больших $n$ придется придумывать что-то совершенно другое.
dimkadimon в сообщении #1254654 писал(а):
Мне интересно как оптимальная $R$ растет в зависимости от $n$?
Примерно до $n=12$ растет как $\exp(cn)$, где $c \approx 2$. А дальше растет тоже экспоненциально, но уже $c \approx 6$. До $n=12$ текущие результаты гарантированно оптимальны. Возможно, это указывает на то, что текущие результаты для больших $n$ ооочень далеки от минимальных.

(Оффтоп)

dimkadimon в сообщении #1255740 писал(а):
Многие задачи можно решить такими перестановками, но видимо не эту.
Как обычно бывает с перестановками: сначала переставляешь по два, потом по два перестает работать и переставляешь по три, потом по четыре. Потом посещает мысль, что пора бы нормальный алгоритм придумать. =)

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение16.10.2017, 18:30 


04/10/17

153
12d3

Поздравляю Вас с попаданием в первую десятку: не каждый раз такое с россиянами случается. Желаю успехов.

P.S.
Если не секрет, какова "мощность" Вашего "железа"?

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение17.10.2017, 10:11 


03/03/12
1380
На Math Help Planet в качестве оптимального варианта при $n=4$ приведен результат $\{11,3,7\}$, $\{11,5,7\}$, $\{3,5,13\}$, $\{7,2,13\}$, $E=718$.
У меня в качестве оптимального варианта при $n=5$ получилось $\{2,5,29,17\}$, $\{2,7,13,19\}$, $\{3,7,17,23\}$, $\{3,11,19,29\}$, $\{5,13,23,11\}$, $E=51227$.

(Оффтоп)

Результат получен чисто логическими рассуждениями, следующими из результата при $n=3$ (при $n=4$ он даёт тоже $718$), без использования перебора вообще, опираясь на одну гипотезу, которой я давно пользуюсь и которая никогда не подводила. Интересно, является ли этот результат минимальным или он только оптимальный. Можно ли экстраполировать такой алгоритм. Сам алгоритм можно увидеть, правда, не полностью, глядя на построение полученной матрицы для $n=5$. Для $n=4$ матрицу надо записать в другом виде, чтоб алгоритм нагляднее просматривался. Ну, и учесть случай $n=3$. В рассмотренных случаях алгоритм даёт единственно возможную матрицу.

Собственно, меня интересует более вопрос: эти результаты только оптимальны, или и минимальны. Если кто знает, подскажите, пожалуйста.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение17.10.2017, 12:28 


09/03/16
34
Цитата:
TR63
для $n=5$: 51227
Собственно, меня интересует более вопрос: эти результаты только оптимальны, или и минимальны.


Не оптимальны, и не минимальны.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение17.10.2017, 13:45 


03/03/12
1380
ctac, спасибо. Правильно я поняла, что $718$ минимальный результат? Или он оптимальный, но не минимальный. А, какой результат оптимальный/минимальный для $n=(4;5)$. Под оптимальным я понимаю результат, меньше которого не известно на данный момент. Т.е. потенциально он может оказаться и минимальным, если сделать полный перебор. Если можете, назовите, пожалуйста, сколько вариантов известно для $n=5$, меньших $51227$. Интересно знать, насколько он плох. Я впервые решаю такую задачу. $718$ у меня сходу получилось без вычислений. Стали интересны закономерности.
Случаи $n=4$ и $n=5$ при исследовании оказались немного различными. К $n=5$ пришлось применить дополнительное действие, чтоб получить нужную структуру, удовлетворяющую наперёд заданным свойствам. Поэтому, видимо, результат хуже.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение17.10.2017, 13:56 


09/03/16
34
TR63

Вы сюда заглядывали?
http://azspcs.com/Contest/PrimorialSoup/BestRawScores

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение17.10.2017, 14:16 


03/03/12
1380
Именно сюда, нет. Сейчас заглянула. В английском я ноль. Пока там не вижу ответа на свой вопрос. Ну, да, ладно. В принципе я уже поняла, то что хотела понять, и без дополнительной информации.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение17.10.2017, 14:23 
Заслуженный участник


04/03/09
911
12d3 в сообщении #1256082 писал(а):
Примерно до $n=12$ растет как $\exp(cn)$, где $c \approx 2$. А дальше растет тоже экспоненциально, но уже $c \approx 6$.

А вот и график.
Изображение
UPD.
Есть еще одно странное совпадение. Для $n \le 12$ rawscore равно кубическому корню из target energy с точностью до порядка.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение17.10.2017, 15:52 


04/10/17

153
Martin Piotte улучшил результат для n=14! Best Raw Score было 738121859747, а стало 659249056399.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение17.10.2017, 17:36 
Заслуженный участник
Аватара пользователя


01/09/13
4676

(Оффтоп)

А за каким модулем там при регистрации реальные имя/фамилию требуют?

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение19.10.2017, 11:23 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
12d3 в сообщении #1256335 писал(а):
А вот и график.

Спасибо за интересный график. Видимо используется другой алгоритм для $N>12$.

-- 19.10.2017, 17:10 --

Geen в сообщении #1256384 писал(а):
А за каким модулем там при регистрации реальные имя/фамилию требуют?

Ал решил что будет лучше использовать реальные имена. Я совсем не против. Многие участники достигли многого в других областях и соревнованиях, а с реальным именем гораздо легче эту информацию найти.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение22.10.2017, 02:58 
Аватара пользователя


25/08/12
171
Germany
There is another nice representation of the problem, in the picture demonstrated for n=5.
Изображение

Each green horizontal line contains n -1 points. The horizontal positions of the points have to be Log(Prime(i)), i=1..n(n-1)/2. With target energy T and $ t= \frac{T}{n}$ the position $X$ of the red vertical line is $X = \frac{Log(t)}{(n-1)}$. Then the task is to move the n-1 points on each line to such a position that the "centers of gravity" $X_1, X_2 , X_3 ...$ are as close as possible to the red line.
This is difficult since each point is coupled to another point on a different line. In the picture shown we have for example $X_1 =\frac {Log(2)+Log(11)+Log(19)+Log(29)}{4}$.
A good approximation for the rawscore can be computed easily with $X$ and the average values $X_1, X_2 , X_3 ...$. It is given by

$rawscore \approx \frac{(n-1)^2}{2}t\sum\limits_{i=1}^{n} (X_i-X)^2 $
The approximation holds as long $ |X_i-X| \ll 1 $. In the example shown above the true rawscore is 1495.

For the minimal solution the $X_i$ are much closer to the X-line:
Изображение

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение23.10.2017, 15:11 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Herbert Kociemba в сообщении #1257810 писал(а):
There is another nice representation of the problem

Thank you Herbert Kociemba, this is a very beautiful way of looking at the problem.

Now I realise that it helps for the dots (on a given green line) to be roughly symmetric around the vertical red line. In your example this is true for $x_2$ and $x_5$. The symmetry allows the centre of gravity to be close to the red line.

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

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



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

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


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

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