2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 16, 17, 18, 19, 20, 21, 22 ... 25  След.
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение10.12.2014, 11:00 
Заслуженный участник
Аватара пользователя


19/12/10
1546
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.$

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение10.12.2014, 11:43 
Аватара пользователя


21/02/10
1594
Екатеринбург
$$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) В алгоритме перебора основанном на постепенном заполнении квадрата числами, главная проблема оценить переспективность частично заполненного квадрата. В таких алгоритмах такой способ расчета числа Делакорта может оказаться полезным.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение10.12.2014, 12:32 
Заслуженный участник
Аватара пользователя


19/12/10
1546
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$$

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

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение10.12.2014, 12:37 
Аватара пользователя


21/02/10
1594
Екатеринбург
Полуручные вычислительные эксперименты, с одним из моих решений для 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.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение10.12.2014, 12:49 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Pavlovsky в сообщении #943594 писал(а):
Некое подвыражение, гарантированно неотрицательное, стоит в неком общем выражении со знаком минус. Чтобы общее выражение было максимальным, надо чтобы подвыражение было минимальным, в нашем случае равно 0.

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

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение10.12.2014, 12:58 
Аватара пользователя


21/02/10
1594
Екатеринбург
whitefox в сообщении #943598 писал(а):
Первый и второй члены выражения зависимы. Нет никакой гарантии, что при уменьшении второго члена до нуля, первый также не уменьшится, причём на большую величину.


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

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

Проверил формулу
$$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) $$
на доступных мне решениях.Формула работает!

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение10.12.2014, 13:16 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение10.12.2014, 13:36 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение10.12.2014, 14:26 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Pavlovsky в сообщении #943614 писал(а):
Можно конечно использовать $[1,n^2]$ результат суммирования от этого не изменится.

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

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение10.12.2014, 14:35 
Аватара пользователя


21/02/10
1594
Екатеринбург
Для 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

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение11.12.2014, 15:59 
Заслуженный участник
Аватара пользователя


19/12/10
1546
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$$

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение11.12.2014, 17:19 
Аватара пользователя


21/02/10
1594
Екатеринбург
Точно. Собственно, так я и запрограммировал.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение12.12.2014, 02:24 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Tomas Rokicki вышел на первое место!

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение12.12.2014, 07:40 
Аватара пользователя


21/02/10
1594
Екатеринбург
Забавно. Для четных 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

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение13.12.2014, 03:16 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Утверждение 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)$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 373 ]  На страницу Пред.  1 ... 16, 17, 18, 19, 20, 21, 22 ... 25  След.

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



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

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


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

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