Al Zimmerman - Delacorte Numbers

[whitefox]

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

А что мы все только про максимум? Кажется я нашел интересные узоры для минимум. Допустим у нас есть минимум решение $A$. Тогда создадим $B$:

$B_{ij}:= \max_k$ such that $A_{ij}\%p_k=0,$

$p=\{1,2,3,5,7,11,13,17,19,23\}.$

Вот какие у меня получаются $B$:

(Оффтоп)

N=8
00334400
05333440
55334340
55334442
11122222
11122272
09166787
90166880

N=9
055533300
054533360
455433366
444333666
444422111
222222111
022221710
009878710
009988700

N=10
0090151000
0199555200
0195555510
1111222222
1112222222
8883334442
8733334444
7833346444
7773364660
0003366600

Интересно то что одинаковые числа группируются вместе!

Это происходит в полном соответствии с Утверждением Pavlovsky о плотной упаковке чисел кратных $p_k.$

[Pavlovsky]

$$D=\sum\limits_{m=1}^{n^2}\Phi(m)\left((x_m-\mathrm{med})^2+(y_m-\mathrm{med})^2\right)-\sum\limits_{k=1}^{n^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)$$

Выражение справа достигает максимума если

$$\sum\limits_{k=1}^{n^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) = 0$$

А это возможно если

$$\bar x_k=\bar y_k=\mathrm{med}$$

Получилась следующая формула расчета числа Делакорта.

$$D=\mathrm{TM} - \sum\limits_{m=1}^{n^2}\Phi(m)\left(R(m)-(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) $$

,где $TM$ теоретический максимум (верхняя оценка);
$R(m)$ квадрат расстояния от ячейки до центра квадрата, рекомендуемый для числа m в соответсвии с его $\Phi(m)$.

-- Ср дек 10, 2014 14:05:26 --

Что можно сказать о таком способе расчета числа Делакорта?!

1) Формула объясняет следующее наблюдение

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

Гипотеза. Пусть K число с максимальным весом. Тогда в решении с максимальным числом Делакорта, числа K и K/2 находятся в противоположных углах квадрата.

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

2) Вычислительная сложность такая же как по формулам whitefox (первый пакет формул). Если алгоритм основан на улучшении некоторого решения, путем перестановок чисел, то выигрыша никого нет.

3) В алгоритме перебора основанном на постепенном заполнении квадрата числами, главная проблема оценить переспективность частично заполненного квадрата. В таких алгоритмах такой способ расчета числа Делакорта может оказаться полезным.

[whitefox]

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

Выражение справа достигает максимума если

$$\sum\limits_{k=1}^{n^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) = 0$$

Вот именно это доказать у меня не получилось. А как Вы это сделали?

[Pavlovsky]

Полуручные вычислительные эксперименты, с одним из моих решений для N=7. Показали следующую картину. Перебор выдаст диагноз, что результат 57192 недостижим для следующего квадрата. Только что в квадрат было поставлено число 8.
$\tikz[scale=.063]{ \draw(0,0)--(0,70)--(70,70)--(70,0)--(0,0); \draw(0,10)--(70,10); \draw(0,20)--(70,20); \draw(0,30)--(70,30); \draw(0,40)--(70,40); \draw(0,50)--(70,50); \draw(0,60)--(70,60); \draw(10,0)--(10,70); \draw(20,0)--(20,70); \draw(30,0)--(30,70); \draw(40,0)--(40,70); \draw(50,0)--(50,70); \draw(60,0)--(60,70); \node at (35,65){\large \textbf{24 20 15 32 14 21 36}}; \node at (5,55){\large \textbf{44}}; \node at (65,55){\large \textbf{45}}; \node at (5,45){\large \textbf{16}}; \node at (65,45){\large \textbf{10}}; \node at (5,25){\large \textbf{35}}; \node at (65,25){\large \textbf{22}}; \node at (5,15){\large \textbf{18}}; \node at (65,15){\large \textbf{28}}; \node at (15,5){\large \textbf{42 30 12}}; \node at (56,5){\large \textbf{ 8 40 48}}; }}$
21 заполненное число - многовато. Думаю мой программно-аппаратный комплекс с перебором для N=7 справится, дальше скорее всего нет.

-- Ср дек 10, 2014 14:42:46 --

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

Вот именно это доказать у меня не получилось. А как Вы это сделали?

Я чего то что ли напутал?
Некое подвыражение, гарантированно неотрицательное, стоит в неком общем выражении со знаком минус. Чтобы общее выражение было максимальным, надо чтобы подвыражение было минимальным, в нашем случае равно 0.

[whitefox]

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

Некое подвыражение, гарантированно неотрицательное, стоит в неком общем выражении со знаком минус. Чтобы общее выражение было максимальным, надо чтобы подвыражение было минимальным, в нашем случае равно 0.

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

[Pavlovsky]

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

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

Так и предполагал. Хотел реанимировать свою гипотезу, не получилось. Ну и бог с ней, вроде как и без нее все сходится.

Практика критерий истины.

Проверил формулу

