Al Zimmerman - Delacorte Numbers

[Pavlovsky]

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

Формула для $\Delta D$ заработала

Ну и как? Работает быстро?

[dmd]

Пока только проверил правильность счёта. Скорость в реальном поиске ещё не проверял, но и так видно, что быстрее чем

sum(i=1, N-1, sum(j=i+1, N, GCD[X[i],X[j]]*DIST[i,j]));

она работать не будет.

(случайный квадрат и его характеристики для проверки)

? \r dlcw.gp
? dlc()
[14, 17, 13, 24, 4, 7, 10, 19, 9, 20, 23, 5, 15, 11, 22, 25, 2, 16, 21, 1, 12, 3, 6, 8, 18]

X=
(14,17,13,24,4),(7,10,19,9,20),(23,5,15,11,22),(25,2,16,21,1),(12,3,6,8,18),

DN= 4932

PsiX=
[75, 113, 135, 149, 131, 205, 117, 189, 177, 185, 135, 265, 87, 161, 215, 221, 91, 277, 111, 237, 225, 203, 141, 313, 211]

PsiY=
[75, 115, 127, 159, 127, 193, 111, 203, 181, 195, 165, 257, 111, 157, 203, 227, 107, 277, 129, 279, 211, 255, 97, 333, 147]

Phi=
[25, 37, 41, 49, 45, 61, 43, 61, 53, 65, 45, 81, 37, 61, 69, 69, 41, 79, 43, 85, 71, 67, 47, 101, 65]

