Al Zimmerman - Delacorte Numbers

[sevir]

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

sevir в сообщении #941714 писал(а):

Как я понял, это уже устаревшие данные: у меня максимум перевалил в четвертую сотню со сдвигом на несколько десятков.

Как я понял у вас максимум 5934хх? Но потом вы говорите что "Спасибо: у меня близкие результаты, но у Вас лучше - я только что запустил новый алгоритм."...

Отличие моего результата от результата Herbert Kociemba - менее пяти единиц.

-- 08.12.2014, 16:50 --

sevir в сообщении #942477 писал(а):

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

sevir в сообщении #941714 писал(а):

Как я понял, это уже устаревшие данные: у меня максимум перевалил в четвертую сотню со сдвигом на несколько десятков.

Как я понял у вас максимум 5934хх? Но потом вы говорите что "Спасибо: у меня близкие результаты, но у Вас лучше - я только что запустил новый алгоритм."...

Отличие моего результата от результата Herbert Kociemba - менее пяти единиц.

Уже превзошел результат Herbert Kociemba: счет продолжается - попытаюсь еще увеличить разрыв.

[jcmeyrignac]

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

I think your 0th circle is my 1st and 2nd circles combined. Your 1st and 2nd circles are perhaps my 3rd and 4th combined. Your 3rd and 4th circles are perhaps my 5th circle. I also have a few cells in the "wrong place". When I try to correct these errors I don't get any improvements in the score. I still don't really know how to use these circles...

No, the circles are different because I use the "uniqueness".

About the circles, I use them for generating seeds, but there is probably other uses.

[sevir]

jcmeyrignac в сообщении #942687 писал(а):

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

I think your 0th circle is my 1st and 2nd circles combined. Your 1st and 2nd circles are perhaps my 3rd and 4th combined. Your 3rd and 4th circles are perhaps my 5th circle. I also have a few cells in the "wrong place". When I try to correct these errors I don't get any improvements in the score. I still don't really know how to use these circles...

No, the circles are different because I use the "uniqueness".

About the circles, I use them for generating seeds, but there is probably other uses.

Не надо ломать копья: даже самый грубый расчет, не требующий времени и ресурсов, расставит все числа по ранжиру: и после одного этого самого расчета все можно проиндексировать для всех последующих расчетов. Эта индексация очень полезна для сокращения времени расчетов: вкупе с формулами whitefox'а она дает громадное ускорение. Я тут уже выкладывал решение, которое получил мгновенно, для $n = 27$ и из которого без труда можно извлечь индексный массив. Хочу заметить, что можно вести более тонкую градацию, используя дроби. Например, для нахождения максимума в случае $n = 10$, который превышает значение 593350, я затратил не более часа времени на 20 ядрах.

[jcmeyrignac]

sevir в сообщении #942737 писал(а):

Например, для нахождения максимума в случае $n = 10$, который превышает значение 593350, я затратил не более часа времени на 20 ядрах.

I got it in 10 minutes on a quadcore, but I use a completely different method.
Also, there are several solutions above 593350, you'll be surprised !

[sevir]

jcmeyrignac в сообщении #942771 писал(а):

sevir в сообщении #942737 писал(а):

Например, для нахождения максимума в случае $n = 10$, который превышает значение 593350, я затратил не более часа времени на 20 ядрах.

I got it in 10 minutes on a quadcore, but I use a completely different method.
Also, there are several solutions above 593350, you'll be surprised !

И какое место Вы занимаете? И какой максимум у Вас для $n = 15$? Вы обгоняете Herbert Kociemba'у? Пока я от Вас не услышал ни одного конкретного предложения: одни общие слова.

[jcmeyrignac]

sevir в сообщении #942801 писал(а):

И какой максимум у Вас для $n = 15$?

$Max15 >= 8109168$

[dimkadimon]

sevir в сообщении #942801 писал(а):

И какое место Вы занимаете?

Он обгоняет всех на этом форуме (6ое место!)

[Nataly-Mak]

sevir в сообщении #942801 писал(а):

И какое место Вы занимаете? И какой максимум у Вас для $n = 15$? Вы обгоняете Herbert Kociemba'у?

Вопрос совершенно некорректный. Мне стыдно за форум!

sevir
а у вас, я полагаю, место 263.
Угадала?

[Pavlovsky]

Чего то мой пост про теоретические максимумы общество проигнорировало. Осмелюсь еще раз поднять эту тему.

Рассмотрим формулу whitefox:

$$D=\frac{n^4(n^2-1)}6+\sum\limits_{k=2}^{\frac{n^2}2}\varphi(k)\cdot D_k$$

$$D_k=\left\lfloor\frac{n^2}k\right\rfloor\sum\limits_{i\in M_k}\left((x(i)-\bar x_k)^2+(y(i)-\bar y_k)^2\right)$$

Пусть $med=\frac{n+1}{2}$ середина квадрата.

