Al Zimmerman - Delacorte Numbers

[sevir]

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

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

Завтра с утра: сейчас машина, на которой затронута эта тема, молотит под линуксом.

[whitefox]

Коль возникают сомнения в правильности формулы для $\Delta D,$ приведу её вывод:

Так как $D_1=\frac{n^4(n^2-1)}6$, а для $k>\frac{n^2}2\quad D_k=0$, то

$$D=\sum\limits_{k=1}^{n^2}\varphi(k)D_k$$

$$\Delta D=S_1+S_2$$

$$S_1=\sum_{k\mid a\atop k\nmid b}\varphi(k)\Delta D_k$$

$$S_2=\sum_{k\mid b\atop k\nmid a}\varphi(k)\Delta D_k$$

Для случая $k\mid a,k\nmid b:$

$$\Delta D_k=\left\lfloor\frac{n^2}k\right\rfloor(x_b^2-x_a^2+y_b^2-y_a^2)-((x_b-x_a)(2X_k+x_b-x_a)+(y_b-y_a)(2Y_k+y_b-y_a))=$$

$$=\left\lfloor\frac{n^2}k\right\rfloor(x_b^2-x_a^2+y_b^2-y_a^2)-((x_b-x_a)^2+(y_b-y_a)^2)-$$ $$-2(x_b-x_a)X_k-2(y_b-y_a)Y_k$$

Поэтому:

$$S_1=(x_b^2-x_a^2+y_b^2-y_a^2)(\Phi(a)-\Phi(\gcd(a,b)))-((x_b-x_a)^2+(y_b-y_a)^2)(a-\gcd(a,b))-$$ $$-2(x_b-x_a)(\Psi_x(a)-\Psi_x(\gcd(a,b)))-2(y_b-y_a)(\Psi_y(a)-\Psi_y(\gcd(a,b)))$$

Для случая $k\mid b,k\nmid a:$

$$\Delta D_k=\left\lfloor\frac{n^2}k\right\rfloor(x_a^2-x_b^2+y_a^2-y_b^2)-((x_a-x_b)(2X_k+x_a-x_b)+(y_a-y_b)(2Y_k+y_a-y_b))=$$

$$=\left\lfloor\frac{n^2}k\right\rfloor(x_a^2-x_b^2+y_a^2-y_b^2)-((x_a-x_b)^2+(y_a-y_b)^2)-$$ $$-2(x_a-x_b)X_k-2(y_a-y_b)Y_k$$

Поэтому:

$$S_2=(x_a^2-x_b^2+y_a^2-y_b^2)(\Phi(b)-\Phi(\gcd(a,b)))-((x_a-x_b)^2+(y_a-y_b)^2)(b-\gcd(a,b))-$$ $$-2(x_a-x_b)(\Psi_x(b)-\Psi_x(\gcd(a,b)))-2(y_a-y_b)(\Psi_y(b)-\Psi_y(\gcd(a,b)))$$

Сложив $S_1$ и $S_2,$ получим:

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

Где $A,B,C_x,C_y,\Phi(m),\Psi_x(m),\Psi_y(m),X_k,Y_k$ определены выше.

[sevir]

Извиняюсь за то, что нес пургу. Вот что дал расчет в ручном режиме:

$$\tikz[scale=.04]{ \draw(0,0)--(0,20)--(20,20)--(20,0)--(0,0); \draw(0,10)--(20,10); \draw(0,20)--(20,20); \draw(10,0)--(10,20); \draw(20,0)--(20,20); \node at (10,15){\large \textbf{1 2}}; \node at (10,5){\large \textbf{3 4}}; }}$$

$a = 1, b= 2 $: $A = -6$, $B = 1$, $C_x = 0$, $C_y = -4$, $\Delta D= 1$

$$\tikz[scale=.04]{ \draw(0,0)--(0,20)--(20,20)--(20,0)--(0,0); \draw(0,10)--(20,10); \draw(0,20)--(20,20); \draw(10,0)--(10,20); \draw(20,0)--(20,20); \node at (10,15){\large \textbf{3 2}}; \node at (10,5){\large \textbf{1 4}}; }}$$

$a = 3, b= 2 $: $A = 0$, $B = 3$, $C_x = 0$, $C_y = -2$, $\Delta D= 1$

Может служить тестом для проверки.

[dimkadimon]

whitefox, а что будет в случае $k|a, k|b$?

[whitefox]

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

whitefox, а что будет в случае $k|a, k|b$?

В этом случае $a\in M_k$ и $b\in M_k$, а потому $D_k$ не изменяется при обмене $a\leftrightarrow b$, то есть $\Delta D_k=0.$

[dimkadimon]

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

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

Да можно и так. Но как вы правильно заметили обмен происходит редко и поэтому ваш оригинальный О(1) метод для $\Delta D$ быстрее.

