Al Zimmermann: Primorial Soup

[dmd]

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

Осталось доказать что $E_t/n+\sqrt{2R*E_t/n}<E_t/(n-1)$.

Это несложно проверить для текущих значений $R$:

(код pari/gp)

test()=
{

R= [24,199,253,2958,67478,123005,2229731,8691987,101517569,6863373741,738121859747,1.48229242839918*10^15,1.18770408852339*10^17,9.82317746689238*10^19,8.63110873273221*10^21,6.22428590000818*10^24,5.97707155222809*10^27,2.28922015808109*10^30,4.30455284965413*10^33,5.08983545968970*10^36,1.67466158019576*10^39,5.39852062894653*10^41,2.32477528729077*10^46,1.61718924378801*10^49,1.39056162878021*10^52];

for(n=4, 28,

 q=n*(n-1)/2; Et= n*prod(i=1,q,prime(i))^(2/n);

 A= Et/n + sqrt(2*R[n-3]*Et/n);

 B= Et/(n-1);

 print("n= ", n, "    <||>= ", if(A<B, "<", ">"))

)

};

(ответ)

? \r test.gp
? test()
n= 4    <||>= >
n= 5    <||>= <
n= 6    <||>= <
n= 7    <||>= <
n= 8    <||>= <
n= 9    <||>= <
n= 10    <||>= <
n= 11    <||>= <
n= 12    <||>= <
n= 13    <||>= <
n= 14    <||>= <
n= 15    <||>= <
n= 16    <||>= <
n= 17    <||>= <
n= 18    <||>= <
n= 19    <||>= <
n= 20    <||>= <
n= 21    <||>= <
n= 22    <||>= <
n= 23    <||>= <
n= 24    <||>= <
n= 25    <||>= <
n= 26    <||>= <
n= 27    <||>= <
n= 28    <||>= <
?

Не выполняется только для n=4.

-- Ср окт 11, 2017 10:43:06 --

ну и заодно можно посмотреть разницу между $E_t/n+\sqrt{2R*E_t/n}$ и $E_t/(n-1)$ и сравнить её с $E_t$

(код)

 print("n= ", n, "    <||>= ", if(A<B, "<", ">"), "     ", ceil(precision(B-A,100)), "      Et= ", ceil(precision(Et,100)))

(ответ)

n= 4    <||>= >     -33      Et= 694
n= 5    <||>= <     272      Et= 42008
n= 6    <||>= <     149328      Et= 5102117
n= 7    <||>= <     23954788      Et= 1045582551
n= 8    <||>= <     5644344932      Et= 320199067842
n= 9    <||>= <     1931890578021      Et= 139236585382214
n= 10    <||>= <     921115887504929      Et= 82917736304314971
n= 11    <||>= <     584637197342375736      Et= 64311200663325126352
n= 12    <||>= <     471081206693109983297      Et= 62182854678993051622811
n= 13    <||>= <     491115151241392965831951      Et= 76614007963801045624680814
n= 14    <||>= <     618977888305674956553496817      Et= 112653995507888698803999094221
n= 15    <||>= <     947207146455542157383273253184      Et= 198913542393464734459263255417872
n= 16    <||>= <     1718978759555675531377474723254987      Et= 412554921076202165232769118938018361
. . .

[Herbert Kociemba]

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

So I give N=11 another try. Within one day I should know if R=6863373741 is optimal. I am quite sure it is.

Yes, R=6863373741 is optimal.

[Herbert Kociemba]

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

Yes, R=6863373741 is optimal.

Sorry, I totally mixed up the numbers in the last two posts. I mean of course 8691987 for N=11 is optimal.

[dmd]

Интересно, что в матрице нашего графа работают преобразования, сохраняющие суммарную энергию графа. Пусть диагональ единиц идёт с верхнего левого угла в правый нижний угол. Меняем местами два соседних столбца ниже диагонали, и там где столбцы надламываются на диагонали - меняем местами две соседние строки слева от диагонали. Таким образом два числа, принадлежащие разным вершинам, можно преобразованиями как угодно перемещать по матрице, но на одной вершине они не окажутся. Если предположить, что в оптимальном решении двойка и тройка принадлежат разным вершинам, то их можно развести по углам матрицы:

M[1,2]=M[2,1]=2

M[n,n-1]=M[n-1,n]=3

и если 2-ку и 3-ку зафиксировать так, то размерность задачи можно несколько сократить.

И в качестве гипотезы. Каким бы не получилось оптимальное решение, преобразованиями цепочка чисел 2,3,5,... может быть размещена на диагонали, ближайшей к диагонали единиц. Но через вершину, т.е. либо на чётных вершинах, либо на нечетных. Нумерация вершин тут у нас, скажем так, получается индексами матрицы.

