Al Zimmerman - Delacorte Numbers

[sevir]

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

Все числа $\Phi(m),\gcd(ab)$ являются константами и вычислены заранее.

Хочется также отметить, что и индексные множества, по которым ведется суммирование, тоже вычисляются заранее.

-- 23.11.2014, 04:20 --

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

Также должно быть:

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

А как эта формула работает, если, например, $a = 3$ для матрицы второго порядка?

[sevir]

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

Если поменять местами числа $a$ и $b$, то изменение числа Делакорта вычисляется по формуле:

$$\Delta D=A-B-2C_x-2C_y$$

Поменяем местами два числа: тогда левая часть поменяет знак, а в правой не изменит знак только $B$. Сложим почленно 2 уравнения и получим:$$\/0=-2*B$. Впечатляет.

[dmd]

Помогите найти ошибку на примере случайного квадрата $5\times 5$

(квадрат)

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

DN= 4697

PsiX=
[75, 72, 150, 152, 300, 168, 420, 352, 324, 240, 880, 384, 468, 252, 360, 512, 1088, 432, 1368, 640, 1260, 1100, 2530, 960, 2500]

PsiY=
[75, 72, 138, 152, 500, 120, 294, 256, 378, 400, 330, 288, 468, 336, 600, 128, 544, 324, 1368, 800, 252, 440, 1518, 768, 2500]

Phi=
[25, 24, 48, 48, 100, 48, 126, 96, 108, 80, 220, 96, 156, 84, 120, 128, 272, 108, 342, 160, 252, 220, 506, 192, 500]

dDNmin[11,16]= -117
dDNmax[1,25]= 15232
?
? dDN
%28 =
[    0    -4   60   90  1536   112  510  462  742 1292  1620  826  952  748 2020   942 2410 1008 5682 3450  3712 3308  9580 4150 15232]

[   -4     0    9   24   927    88  383  340  423  880  1681  632  595  480 1341  1140 2223  824 4127 2556  3999 3200  8187 3400 11947]

[   60     9    0   23   592    93  368  251  216  565  2056  447  352  189  864  1431 2396  657 3100 1843  4800 3337  7664 2919  9648]

[   90    24   23    0   221   164  625  376  153  268  2879  512  449   56  419  2088 3129  676 2697 1376  5853 3928  8081 2688  8105]

[ 1536   927  592  221     0  1531 1844  973  316  -65  5320 1361 1120   35   40  4025 5136 1231 3000 1005  8896 5775 10000 2905  7680]

[  112    88   93  164  1531     0  103  120  567 1280   549  372  503  584 1881   344 1063  576 4051 2856  2079 1864  6131 3132 11967]

[  510   383  368  625  1844   103    0   61  496 1467   628   61  108  511 1672   577  832  299 2712 2469  2716 1863  4948 2581  9468]

[  462   340  251  376   973   120   61    0  145  776  1047  -24  -87   68  783   960 1021   88 1489 1376  3085 1876  4197 1824  6513]

[  742   423  216  153   316   567  496  145    0  279  2340  321  164  -45  312  2013 2200  495 1264  881  5076 3023  5084 1809  5220]

[ 1292   880  565  268   -65  1280 1467  776  279    0  4177 1036  915  128   25  3400 3931  992 1655  600  7095 4416  6735 1940  4515]

[ 1620  1681 2056 2879  5320   549  628 1047 2340 4177     0  267  976 1869 4176  -117  272  625 4240 4647   888 1045  4232 3387 11960]

[  826   632  447  512  1361   372   61  -24  321 1036   267    0   37  248 1179   408  149  -12 1469 1552  1413  760  2269 1440  6333]

[  952   595  352  449  1120   503  108  -87  164  915   976   37    0  215 1000  1285  800  235  936 1425  3008 1715  2512 1565  4960]

[  748   480  189   56    35   584  511   68  -45  128  1869  248  215    0  177  1860 1635  328  395  428  4095 2176  2775  968  2735]

[ 2020  1341  864  419    40  1881 1672  783  312   25  4176 1179 1000  177    0  3723 3620 1005  860  255  6840 3965  4720 1395  2360]

[  942  1140 1431 2088  4025   344  577  960 2013 3400  -117  408 1285 1860 3723     0  369  824 3933 4160   345  628  2985 2960 10013]

