2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 7, 8, 9, 10, 11, 12, 13 ... 25  След.
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение24.11.2014, 17:12 


22/11/14

43
whitefox в сообщении #935533 писал(а):
Пример приведите, пожалуйста.

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

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


19/12/10
1546
Коль возникают сомнения в правильности формулы для $\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$ определены выше.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение24.11.2014, 19:00 


22/11/14

43
Извиняюсь за то, что нес пургу. Вот что дал расчет в ручном режиме:
$$\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$

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

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


01/06/12
1016
Adelaide, Australia
whitefox, а что будет в случае $k|a, k|b$?

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


19/12/10
1546
dimkadimon в сообщении #935665 писал(а):
whitefox, а что будет в случае $k|a, k|b$?

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

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


01/06/12
1016
Adelaide, Australia
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$ быстрее.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение24.11.2014, 23:20 


22/11/14

43
А вот что дал расчет в ручном режиме при обмене двойки и четверки.
Это до обмена.
$$\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. Может я при ручном расчете ошибся, но уж очень хитрая ошибка: модуль числа не изменился.

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение25.11.2014, 00:48 


22/11/14

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

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение25.11.2014, 03:44 


22/11/14

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

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

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение25.11.2014, 06:58 


16/08/05
1146
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$
Это так?

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


01/06/12
1016
Adelaide, Australia
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.

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


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

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


19/12/10
1546
dimkadimon в сообщении #935812 писал(а):
В итоге формула получилась похожая, но немного другая особенно для B

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

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение25.11.2014, 13:37 


22/11/14

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

 Профиль  
                  
 
 Re: Al Zimmerman - Delacorte Numbers
Сообщение25.11.2014, 14:16 


16/08/05
1146
Спасибо!

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 373 ]  На страницу Пред.  1 ... 7, 8, 9, 10, 11, 12, 13 ... 25  След.

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



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

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


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

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