2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6 ... 12  След.
 
 Re: Al Zimmermann: Primorial Soup
Сообщение11.10.2017, 08:08 


16/08/05
1146
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
. . .

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


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

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


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

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


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

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

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

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

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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение13.10.2017, 23:46 


16/08/05
1146
пример преобразования
Изображение

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение14.10.2017, 00:23 


04/10/17

153
dmd

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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение14.10.2017, 00:38 


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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение14.10.2017, 00:48 


04/10/17

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

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

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


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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение14.10.2017, 01:39 


04/10/17

153
12d3 в сообщении #1255567 писал(а):
dmd
По сути такое преобразование - это перенумерация вершин в другом порядке. Сам граф не меняется.

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

-- 14.10.2017, 02:10 --

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

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

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

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


01/06/12
1016
Adelaide, Australia
as73251 в сообщении #1255562 писал(а):
На самом деле алгоритм решения данного конкурса чрезвычайно прост: я думаю, что к концу конкурса верх будет заполнен одними 25-ками. Если же этого не случится, то сразу по окончании конкурса я опубликую этот алгоритм, а точнее, мгновенно и в любом случае, чтобы мое утверждение не считали голословным (ответ заготовлю заранее).

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

-- 14.10.2017, 08:17 --

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

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

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение14.10.2017, 02:49 


04/10/17

153
dimkadimon

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

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


20/04/10
1776
dimkadimon в сообщении #1255577 писал(а):
Тут простой "сортировкой массива" не отделаешься. Как уже писали раньше: маленькие изменения в массиве дают очень большие изменения в очках.

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

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

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


01/06/12
1016
Adelaide, Australia
lel0lel в сообщении #1255637 писал(а):
В теории выглядит всё гладко, но, чтобы узнать насколько это эффективно, нужно применить на практике. Обязательно найду время на следующей неделе, чтобы проверить будет ли алгоритм с парными перестановками приводить к минимуму и насколько он будет медленным или быстрым для больших N.

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

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


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

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

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



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

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


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

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