[ 2410  2223 2396 3129  5136  1063  832 1021 2200 3931   272  149  800 1635 3620   369    0  347 2320 3573   976  455  1480 2125  7320]

[ 1008   824  657  676  1231   576  299   88  495  992   625  -12  235  328 1005   824  347    0  415  936  1635  584   575  540  2835]

[ 5682  4127 3100 2697  3000  4051 2712 1489 1264 1655  4240 1469  936  395  860  3933 2320  415    0  465  5560 2615  1616  493  1600]

[ 3450  2556 1843 1376  1005  2856 2469 1376  881  600  4647 1552 1425  428  255  4160 3573  936  465    0  6341 3420  3125  632   625]

[ 3712  3999 4800 5853  8896  2079 2716 3085 5076 7095   888 1413 3008 4095 6840   345  976 1635 5560 6341     0  431  2864 3645 11328]

[ 3308  3200 3337 3928  5775  1864 1863 1876 3023 4416  1045  760 1715 2176 3965   628  455  584 2615 3420   431    0   683 1480  6075]

[ 9580  8187 7664 8081 10000  6131 4948 4197 5084 6735  4232 2269 2512 2775 4720  2985 1480  575 1616 3125  2864  683     0  653  3840]

[ 4150  3400 2919 2688  2905  3132 2581 1824 1809 1940  3387 1440 1565  968 1395  2960 2125  540  493  632  3645 1480   653    0   645]

[15232 11947 9648 8105  7680 11967 9468 6513 5220 4515 11960 6333 4960 2735 2360 10013 7320 2835 1600  625 11328 6075  3840  645     0]

