Al Zimmermann: Primorial Soup

[dimkadimon]

lel0lel в сообщении #1255644 писал(а):

удивительно медленно работает алгоритм! Cпасибо за ответ.

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

[as73251]

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

lel0lel в сообщении #1255644 писал(а):

удивительно медленно работает алгоритм! Cпасибо за ответ.

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

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

[12d3]

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 писал(а):

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

Как обычно бывает с перестановками: сначала переставляешь по два, потом по два перестает работать и переставляешь по три, потом по четыре. Потом посещает мысль, что пора бы нормальный алгоритм придумать. =)

[as73251]

12d3

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

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

[TR63]

На 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$. В рассмотренных случаях алгоритм даёт единственно возможную матрицу.

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

[ctac]

Цитата:

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

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

[TR63]

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

[ctac]

TR63

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

[TR63]

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

[12d3]

12d3 в сообщении #1256082 писал(а):

Примерно до $n=12$ растет как $\exp(cn)$, где $c \approx 2$. А дальше растет тоже экспоненциально, но уже $c \approx 6$.

А вот и график.

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

[as73251]

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

[Geen]

(Оффтоп)

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

[dimkadimon]

12d3 в сообщении #1256335 писал(а):

А вот и график.

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

-- 19.10.2017, 17:10 --

Geen в сообщении #1256384 писал(а):

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

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

[Herbert Kociemba]

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:

[dimkadimon]

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.