[sevir]

А вот что дал расчет в ручном режиме при обмене двойки и четверки.
Это до обмена.

$$\tikz[scale=.04]{ \draw(0,0)--(0,20)--(20,20)--(20,0)--(0,0); \draw(0,10)--(20,10); \draw(0,20)--(20,20); \draw(10,0)--(10,20); \draw(20,0)--(20,20); \node at (10,15){\large \textbf{1 2}}; \node at (10,5){\large \textbf{3 4}}; }}$$

$a = 2, b= 4$: $A = -6$, $B = 2$, $C_x = -4$, $C_y = 0$, $\Delta D= 0$
Т.е. здесь вроде все правильно.

А теперь после обмена:

$$\tikz[scale=.04]{ \draw(0,0)--(0,20)--(20,20)--(20,0)--(0,0); \draw(0,10)--(20,10); \draw(0,20)--(20,20); \draw(10,0)--(10,20); \draw(20,0)--(20,20); \node at (10,15){\large \textbf{1 4}}; \node at (10,5){\large \textbf{3 2}}; }}$$

$a = 4, b= 2 $: $A = 6$, $B = 2$, $C_x = 4$, $C_y = 0$, $\Delta D= -4$

Т.е. как я ранее и писал, $A, C_x$ и $C_y$ меняют знаки без изменения модуля, а B остается неизменным. Следовательно, вопрос упирается в C_x, т.к. A и B так и должны себя вести. Но скорее всего проблема связана с B. Может я при ручном расчете ошибся, но уж очень хитрая ошибка: модуль числа не изменился.

[sevir]

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

А теперь после обмена:

$$\tikz[scale=.04]{ \draw(0,0)--(0,20)--(20,20)--(20,0)--(0,0); \draw(0,10)--(20,10); \draw(0,20)--(20,20); \draw(10,0)--(10,20); \draw(20,0)--(20,20); \node at (10,15){\large \textbf{1 4}}; \node at (10,5){\large \textbf{3 2}}; }}$$

$a = 4, b= 2 $: $A = 6$, $B = 2$, $C_x = 4$, $C_y = 0$, $\Delta D= -4$

Т.е. как я ранее и писал, $A, C_x$ и $C_y$ меняют знаки без изменения модуля, а B остается неизменным. Следовательно, вопрос упирается в C_x, т.к. A и B так и должны себя вести. Но скорее всего проблема связана с B. Может я при ручном расчете ошибся, но уж очень хитрая ошибка: модуль числа не изменился.

Если посчитать по формуле для

$$S_1=\left\lfloor\frac{n^2}k\right\rfloor(x_b^2-x_a^2+y_b^2-y_a^2)-((x_b-x_a)^2+(y_b-y_a)^2)-$$ $$-2(x_b-x_a)X_k-2(y_b-y_a)Y_k,$$

то $\Delta D= 0$.

[sevir]

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

Следовательно, вопрос упирается в C_x, т.к. A и B так и должны себя вести. Но скорее всего проблема связана с B. Может я при ручном расчете ошибся, но уж очень хитрая ошибка: модуль числа не изменился.

Проблема заключалась в неправильном подсчете C_x: был сбит с толку равенством модулей. whitefox'у спасибо за деликатность.

[dmd]

whitefox

Извините за много вопросов, охота разобраться.

1)
$\Phi(a)+\Phi(b)-2\Phi(gcd(a,b))=\Phi(a)-\Phi(b)$
$\Psi_x(a)+\Psi_x(b)-2\Psi_x(gcd(a,b))=\Psi_x(a)-\Psi_x(b)$
$\Psi_y(a)+\Psi_y(b)-2\Psi_y(gcd(a,b))=\Psi_y(a)-\Psi_y(b)$
Это какое-то очевидное свойство? Оно следует из первых формул $\Delta D$ и формул вывода $\Delta D$.

2)
$gcd$ в $\Delta D$ - это нормальный $gcd$ или $gcd$ без единицы?

3)
$\Phi(m)=\sum\limits_{k\mid m}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor$
$\Psi_x(m)=\sum\limits_{k\mid m}\varphi(k)X_k$
$\Psi_y(m)=\sum\limits_{k\mid m}\varphi(k)Y_k$
Суммирование в этих формулах ведётся от $2$ до $n^2/2$?

4)
$k\mid m$ в нижнем пределе суммирования означает, что суммирование ведётся только по $k$ делящим $m$?

5)
если $p$ простое > $n^2/2$, то
$\Phi(1)=\Phi(p)=0$
$\Psi_x(1)=\Psi_x(p)=0$
$\Psi_y(1)=\Psi_y(p)=0$
Это так?

[dimkadimon]

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