(код)

 PsiX=PsiY=Phi= vector(N);
 for(k=1, N,
  Xk=Yk=Px=Py=F= 0;
  for(i=1, N, a= X[i]; if(!(a%k), ia= a\n; ja= a%n; if(ja, ia++, ja= n); Xk+= ia; Yk+= ja));
  for(i=1, k, Px+= eulerphi(k)*Xk; Py+= eulerphi(k)*Yk; F+= eulerphi(k)*(N\k));
  PsiX[k]= Px; PsiY[k]= Py; Phi[k]= F
 );

 print("PsiX="); print(PsiX); print(); print("PsiY="); print(PsiY); print(); print("Phi="); print(Phi); 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[a]-Phi[b]);
   B= ((xb-xa)^2+(yb-ya)^2)*(a+b-2*gcd(a,b));
   Cx= (xb-xa)*(PsiX[a]-PsiX[b]);
   Cy= (yb-ya)*(PsiY[a]-PsiY[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);

[sevir]

dmd

Вы прочитали мое последнее сообщение? Полагаю, что сначала ошибку должен исправить автор формул.

[dimkadimon]

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

Помогите найти ошибку на примере случайного квадрата $5\times 5$

(квадрат)

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

DN= 4697

PsiX=
[75, 72, 150, 152, 300, 168, 420, 352, 324, 240, 880, 384, 468, 252, 360, 512, 1088, 432, 1368, 640, 1260, 1100, 2530, 960, 2500]

PsiY=
[75, 72, 138, 152, 500, 120, 294, 256, 378, 400, 330, 288, 468, 336, 600, 128, 544, 324, 1368, 800, 252, 440, 1518, 768, 2500]

Phi=
[25, 24, 48, 48, 100, 48, 126, 96, 108, 80, 220, 96, 156, 84, 120, 128, 272, 108, 342, 160, 252, 220, 506, 192, 500]

dDNmin[11,16]= -117
dDNmax[1,25]= 15232
?
? dDN
%28 =
[    0    -4   60   90  1536   112  510  462  742 1292  1620  826  952  748 2020   942 2410 1008 5682 3450  3712 3308  9580 4150 15232]

[   -4     0    9   24   927    88  383  340  423  880  1681  632  595  480 1341  1140 2223  824 4127 2556  3999 3200  8187 3400 11947]

[   60     9    0   23   592    93  368  251  216  565  2056  447  352  189  864  1431 2396  657 3100 1843  4800 3337  7664 2919  9648]

[   90    24   23    0   221   164  625  376  153  268  2879  512  449   56  419  2088 3129  676 2697 1376  5853 3928  8081 2688  8105]

[ 1536   927  592  221     0  1531 1844  973  316  -65  5320 1361 1120   35   40  4025 5136 1231 3000 1005  8896 5775 10000 2905  7680]

[  112    88   93  164  1531     0  103  120  567 1280   549  372  503  584 1881   344 1063  576 4051 2856  2079 1864  6131 3132 11967]

[  510   383  368  625  1844   103    0   61  496 1467   628   61  108  511 1672   577  832  299 2712 2469  2716 1863  4948 2581  9468]

[  462   340  251  376   973   120   61    0  145  776  1047  -24  -87   68  783   960 1021   88 1489 1376  3085 1876  4197 1824  6513]

[  742   423  216  153   316   567  496  145    0  279  2340  321  164  -45  312  2013 2200  495 1264  881  5076 3023  5084 1809  5220]

[ 1292   880  565  268   -65  1280 1467  776  279    0  4177 1036  915  128   25  3400 3931  992 1655  600  7095 4416  6735 1940  4515]

[ 1620  1681 2056 2879  5320   549  628 1047 2340 4177     0  267  976 1869 4176  -117  272  625 4240 4647   888 1045  4232 3387 11960]

[  826   632  447  512  1361   372   61  -24  321 1036   267    0   37  248 1179   408  149  -12 1469 1552  1413  760  2269 1440  6333]

[  952   595  352  449  1120   503  108  -87  164  915   976   37    0  215 1000  1285  800  235  936 1425  3008 1715  2512 1565  4960]

[  748   480  189   56    35   584  511   68  -45  128  1869  248  215    0  177  1860 1635  328  395  428  4095 2176  2775  968  2735]

[ 2020  1341  864  419    40  1881 1672  783  312   25  4176 1179 1000  177    0  3723 3620 1005  860  255  6840 3965  4720 1395  2360]

[  942  1140 1431 2088  4025   344  577  960 2013 3400  -117  408 1285 1860 3723     0  369  824 3933 4160   345  628  2985 2960 10013]

[ 2410  2223 2396 3129  5136  1063  832 1021 2200 3931   272  149  800 1635 3620   369    0  347 2320 3573   976  455  1480 2125  7320]

[ 1008   824  657  676  1231   576  299   88  495  992   625  -12  235  328 1005   824  347    0  415  936  1635  584   575  540  2835]

[ 5682  4127 3100 2697  3000  4051 2712 1489 1264 1655  4240 1469  936  395  860  3933 2320  415    0  465  5560 2615  1616  493  1600]

[ 3450  2556 1843 1376  1005  2856 2469 1376  881  600  4647 1552 1425  428  255  4160 3573  936  465    0  6341 3420  3125  632   625]

[ 3712  3999 4800 5853  8896  2079 2716 3085 5076 7095   888 1413 3008 4095 6840   345  976 1635 5560 6341     0  431  2864 3645 11328]

[ 3308  3200 3337 3928  5775  1864 1863 1876 3023 4416  1045  760 1715 2176 3965   628  455  584 2615 3420   431    0   683 1480  6075]

[ 9580  8187 7664 8081 10000  6131 4948 4197 5084 6735  4232 2269 2512 2775 4720  2985 1480  575 1616 3125  2864  683     0  653  3840]

[ 4150  3400 2919 2688  2905  3132 2581 1824 1809 1940  3387 1440 1565  968 1395  2960 2125  540  493  632  3645 1480   653    0   645]

[15232 11947 9648 8105  7680 11967 9468 6513 5220 4515 11960 6333 4960 2735 2360 10013 7320 2835 1600  625 11328 6075  3840  645     0]

(код)

 PsiX=PsiY=Phi= vector(N);
 for(k=1, N,
  Xk=Yk=Px=Py=F= 0;
  for(i=1, N, a= X[i]; if(!(a%k), ia= a\n; ja= a%n; if(ja, ia++, ja= n); Xk+= ia; Yk+= ja));
  for(i=1, k, Px+= eulerphi(k)*Xk; Py+= eulerphi(k)*Yk; F+= eulerphi(k)*(N\k));
  PsiX[k]= Px; PsiY[k]= Py; Phi[k]= F
 );

 print("PsiX="); print(PsiX); print(); print("PsiY="); print(PsiY); print(); print("Phi="); print(Phi); 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[a]-Phi[b]);
   B= ((xb-xa)^2+(yb-ya)^2)*(a+b-2*gcd(a,b));
   Cx= (xb-xa)*(PsiX[a]-PsiX[b]);
   Cy= (yb-ya)*(PsiY[a]-PsiY[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);

Надо N*N/k, а у вас N/k. Суммировать надо от 2 до N*N/2. Еще мне кажется оригинальная формула не совсем работает, особенно B.

[sevir]

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

Еще мне кажется оригинальная формула не совсем работает, особенно B.

B принципиально правильно работать не может, что я выше и показал. Остальные члены правильно себя ведут, вопрос только в том, насколько правильно.

[dmd]

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

Надо N*N/k, а у вас N/k.

Извиняюсь, забыл скопировать первую строчку. У меня несколько другие обозначения, $N$ это 25 (квадрат 5х5). Т.е. там вначале еще строчка

n=5;N=n^2;

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

Суммировать надо от 2 до N*N/2.

Вот в этом месте больше всего непонятно. Формула для $\Delta D$ содержит $a$ и $b$, которые должны меняться от 1 до 25 (квадрат 5х5), они не могут меняться от 2 до 12. Впрочем первая формула для $D$, в которой соответствующую сумму я правильно посчитал от от 2 до 12, тоже не дала (в моём изложении) нужного значения.

-- Пн ноя 24, 2014 10:54:44 --

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

[dmd]

Ага, я нашёл свою ошибку и теперь первая формула для полного $D$ у меня правильно считается. Но формула для $\Delta D$ под вопросом.

Давайте сверим для случайного квадрата векторы $\Psi_x$, $\Psi_y$, $\Phi$:

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

DN= 4715

PsiX=
[75, 74, 174, 152, 260, 156, 504, 384, 324, 200, 990, 384, 156, 420, 480, 640, 816, 108, 1368, 480, 1008, 880, 506, 960, 1000]

PsiY=
[75, 76, 126, 128, 280, 132, 420, 160, 324, 280, 660, 240, 468, 336, 120, 128, 1360, 108, 684, 640, 756, 880, 2024, 576, 2000]

Phi=
[25, 24, 48, 48, 100, 48, 126, 96, 108, 80, 220, 96, 156, 84, 120, 128, 272, 108, 342, 160, 252, 220, 506, 192, 500]

[sevir]

dmd
Я ведь указал на явную ошибку в исходных формулах whitefox'а: для чего тогда что-то с чем-то сверять и отнимать у людей время?

[whitefox]

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

Почему при перестановке двух чисел в квадрате оказалось не нужным полностью пересчитать таблицы $\Psi_x$ и $\Psi_y$, а достаточно только в них пересчитать по паре чисел формулами

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

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

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

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


Ну т.е. хорошо если это так. Но на первый взгляд выглядит неправдоподобно легко.

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

The reason is that I think it is not sufficient to update only $\Psi_x()$ and $\Psi_y()$ for a and b but also you have to update it for all divisors of a and b.

Вы совершенно правы. Обновления $\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).$ При этом оценка $O(1)$ остаётся справедливой для вычисления $\Delta D.$ То есть данный метод "зеркален" второму методу dimkadimon. Там сложность вычисления $\Delta D$ есть $O(n^2)$, а сложность обмена $a\leftrightarrow b$ есть $O(1).$ При предложенном подходе ускорение достигается за счёт того, что обмены $a\leftrightarrow b$ производятся значительно реже чем вычисление $\Delta D.$