$$D=\mathrm{TM} - \sum\limits_{m=1}^{n^2}\Phi(m)\left(R(m)-(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) $$

на доступных мне решениях.Формула работает!

[whitefox]

Pavlovsky
Верно ли указан интервал суммирования во второй сумме $\left[2,\frac{n^2}2\right]?$
Не правильнее было бы $[1,n^2]?$

[Pavlovsky]

Идет суммирование по множествам $M_k$. Можно конечно использовать $[1,n^2]$ результат суммирования от этого не изменится. Но $\left[2,\frac{n^2}2\right]$ как то нагляднее для практического применения.

[whitefox]

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

Можно конечно использовать $[1,n^2]$ результат суммирования от этого не изменится.

Это точно? Что-то у меня сомнения по этому поводу.

[Pavlovsky]

Для k=1

$$(\bar x_k-\mathrm{med})^2+(\bar y_k-\mathrm{med})^2=0$$

Для $k > \frac{n^2}{2}$

$$\left\lfloor\frac{n^2}k\right\rfloor=0$$

-- Ср дек 10, 2014 16:40:04 --

Ой. Для $k > \frac{n^2}{2}$

$$\left\lfloor\frac{n^2}k\right\rfloor=1$$

Тогда интервал должен быть только $\left[2,\frac{n^2}2\right]$.

-- Ср дек 10, 2014 16:51:39 --

Пример вычисления числа Делакорта на примере для N=7
Первая сумма. Колонка №1 число m. Колонка №2 вклад в сумму.

Цитата:

32 96
21 -294
33 288
6 72
26 -60
25 36
9 186
13 72
5 -36
3 -64
23 -132
12 336
38 -240
8 -72
Итого = 188

Вторая сумма.
Колонка №1 номер k множества $M_k$. Колонка №2 вклад в сумму.

Цитата:

2 1
3 10
4 20
5 4
6 104
8 16
9 6
10 20
11 10
12 16
13 24
14 30
15 32
16 8
17 16
18 6
19 18
21 12
22 10
Итого = 363

57400-188-363=56849

Вот расчет по традиционной формуле:
Колонка №1 номер k множества $M_k$. Колонка №2 $D_k$. Колонка №3 $\varphi (k)$. Колонка №4 сумма.

Цитата:

1 19 208 * 1 = 19 208
2 6 359 * 1 = 6 359
3 2 923 * 2 = 5 846
4 1 790 * 2 = 3 580
5 818 * 4 = 3 272
6 876 * 2 = 1 752
7 518 * 6 = 3 108
8 464 * 4 = 1 856
9 284 * 6 = 1 704
10 191 * 4 = 764
11 131 * 10 = 1 310
12 252 * 4 = 1 008
13 58 * 12 = 696
14 118 * 6 = 708
15 104 * 8 = 832
16 110 * 8 = 880
17 17 * 16 = 272
18 61 * 6 = 366
19 25 * 18 = 450
20 52 * 8 = 416
21 61 * 12 = 732
22 45 * 10 = 450
23 32 * 22 = 704
24 72 * 8 = 576
Результат = 56 849

-- Ср дек 10, 2014 17:13:22 --

Еще пример.
(4,2,7),(3,9,8),(1,5,6)
Первая сумма.
3 6
9 6
8 8
Итого= 20
Вторая сумма
2 2
3 2
4 2
Итого= 6
Результат = 182-20-6=156

Традиционная формула:
1 108 * 1 = 108
2 22 * 1 = 22
3 8 * 2 = 16
4 5 * 2 = 10
Результат = 156

[whitefox]

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

Получилась следующая формула расчета числа Делакорта.

$$D=\mathrm{TM} - \sum\limits_{m=1}^{n^2}\Phi(m)\left(R(m)-(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) $$

,где $TM$ теоретический максимум (верхняя оценка);
$R(m)$ квадрат расстояния от ячейки до центра квадрата, рекомендуемый для числа m в соответсвии с его $\Phi(m)$.

Здесь $\Phi(m)$, определяемую Pavlovsky как:

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

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

нужно заменить на $\widetilde{\Phi}(m)$:

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

$$\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$$

[Pavlovsky]

Точно. Собственно, так я и запрограммировал.

[dimkadimon]

Tomas Rokicki вышел на первое место!

[Pavlovsky]

Забавно. Для четных N координаты центра дробное число.
Штрф для $M_k$ вычисляется по формуле:

$$\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) $$

Если n четно, а $\left\lfloor\frac{n^2}k\right\rfloor$ нечетно, тогда

$$\left\lfloor\frac{n^2}k\right\rfloor^2\left((\bar x_k-\mathrm{med})^2+(\bar y_k-\mathrm{med})^2\right) \ge \frac{1}{2} $$

И соответсвенно штраф для такого $M_k$ не может быть меньше $\frac {\varphi(k)}{2}$, при любом расположении чисел в квадрате.

-- Пт дек 12, 2014 09:55:33 --

Поправка к теоретическому максимуму (верхняя оценка) для четных N

Цитата:

N = 4 3
N = 6 15
N = 8 44
N = 10 115
N = 12 221
N = 14 425
N = 16 729
N = 18 1132
N = 20 1777
N = 22 2591
N = 24 3651
N = 26 5040

[dimkadimon]

Утверждение 1: Если из всех gcd вычесть 1, тогда можно игнорировать все пары чисел (a,b), где gcd(a,b)=1. Это потому что вес таких чисел в числе Делакорт будет 0.

Это мы уже давно знали и тут ничего нового. А вот следующее утверждение кажется новое и может пригодиться.

Утверждение 2: Если из всех дистанций вычесть 1, тогда можно игнорировать все пары чисел (a,b), которые касаются друг друга. То есть все пары где $|a_x-b_x|+|a_y-b_y|=1$. У таких пар чисел вec тоже будет 0.

Для NxN квадрата таких пар будет $2N(N-1)$.