Dk=
[2500, 700, 232, 176, 60, 83, 32, 28, 10, 9, 1, 25, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

DW= 4932

dDNmin[8,21]= -459
dDNmax[6,18]= 192
3869    4520

? dDN
%46 =
[   0  -69  -92  150   80 -41   60 -169  110  -30 -108  -89   56   13  120  -93  -60  118   30  -93    0   17  176   50  128]

[ -69    0    0   28  -27   0   91    0  168  -82    0   48  174  120  101  -48   39  150  -58    0 -207   64  147  -12  -27]

[ -92    0    0  -39  -60   0   42    0  120  -95    0   40  152   70   56  -64   18   81  -40    0 -324   38   96  -67  -76]

[ 150   28  -39    0  100 -46 -178 -310 -155 -140 -235 -344 -265 -396 -228 -342 -422 -324 -429 -350  -48 -300 -210 -288 -184]

[  80  -27  -60  100    0  41   44 -139   14   52  -68  -23  112 -137  -16  -63  -60   24  -10 -111 -112  -21   96  -16   16]

[ -41    0    0  -46   41   0   87  -24  144  -64    0   24  126  160  169   -8   47  192   94   72  -63  108  191  102   93]

[  60   91   42 -178   44  87    0  -49   20   -6   82  -13    6   25   64   75   16   30 -152   43 -112  105  100    6   24]

[-169    0    0 -310 -139 -24  -49    0    8 -220    0    0   46   40  -11  -96  -17   -4 -102    0 -459  -20  -21 -138 -199]

[ 110  168  120 -155   14 144   20    8    0 -119   72    8   28  -62  -54  -40  -64 -111 -120  -72 -366   -6  -58 -231  -78]

[ -30  -82  -95 -140   52 -64   -6 -220 -119    0 -155  -90  -41 -194  -16   12 -178 -144  -65   -4 -268  -78  -14  -48   60]

[-108    0    0 -235  -68   0   82    0   72 -155    0   40  104  150   96  -32   34  165  -96    0 -180   30   88   17  -76]

[ -89   48   40 -344  -23  24  -13    0    8  -90   40    0   22   96   81    0   15   54  -90   96 -267   56   47    0  -47]

[  56  174  152 -265  112 126    6   46   28  -41  104   22    0   68  100   62    6  -17  -52  150 -280   80   28  -25    8]

[  13  120   70 -396 -137 160   25   40  -62 -194  150   96   68    0  -29   80   61   -2  -32    0 -341   72    5 -108 -193]

[ 120  101   56 -228  -16 169   64  -11  -54  -16   96   81  100  -29    0   81   40   -4   58   17 -256   67   64  -40  -40]

[ -93  -48  -64 -342  -63  -8   75  -96  -40   12  -32    0   62   80   81    0   -5  132 -102    0  -71   44   95   78   13]

[ -60   39   18 -422  -60  47   16  -17  -64 -178   34   15    6   61   40   -5    0   50 -108    3 -264    5   -4  -30 -120]

[ 118  150   81 -324   24 192   30   -4 -111 -144  165   54  -17   -2   -4  132   50    0  -81   36 -144  106   22    0  -88]

[  30  -58  -40 -429  -10  94 -152 -102 -120  -65  -96  -90  -52  -32   58 -102 -108  -81    0  122 -406  -24  -26   -9   26]

[ -93    0    0 -350 -111  72   43    0  -72   -4    0   96  150    0   17    0    3   36  122    0 -423  -20   15  -42  -99]

[   0 -207 -324  -48 -112 -63 -112 -459 -366 -268 -180 -267 -280 -341 -256  -71 -264 -144 -406 -423    0 -149 -120 -132  -80]

[  17   64   38 -300  -21 108  105  -20   -6  -78   30   56   80   72   67   44    5  106  -24  -20 -149    0   29   28  -33]

[ 176  147   96 -210   96 191  100  -21  -58  -14   88   47   28    5   64   95   -4   22  -26   15 -120   29    0   10    0]

[  50  -12  -67 -288  -16 102    6 -138 -231  -48   17    0  -25 -108  -40   78  -30    0   -9  -42 -132   28   10    0  -36]

[ 128  -27  -76 -184   16  93   24 -199  -78   60  -76  -47    8 -193  -40   13 -120  -88   26  -99  -80  -33    0  -36    0]

Если раскоментарить соответсвующую строчку в проверке и поменять местами 8-е и 21-е числа в векторе $X$, то после запуска получим число Delacorte именно 3869, как и предсказывает формула whitefox. А если поменяем местами 6-е и 18-е числа, то получим число Delacorte 4520.

Вся проверка:

dlc()=
{
n= 5; N= n^2; x= vector(N); Dmax= 0; Dmin= 10^100;
s= Set(); for(i=1, N, s= setunion(s, [i]));

GCD= matrix(N, N, i, j, gcd(i, j)-1);

DIST= matrix(N, N);
for(a=1, N,
 ia= a\n; ja= a%n; if(ja, ia++, ja= n);
 for(b=1, N,
  ib= b\n; jb= b%n; if(jb, ib++, jb= n);
  if(ib > ia || (ia == ib && jb > ja), DIST[a,b]= (ia - ib)^2 + (ja - jb)^2, DIST[a,b]= 0)
));

 S= s; X= x; i= N;
 while(i, r= random(#S)+1; t= S[r]; S= setminus(S, [t]); X[i]= t; i--);

\\X= [14, 17, 13, 24, 4, 7, 10, 19, 9, 20, 23, 5, 15, 11, 22, 25, 2, 16, 21, 1, 12, 3, 6, 8, 18];

 Do= sum(i=1, N-1, sum(j=i+1, N, GCD[X[i],X[j]]*DIST[i,j]));

 print(X); print();
 print("X=");
 for(i=1, N, if((i%n)==1, print1("(",X[i],","), if((i%n)==0, print1(X[i],"),"), print1(X[i],",")))); print(); print();
 print("DN= ",Do + N^2*(N-1)/6); print();

 PsiX=PsiY=Phi=Dk= vector(N);
 for(k=1, N,
  Xk=Yk=Px=Py=F=Sk= 0;
  for(i=1, N, a= X[i]; if(!(a%k), xa= i\n; ya= i%n; if(ya, xa++, ya= n); Xk+= xa; Yk+= ya; Sk+= xa^2+ya^2));
  for(i=1, N, m= X[i]; if(!(m%k), PsiX[m]+= eulerphi(k)*Xk; PsiY[m]+= eulerphi(k)*Yk; Phi[m]+= eulerphi(k)*(N\k)));
  Dk[k]= (N\k)*Sk-(Xk^2+Yk^2)
 );

 print("PsiX="); print(PsiX); print(); print("PsiY="); print(PsiY); print(); print("Phi="); print(Phi); print();
 print("Dk="); print(Dk); print();
 DW= sum(k=2, N\2, eulerphi(k)*Dk[k]);
 print("DW= ",DW + N^2*(N-1)/6); print();

 dDN= matrix(N, N);
 for(a=1, N,
  xa= a\n; ya= a%n; if(ya, xa++, ya= n);
  for(b=1, N,
   xb= b\n; yb= b%n; if(yb, xb++, yb= n);
   A= (xb^2-xa^2+yb^2-ya^2)*(Phi[X[a]]-Phi[X[b]]);
   B= ((xb-xa)^2+(yb-ya)^2)*(X[a]+X[b]-2*gcd(X[a],X[b]));
   Cx= (xb-xa)*(PsiX[X[a]]-PsiX[X[b]]);
   Cy= (yb-ya)*(PsiY[X[a]]-PsiY[X[b]]);
   d= A-B-2*(Cx+Cy); dDN[a,b]= d;
   if(d<Dmin, Dmin= d; amin= a; bmin= b); if(d>Dmax, Dmax= d; amax= a; bmax= b)
 ));

 print("dDNmin[",amin,",",bmin,"]= ",Dmin);
 print("dDNmax[",amax,",",bmax,"]= ",Dmax);
 print(Dt + N^2*(N-1)/6 + Dmin,"    ",Dt + N^2*(N-1)/6 + Dmax); print();

};

Вижу, что смогу до вхождения в поисковые циклы сделать предварительно вычисленными матрицы $A$ и $B$. И вроде это всё. Остальное придётся на ходу вычислять внутри циклов.

[Pavlovsky]

Для заданного N выпишем простые числа такие что: $p\le \frac{N^2}{2}$ , $2p\le N^2$ , $3p > N^2$
Например для N=6 такие числа 13,17.

Утверждение. Пусть у нас есть два простых числа $p_1 < p_2$, удовлетворяющих вышеприведенному условию. Тогда в максимальном решении, $\mathrm{distance}^2(p_1,2p_1) \le \mathrm{distance}^2(p_2,2p_2)$.

[Herbert Kociemba]

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

Вы совершенно правы. Обновления $\Psi_x,\Psi_y$ только для $a$ и $b$ совершенно не достаточно. Нужно обновлять эти значения для всех $m$ таких, что $\gcd(m,a)\ne\gcd(m,b)$ по следующим формулам:

$$\Psi'_x(m)=\Psi_x(m)+(x_b-x_a)(\gcd(m,a)-\gcd(m,b))$$

$$\Psi'_y(m)=\Psi_y(m)+(y_b-y_a)(\gcd(m,a)-\gcd(m,b))$$

Но выполнять эти вычисления нужно только при фактическом выполнении обмена $a\leftrightarrow b.$ Сложность обновления составит $O(n^2).$

I think this update is only O(Log(n)). Because you only have to update if gcd(m,a)>1 or gcd(m,b)> 1. And in this case m is an element of the union U of the divisors of a and the divisors of b. And U will on average have 2*Log(n) elements.

[Yadryara]

Господа.

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

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

N=5, MAX=6149

Вот моё микроисследование:

$$\begin{array}{rrrrrrrrrrrrrrrrrrrrrr} 25 & 26 & 27 & 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 & 41 &\;\; 43 &\;\; 45 &\;\; 47 & 48 & 49 \\ 99 & 51 & 76 & 56 & 66 & 46 & 68 & 45 & 51 & 43 & 66 & 20 & 8 & 19 & 48 & 40 & 62 & 41 & 32 & 41 & 8 & 26 \\ \end{array}$$

В верхней строке — последние 2 цифры числа Делакорта для того или иного локального максимума. Опущены первые две цифры, а именно "61". Например, запись "31" означает "6131".

В нижней строке — количество достижений этого локального максимума.

Локальным максимумом считал расстановку, для которой никакая парная перестановка не даёт увеличения числа Делакорта.

Наглядно показано, что чаще всего в данном диапазоне($D>6124$) встречается локальный максимум $6125$ — 99 раз.

Весьма редко встречаются числа $6137$ и $6148$ — по 8 раз, а числа $6142$, $6144$, $6146$ не встречаются вовсе.

Как и числа, превышающие $6149$.

Доказательством нахождения глобального максимума для 5-го порядка, это, конечно, не является. Выглядит ли данная статистика достаточно убедительно, чтобы прекратить поиск для этого порядка, вот в чём вопрос.

[sevir]

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

I think this update is only O(Log(n)).

Эксперименты с $n = 27$ это подтверждают, причем с довольно малым множителем.

[Pavlovsky]

Утверждение. Четность числа Делакорта зависит только от расположения четных чисел в матрице. Если сумма квадратов растояний между четными числами ($D_2$) четна, то и число Делакорта четно.

-- Ср ноя 26, 2014 10:37:50 --

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

Простые числа которые больше floor(N*N/2) можно ставить в середину квадрата.

Пусть $x_s=(N+1)/2$ координата x середины квадрата. Пусть $\bar x_k$ арифметическое среднее координат x ячеек с числами кратными k.

Утверждение. Если для всех k верно $|x_s-\bar x_k|\le \frac{1}{2}$, тогда верно утверждение dimkadimon.

Гипотеза. В оптимальном максимальном решении. Центр масс ячеек с числами кратными k, находится в районе середины квадрата.

[Herbert Kociemba]

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

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

I think this update is only O(Log(n)).

Эксперименты с $n = 27$ это подтверждают, причем с довольно малым множителем.

Sorry, I made a mistake. It is indeed O(N^2) because m can be of course greater than a or b. If for example a=2 and b=3, you have to update for all m which are multiples of 2 or 3.

[Yadryara]

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

Утверждение. Четность числа Делакорта зависит только от расположения четных чисел в матрице. Если сумма квадратов растояний между четными числами ($D_2$) четна, то и число Делакорта четно.

Верно. Это моментально следует из того, что единственным нечётным $\varphi(k)$ при $k>1$ является $\varphi(2)=1$. А в данной задаче $k>1$.

Собственно говоря, это было уже давно понятно. Интересно, как это можно использовать для решения основной задачи. При малых $n$ это позволяет несколько сократить перебор.

[Pavlovsky]

Yadryara в сообщении #936291 писал(а):

Интересно, как это можно использовать для решения основной задачи.

Фиг его знает. Есть свойство, я его озвучил, может кому пригодится. Ну например если хотим получить для N=5 число Делакорта 6150, тогда

Yadryara в сообщении #936291 писал(а):

При малых $n$ это позволяет несколько сократить перебор.

Впрочем отсутсвие решения 6150, совсем не означает, что 6149 теоретический максимум.

[Yadryara]

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

Впрочем отсутсвие решения 6150, совсем не означает, что 6149 теоретический максимум.

Да. Если считать, распространив Ваше правило плотных упаковок и на "антиплотные", то для 5-го порядка границы числа Делакорта будут $3146$ — $7084$.

[dimkadimon]

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

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

В итоге формула получилась похожая, но немного другая особенно для B

Было бы интересно взглянуть. Не поделитесь?

Показываю только B, потому что остальные такие же как у вас:

$B=((x_a-x_b)^2+(y_a-y_b)^2)(2(\gcd(a,b)-1)-E(a)-E(b)),$

$E(m)=\sum_{k|m} \varphi(k).$

Для всех $\sum_{k|m}$ я использую $k \in [2,N^2/2]$. Скорее всего формула равна вашей и тут ничего нового.

[sevir]

Как я понял, регистрация сайта http://www.azspcs.net/ "приказала долго жить".

[Pavlovsky]

Вроде как процесс перезда идет.
https://groups.yahoo.com/neo/groups/AlZ ... sages/6409

-- Чт ноя 27, 2014 09:37:55 --

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

Утверждение. Пусть у нас есть два простых числа $p_1 < p_2$, удовлетворяющих вышеприведенному условию. Тогда в максимальном решении, $\mathrm{distance}^2(p_1,2p_1) \le \mathrm{distance}^2(p_2,2p_2)$.

Это утверждение можно немного обобщить.
Утверждение. Пусть у нас есть два простых числа $p_1 < p_2$, такие что $\left\lfloor\frac{N^2}{p_1}\right\rfloor=\left\lfloor\frac{N^2}{p_2}\right\rfloor$ Тогда в максимальном решении, $D_{p_1} \le D_{p_2}$. Где $D_{p_1} (D_{p_2})$ сумма квадратов расстояний между числами кратными $p_1 (p_2)$

[sevir]

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

Вроде как процесс перезда идет.

А Вы не процитируете: там регистрация требуется.