Гипотеза. D достигает максимума, если для всех k $\bar x_k = \bar y_k = med$. Тогда формулу можно переписать:

$$D=\frac{n^4(n^2-1)}6+\sum\limits_{i=1}^{n^2}\Phi(i)\cdot D(i)$$

, где
Квадрат расстояния от ячейки с числом i до центра квадрата:

$$D(i)=\left((x(i)-med)^2+(y(i)-med)^2)$$

Весовая функция числа i:

$$\Phi(i)=\sum\limits_{k\mid i, k\ge 2}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor$$

Утверждение. D достигает максимума, если для любых a,b

$$\Phi(a)\ge \Phi(b) => D(a) \ge D(b)$$

[Nataly-Mak]

Pavlovsky в сообщении #942860 писал(а):

Чего то мой пост про теоретические максимумы общество проигнорировало.

Скажу за себя.
Я и раньше-то совсем не вникала во все эти формулы. А сейчас и тем более, ибо давно вышла из конкурса.
Ваш пост с теоретическими максимумами видела и была восхищена (правда).

Вам с whitefox давно пора представить на защиту диссертацию "Числа Делакорта"

Нет, шутки шутками, а если серьёзно: написать статью в солидный журнал стоит.

[cepesh]

sevir забанен как клон пользователей wanderers, Nik_Svan, y_nikolaenko, drozdov_mihail, ...

[whitefox]

Pavlovsky в сообщении #942860 писал(а):

Пусть $med=\frac{n+1}{2}$ середина квадрата.

Гипотеза. D достигает максимума, если для всех k $\bar x_k = \bar y_k = med$.

Замечу,что значение $\mathrm{med}$ зависит от расположения начала координат. Если начало координат поместить в центр квадрата, то $\mathrm{med} = 0.$

Число Делакорта от расположения начала координат не зависит, и выражается формулой:

$$D=\sum\limits_{m=1}^{n^2}(x_m^2+y_m^2)\Phi(m)-\sum\limits_{m=1}^{n^2}\left(x_m\Psi_x(m)+y_m\Psi_y(m)\right)$$

Из которой выводится:

$$D^*=\sum\limits_{m=1}^{n^2}\widetilde{\Phi}(m)\left((x_m-\mathrm{med})^2+(y_m-\mathrm{med})^2\right)-\sum\limits_{k=2}^{\frac{n^2}2}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor^2\left((\bar x_k-\mathrm{med})^2+(\bar y_k-\mathrm{med})^2\right)$$

где

$$D^*=D-\frac{n^4(n^2-1)}6,\quad\widetilde{\Phi}(m)=\sum\limits_{k\mid m\atop{2\leqslant k\leqslant\frac{n^2}2}}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor$$

Из чего следует, что:

$$D^*\leqslant\sum\limits_{m=1}^{n^2}\widetilde{\Phi}(m)\left((x_m-\mathrm{med})^2+(y_m-\mathrm{med})^2\right)$$

независимо от справедливости Гипотезы.

В частности, при расположении начала координат в центре квадрата:

$$D^*\leqslant\sum\limits_{m=1}^{n^2}\widetilde{\Phi}(m)(x_m^2+y_m^2)$$

[Pavlovsky]

whitefox спасибо. Я так понял гипотеза, с вашим уточнением (точнее моя гипотеза нафиг не нужна ), доказана?


Провел эксперименты с этой формулой. Взял решение для N=7 Dm=56849 (есть у меня и лучше). Рекорд для N=7 Dr=57192. Теоретический максимум Dt=57400.

Посчитал потери в своем решении от помещения чисел не в свой круг, получилось -276. То есть уже за счет неправильного размещения чисел по кругам, мне уже рекорда 57192 не достичь (57192-57400=-208). Потери от того, что не все центры масс находятся в центре квадрата получаются =56849-57400+276=-275.

[whitefox]

Pavlovsky в сообщении #942929 писал(а):

whitefox спасибо. Я так понял гипотеза доказана?

К сожалению, нет. Доказана только независимость оценки верхней границы числа Делакорта от справедливости гипотезы. Ну и сама оценка, разумеется

[Pavlovsky]

whitefox в сообщении #942932 писал(а):

Нет, доказана только независимость оценки верхней границы числа Делакорта от справедливости гипотезы.

Чуток опередили, пока я редактировал свое сообщение. Моя гипотеза не нужна!

-- Вт дек 09, 2014 16:46:05 --

Получается такой алгоритм перебора.
1) Упорядочиваем список чисел по убыванию веса.
2) Размещаем очередное число из списка в свободную ячейку.
3) Считаем потери.
3.1) От нарушения условия

$$\Phi(a)\ge \Phi(b) => D(a) \ge D(b)$$

3.2) Оцениваем

$$\sum\limits_{m=1}^{n^2}\left(x_m\Psi_x(m)+y_m\Psi_y(m)\right)$$

4) Если потери превышают порог, возвращаем перебор назад.