Извините за много вопросов, охота разобраться.

dmd, я тоже долго мучился и никак не мог найти $\Delta D$ правильно. В итоге вот что я сделал. Взял оригинальную формулу whitefox для D' и стал ee потихоньку конвертировать в формулу для $\Delta D$, аккуратно проверяя каждый шаг. В итоге формула получилась похожая, но немного другая особенно для B. Для gcd я брал (gcd-1), a для k суммировал от 2 до $N*N/2$ (иначе не получалось). 4) У вас верно, k|m значит m%k=0.

[whitefox]

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

1)
$\Phi(a)+\Phi(b)-2\Phi(gcd(a,b))=\Phi(a)-\Phi(b)$
$\Psi_x(a)+\Psi_x(b)-2\Psi_x(gcd(a,b))=\Psi_x(a)-\Psi_x(b)$
$\Psi_y(a)+\Psi_y(b)-2\Psi_y(gcd(a,b))=\Psi_y(a)-\Psi_y(b)$
Это какое-то очевидное свойство? Оно следует из первых формул $\Delta D$ и формул вывода $\Delta D$.

Вот одно из слагаемых $S_1:\quad(x_b^2-x_a^2+y_b^2-y_a^2)(\Phi(a)-\Phi(\gcd(a,b)))$
А вот соответствующее ему слагаемое из $S_2:\quad(x_a^2-x_b^2+y_a^2-y_b^2)(\Phi(b)-\Phi(\gcd(a,b)))$
Обратите внимание на знаки.
При сложении этих слагаемых получим: $(x_b^2-x_a^2+y_b^2-y_a^2)(\Phi(a)-\Phi(b))$
С другими формулами аналогично.

-- 25 ноя 2014, 09:35 --

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

2)
$gcd$ в $\Delta D$ - это нормальный $gcd$ или $gcd$ без единицы?

Абсолютно нормальный наибольший общий делитель.

-- 25 ноя 2014, 09:46 --

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

3)
$\Phi(m)=\sum\limits_{k\mid m}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor$
$\Psi_x(m)=\sum\limits_{k\mid m}\varphi(k)X_k$
$\Psi_y(m)=\sum\limits_{k\mid m}\varphi(k)Y_k$
Суммирование в этих формулах ведётся от $2$ до $n^2/2$?

Суммирование ведётся по делителям числа $m$, а само $m$ отвечает условию $1\leqslant m\leqslant n^2.$ Именно для того чтобы иметь возможность не ограничиваться для $m$ интервалом $\left[2,\frac{n^2}2\right]$ для $D$ была использована формула

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

Так как $D_1=\frac{n^4(n^2-1)}6$, а для $k>\frac{n^2}2\quad D_k=0$, то

$$D=\sum\limits_{k=1}^{n^2}\varphi(k)D_k$$

-- 25 ноя 2014, 09:47 --

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

4)
$k\mid m$ в нижнем пределе суммирования означает, что суммирование ведётся только по $k$ делящим $m$?

Да.

-- 25 ноя 2014, 10:08 --

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

5)
если $p$ простое > $n^2/2$, то
$\Phi(1)=\Phi(p)=0$
$\Psi_x(1)=\Psi_x(p)=0$
$\Psi_y(1)=\Psi_y(p)=0$
Это так?

$\Phi(1)=\sum\limits_{k|1}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor=\varphi(1)\left\lfloor\frac{n^2}1\right\rfloor=n^2$
Для любого простого $p$, а не только для $p>\frac{n^2}2$ будет:
$\Phi(p)=\sum\limits_{k|p}\varphi(k)\left\lfloor\frac{n^2}k\right\rfloor=\varphi(1)\left\lfloor\frac{n^2}1\right\rfloor+\varphi(p)\left\lfloor\frac{n^2}p\right\rfloor=n^2+(p-1)\left\lfloor\frac{n^2}p\right\rfloor$
Если при этом $n^2>p>\frac{n^2}2$, то $\Phi(p)=n^2+p-1$

Аналогично:
$\Psi_x(1)=X_1,\Psi_x(p)=X_1+(p-1)X_p.$
$\Psi_y(1)=Y_1,\Psi_y(p)=Y_1+(p-1)Y_p.$
Если $n^2>p>\frac{n^2}2,$ то $X_p=x_p,Y_p=y_p$

[whitefox]

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

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

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

[sevir]

Да, математика - это царица наук, а теория чисел - самый драгоценный бриллиант в ее короне: думаю, что подходы, связанные с решением поставленной задачи, не ограничиваются только замечательными формулами whitefox'а.

[dmd]

Спасибо!

Формула для $\Delta D$ заработала, выражение для $B$ - правильное. Все непонятки у меня были в неправильной последовательности суммирований и расстановке пределов суммирований.