-- 24 ноя 2014, 15:22 --

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

Поменяем местами два числа: тогда левая часть поменяет знак, а в правой не изменит знак только $B$. Сложим почленно 2 уравнения и получим: $0=-2B$. Впечатляет.

Обратите внимание, что формула для $\Delta D$ симметрична по $a$ и $b.$ Вот, что получится при замене в формуле $a\leftrightarrow b:$

$$A=\left(x^2_a-x^2_b+y^2_a-y^2_b\right)\left(\Phi(b)-\Phi(a)\right)=\left(x^2_b-x^2_a+y^2_b-y^2_a\right)\left(\Phi(a)-\Phi(b)\right)$$

$$C_x=(x_a-x_b)\left(\Psi_x(b)-\Psi_x(a)\right)=(x_b-x_a)\left(\Psi_x(a)-\Psi_x(b)\right)$$

$$C_y=(y_a-y_b)\left(\Psi_y(b)-\Psi_y(a)\right)=(y_b-y_a)\left(\Psi_y(a)-\Psi_y(b)\right)$$

Как видите, знак не меняется у всех компонент $\Delta D.$

[whitefox]

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

А как эта формула работает, если, например, $a = 3$ для матрицы второго порядка?

Порядок матрицы в эту формулу не входит, поэтому она работает на матрицах второго порядка точно также как и на матрицах любого другого порядка. Например, $a=3,b=1$ тогда $B=2((x_3-x_1)^2+(y_3-y_1)^2).$