[dmd]

пример преобразования

[as73251]

dmd

На самом деле алгоритм решения данного конкурса чрезвычайно прост: я думаю, что к концу конкурса верх будет заполнен одними 25-ками. Если же этого не случится, то сразу по окончании конкурса я опубликую этот алгоритм, а точнее, мгновенно и в любом случае, чтобы мое утверждение не считали голословным (ответ заготовлю заранее).

[lel0lel]

Задачи, решаемые с помощью сортировки массива не сложные, странно, что на это не обратили внимание организаторы конкурса.

[as73251]

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

Задачи, решаемые с помощью сортировки массива не сложные, странно, что на это не обратили внимание организаторы конкурса.

Задача Al'а очень качественная: не надо понимать мои слова буквально о простоте данного конкурса.

[12d3]

dmd
По сути такое преобразование - это перенумерация вершин в другом порядке. Сам граф не меняется.

[as73251]

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

dmd
По сути такое преобразование - это перенумерация вершин в другом порядке. Сам граф не меняется.

На языке матриц это перестановка строк и столбцов, сохраняющих симметрию матрицы. Например, для n=6 задача матричным методом быстро решается тупым перебором всех вариантов при условии, что элементы первой строки расположены в возрастающем порядке (15!/5! = 10897286400). При этом для генерирования перестановок лучше всего использовать алгоритм Джонсона-Троттера: пересчет произведений и суммы тогда занимает всего несколько тактов.

-- 14.10.2017, 02:10 --

as73251 в сообщении #1255562 писал(а):

dmd

На самом деле алгоритм решения данного конкурса чрезвычайно прост: я думаю, что к концу конкурса верх будет заполнен одними 25-ками. Если же этого не случится, то сразу по окончании конкурса я опубликую этот алгоритм, а точнее, мгновенно и в любом случае, чтобы мое утверждение не считали голословным (ответ заготовлю заранее).

Извиняюсь: это я погорячился. Но в любом случае алгоритм я опубликую.

[dimkadimon]

as73251 в сообщении #1255562 писал(а):

На самом деле алгоритм решения данного конкурса чрезвычайно прост: я думаю, что к концу конкурса верх будет заполнен одними 25-ками. Если же этого не случится, то сразу по окончании конкурса я опубликую этот алгоритм, а точнее, мгновенно и в любом случае, чтобы мое утверждение не считали голословным (ответ заготовлю заранее).

Тогда почему сейчас нет 25.00? Пока что я не вижу эту "простоту". Буду с нетерпением ждать вашего алгоритма.

-- 14.10.2017, 08:17 --

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

Задачи, решаемые с помощью сортировки массива не сложные, странно, что на это не обратили внимание организаторы конкурса.

Тут простой "сортировкой массива" не отделаешься. Как уже писали раньше: маленькие изменения в массиве дают очень большие изменения в очках. Именно поэтому нужны более "умные" алгоритмы для этой задачи.

[as73251]

dimkadimon

Вы не прочитали мое последнее сообщение, хотя мне понятно, почему два первых места отделены значительным интервалом от последующих.

[lel0lel]

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

Тут простой "сортировкой массива" не отделаешься. Как уже писали раньше: маленькие изменения в массиве дают очень большие изменения в очках.

По-моему, это как раз то что нужно для сортировки. В сущности, мы же не против чтобы полная энергия уменьшалась "большими шагами", главное, чтобы с каждой выполненной перестановкой она уменьшалась. Чтобы уменьшить затраты на расчёт полной энергии при оценивании очередной потенциальной перестановки - удобно запоминать предыдущие значения энергий вершин, тогда перерасчёт нужно сделать только по тем вершинам, у которых энергия изменяется в результате такой перестановки.

В теории выглядит всё гладко, но, чтобы узнать насколько это эффективно, нужно применить на практике. Обязательно найду время на следующей неделе, чтобы проверить будет ли алгоритм с парными перестановками приводить к минимуму и насколько он будет медленным или быстрым для больших N.

[dimkadimon]

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

В теории выглядит всё гладко, но, чтобы узнать насколько это эффективно, нужно применить на практике. Обязательно найду время на следующей неделе, чтобы проверить будет ли алгоритм с парными перестановками приводить к минимуму и насколько он будет медленным или быстрым для больших N.

Вот мой результат из практики. Пользуясь обычной сортировкой (перестановка пар) я смог найти только первые 4 лучших решения и то не сразу. Когда поменял алгоритм я смог найти следующие 3 лучших решения. Причем мой новый алгоритм находит первые 5 лучших решений почти мгновенно.

[lel0lel]

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