[sevir]

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

Обратите внимание, что формула для $\Delta D$ симметрична по $a$ и $b.$

Я не про это: если бы она не была симметрична в том смысле, о котором Вы пишете, то ваши формулы вообще потеряли бы всякий смысл. Я говорил о том, что мы рассматриваем две разные матрицы, которые отличаются только перестановкой двух элементов. И к этим элементам применяем ваше преобразование как в первой матрице, так и во второй. Тогда числа Делакорта должны отличаться только знаками. Но этого не будет из-за того, о чем я уже ранее говорил.

-- 24.11.2014, 16:17 --

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

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

А как эта формула работает, если, например, $a = 3$ для матрицы второго порядка?

Порядок матрицы в эту формулу не входит, поэтому она работает на матрицах второго порядка точно также как и на матрицах любого другого порядка. Например, $a=3,b=1$ тогда $B=2((x_3-x_1)^2+(y_3-y_1)^2).$

Я говорил о 3-ке, привязанной именно к матрице второго порядка, т.к. она только в ней лежит за "экватором": поменяв местами тройку и единицу, мы ничего не изменим, но для пары $a=3,b=2$ $B$ будет одно, а для пары $a=1,b=2$ $B$ будет другим.

[whitefox]

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

Тогда числа Делакорта должны отличаться только знаками. Но этого не будет из-за того, о чем я уже ранее говорил.

Вы не учли, что эти матрицы имеют различные значения $\Psi_x,\Psi_y$. Как результат -- их $\Delta D$ различаются только знаком.

-- 24 ноя 2014, 16:22 --

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

поменяв местами тройку и единицу, мы ничего не изменим, но для пары $a=3,b=2$ $B$ будет одно, а для пары $a=1,b=2$ $B$ будет другим.

А $\Delta D$ тоже будет разным?

[sevir]

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

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

Тогда числа Делакорта должны отличаться только знаками. Но этого не будет из-за того, о чем я уже ранее говорил.

Вы не учли, что эти матрицы имеют различные значения $\Psi_x,\Psi_y$. Как результат -- их $\Delta D$ различаются только знаком.

Прямой расчет показывает (хотя это и так понятно), что они будут отличаться только знаками: могу привести его для матрицы второго порядка.

-- 24.11.2014, 16:32 --

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

А $\Delta D$ тоже будет разным?

Естественно: ведь я беру новую матрицу с переставленными тройкой и единицей, хотя $\Delta D$ не должно меняться.

[whitefox]

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

Естественно: ведь я беру новую матрицу с переставленными тройкой и единицей, хотя $\Delta D$ не должно меняться.

Пример приведите, пожалуйста.

-- 24 ноя 2014, 16:57 --

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

But I claim that the algorithm of whitefox is not O(1) but O(Log(N))=O(Log(N^2)) as I wrote before.

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

In fact, Whitefox' algorithm is O(1) for computing the score of swapping a pair.

But the swapping requires to update at most 29+23 products, for example when swapping 720 and 672 on a 27x27 grid.
So the algorithm is indeed O(1+log(n))

Можно $\Psi_x,\Psi_y$ не хранить, а вычислять в процессе вычисления $\Delta D.$ При этом хранить $X_k,Y_k$ и обновлять их при фактическом выполнении обмена $a\leftrightarrow b.$ В этом случае сложность вычисления $\Delta D$ и сложность пересчёта $X_k,Y_k$ будет пропорциональна числу делителей $a$ и $b,$ то есть в среднем $O(\log n).$