2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 27, 28, 29, 30, 31, 32, 33 ... 67  След.
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение12.08.2013, 17:59 
Аватара пользователя


21/02/10
1594
Екатеринбург
dmd в сообщении #754173 писал(а):
уметь генерить исходный нулевой квадрат.

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение12.08.2013, 22:30 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dmd
формулы параллельного переноса на торе никогда не писала. Но сама процедура переноса выполняется очень просто. В моей книге "Волшебный мир магических квадратов" это подробно описано. Да я думаю, вы это знаете. Можно делать перенос по одной оси (по x или по y), а можно комбинированно - по двум осям.
Любой пандиагональный квадрат порядка $n$ имеет ровно $n^2$ эквивалентных квадратов (считая и сам исходный кадрат), полученных параллельным переносом на торе.

Я ищу ассоциативный квадрат Стенли 10-го порядка из различных простых чисел. Это оказалось непросто. Пока есть только первое приближение, константа ассоциативности $K=6006$:

Код:
11  101  497  521  17  1211  707  731  1127  1217
13  103  499  523  19  1213  709  733  1129  1219
77  167  563  587  83  1277  773  797  1193  1283
1013  1103  1499  1523  1019  2213  1709  1733  2129  2219
1577  1667  2063  2087  1583  2777  2273  2297  2693  2783

Много дырок. Собственно, это получено достраиванием известного ассоциативного квадрата Стенли 8-го порядка вручную. Программа только тестировала решение.

Закончила все проверки для ассоциативного квадрата Стенли 8-го порядка; квадрат с индексом меньше 24024 не найден по моей программе.
Осталось закончить все проверки для совершенного магического квадрата 8-го порядка. Тогда уже можно вплотную заняться квадратами 10-го порядка, да ещё и 9-го тоже.

-- Пн авг 12, 2013 23:52:58 --

Пример покажу параллельного переноса на торе пандиагонального магического квадрата, может, пригодится тем, кто ещё не сталкивался с этим преобразованием.

Берём пандиагональный квадрат:

Код:
113 67 443 439 31 149 191
379 101 89 281 43 317 223
211 293 97 163 449 41 179
233 389 131 109 461 73 37
359 241 13 107 173 479 61
47 263 409 311 139 181 83
91 79 251 23 137 193 659

Пусть мы хотим, чтобы в левой верхней ячейке нового квадрата стояло число 13. Сначала выполняем перенос по оси $x$ (можно и по оси $y$ сначала) так, чтобы строка, в которой стоит число 13, оказалась первой сверху:

Код:
359 241 13 107 173 479 61
47 263 409 311 139 181 83
91 79 251 23 137 193 659
113 67 443 439 31 149 191
379 101 89 281 43 317 223
211 293 97 163 449 41 179
233 389 131 109 461 73 37

Теперь выполняем перенос по оси $y$ так, чтобы столбец, в котором стоит число 13, оказался первым слева:

Код:
13 107 173 479 61 359 241
409 311 139 181 83 47 263
251 23 137 193 659 91 79
443 439 31 149 191 113 67
89 281 43 317 223 379 101
97 163 449 41 179 211 293
131 109 461 73 37 233 389

Вот и всё.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.08.2013, 02:23 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #754157 писал(а):
Переносом на торе получаем 49 квадратов. Альфа-преобразованием (Россер) умножаем количество квадратов на 6. Через каждую ячейку будет проходить 48 квадратов. Вполне достаточно.


Кстати базисных квадратов с S=0 гораздо больше. У всех таких квадратов два прямоугольника в виде

1 -1
-1 1

Для маленьких N можно найти все такие квадраты методом полного перебора.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.08.2013, 04:08 


16/08/05
1146
Ловим дырку.
Изображение
Код:
pdms()=
{
n= 7;
m= [113,67,443,439,31,149,191;379,101,89,281,43,317,223;211,293,97,163,449,41,179;233,389,131,109,461,73,37;359,241,13,107,173,479,61;47,263,409,311,139,181,83;91,79,251,23,137,193,659];
k= [0, 0, 0, 0, 0, 0, 0; 0, 0, 0, 0, 0, 0, 0; 0, 0, 0, 0, 0, 0, 0;-1, 1, 0, 0, 0, 0, 0; 0, 0,-1, 0, 0, 0, 1; 0, 0, 1, 0, 0, 0,-1; 1,-1, 0, 0, 0, 0, 0];

forstep(l=-1, 1, 2,
forstep(d=2, 1000, 2,
  M= m+l*d*k; q= 0;
  for(i=1, n,
   for(j=1, n,
    a= M[i,j];
    if(a<3, break(3));
    if(!isprime(a), q++);
   )
  );
  if(q<2, print(q,"    ",l,"    ",d); print(M))
)
)
};

Попалась двойняшка.
Код:
0    -1    30
[113, 67, 443, 439, 31, 149, 191; 379, 101, 89, 281, 43, 317, 223; 211, 293, 97, 163, 449, 41, 179; 263, 359, 131, 109, 461, 73, 37; 359, 241, 43, 107, 173, 479, 31; 47, 263, 379, 311, 139, 181, 113; 61, 109, 251, 23, 137, 193, 659]

Изображение

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.08.2013, 04:11 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dmd
красиво, мне понравилось :roll:
Теперь избавляемся от двойняшек...

-- Вт авг 13, 2013 05:25:48 --

Что-то красивое и у dimkadimon получилось :wink:

Цитата:
2 7.46 Dmitry Kamenetsky Adelaide, Australia 13 Aug 2013 01:10

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.08.2013, 05:15 


18/11/10
75
dimkadimon в сообщении #754337 писал(а):
Кстати базисных квадратов с S=0 гораздо больше. У всех таких квадратов два прямоугольника в виде

1 -1
-1 1

Now you know my secret algorithm :D

At this point everything comes down to technical details of the implementation.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.08.2013, 05:52 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ну, вот и раскололи орешек общими усилиями :D
Жалко, что слишком поздно, на реализацию осталась всего неделя.
Хотя... задачу ведь можно и после конкурса решать, если кому понравилось :wink:
Я, к примеру, квадраты очень редко "бросаю", ну если конкурс отвлечёт иногда.
Сейчас у меня, правда, антимагические квадраты Стенли, но они очень сильно связаны с магическими квадратами, в чём все, наверное, убедились.

-- Вт авг 13, 2013 07:02:50 --

И опять у Pavlovsky оттяпали сотки и стало меньше 6 баллов :D

Цитата:
6 5.99 Valery Pavlovsky Ekaterinburg, Russia 12 Aug 2013 00:39

Что творится-то... трудно даже на уровне 6 баллов удержаться.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.08.2013, 06:19 
Аватара пользователя


21/02/10
1594
Екатеринбург
dmd в сообщении #754344 писал(а):
Ловим дырку.

Двойняшек лучше не допускать изночально. С ними трудно бороться.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.08.2013, 06:23 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Разве труднее, чем с дыркой? Повтор элемента - та же дырка, то есть не разрешённое правилами число.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.08.2013, 06:55 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #754350 писал(а):
трудно даже на уровне 6 баллов удержаться.


Набросал алгоритм блуждающей дырки. Первые вычисилительные эксперименты показали работоспособность алгоритма. Так что в зону 6.00 балла вернусь.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.08.2013, 06:58 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Jarek в сообщении #754348 писал(а):
Now you know my secret algorithm :D

At this point everything comes down to technical details of the implementation.


I find this hard to believe. My results are still quite far from yours even for small N, so you must be doing something extra. Anyway, do not reveal anything at this stage. I am really looking forward to your final report.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.08.2013, 07:44 


18/11/10
75
dimkadimon в сообщении #754358 писал(а):
I find this hard to believe. My results are still quite far from yours even for small N, so you must be doing something extra. Anyway, do not reveal anything at this stage. I am really looking forward to your final report.

This algorithm is surprisingly sensitive on the way you actually conduct the search. A small change of settings quite often produces a significant improvement of the results. Quite often an experiment is the only way to work it out. My current findings would be completely unbelievable to me, when I was starting using the algorithm, but step by step I managed to improve its performance. The extra I have, is something like month and a half of time, when I was able to load the basic version of the algorithm with many little tricks and tune it up.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.08.2013, 21:14 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Поработала над ассоциативным квадратом Стенли 9-го порядка. Сначала хотела описывать (составлять систему уравнений) и уже начала, но потом решила попробовать сделать общую формулу по аналогии с ассоциативным квадратом Стенли 10-го порядка.
В который раз убеждаюсь: аналогия - великая вещь!

Конфигурация ассоциативного квадрата Стенли 9-го порядка:

Код:
x1 x2 x3 x4 x5 x6 x7 x8 x9
x10 x11 x12 x13 x14 x15 x16 x17 x18
x19 x20 x21 x22 x23 x24 x25 x26 x27
x28 x29 x30 x31 x32 x33 x34 x35 x36
x37 x38 x39 x40 x41 k-x40 k-x39 k-x38 k-x37
k-x36 k-x35 k-x34 k-x33 k-x32 k-x31 k-x30 k-x29 k-x28
k-x27 k-x26 k-x25 k-x24 k-x23 k-x22 k-x21 k-x20 k-x19
k-x18 k-x17 k-x16 k-x15 k-x14 k-x13 k-x12 k-x11 k-x10
k-x9 k-x8 k-x7 k-x6 k-x5 k-x4 k-x3 k-x2 k-x1

k - константа ассоциативности. Для квадрата 9-го порядка имеем:

$S=9k/2$, $x_{41}=k/2$

Общая формула ассоциативного квадрата Стенли 9-го порядка

(Оффтоп)

Код:
x37=x1+x41-x5
x38=x2+x37-x1
x39=x3+x37-x1
x40=x4+x37-x1
x6=2 x5-x4
x7=2 x5-x3
x8=2 x5-x2
x9=2 x5-x1
x11=x2+x10-x1
x12=x3+x10-x1
x13=x4+x10-x1
x14=x5+x10-x1
x15=x6+x10-x1
x16=x7+x10-x1
x17=x8+x10-x1
x18=x9+x10-x1
x20=x2+x19-x1
x21=x3+x19-x1
x22=x4+x19-x1
x23=x5+x19-x1
x24=x6+x19-x1
x25=x7+x19-x1
x26=x8+x19-x1
x27=x9+x19-x1
x29=x2+x28-x1
x30=x3+x28-x1
x31=x4+x28-x1
x32=x5+x28-x1
x33=x6+x28-x1
x34=x7+x28-x1
x35=x8+x28-x1
x36=x9+x28-x1

Получилось всего 8 свободных переменных. Формулу проверила на обратимом квадрате 9-го порядка и на квадрате из произвольных натуральных чисел, полученном достраиванием ассоциативного квадрата Стенли 7-го порядка.
Написала программу, программа работает быстро.
Запустила, нашла одно решение, но... не сделала в программе вторую половинку, которая вычисляется по ассоциативности, и проверки элементов этой половинки, разумеется, нет. И получила решение весьма интересное: вторая половинка полностью повторяет первую:

Код:
5059 5413 11719 14293 14341 14389 16963 23269 23623
7369 7723 14029 16603 16651 16699 19273 25579 25933
12829 13183 19489 22063 22111 22159 24733 31039 31393
15139 15493 21799 24373 24421 24469 27043 33349 33703
10099 10453 16759 19333 19381 19429 22003 28309 28663
5059 5413 11719 14293 14341 14389 16963 23269 23623
7369 7723 14029 16603 16651 16699 19273 25579 25933
12829 13183 19489 22063 22111 21959 24733 31039 31393
15139 15493 21799 24373 24421 24269 27043 33349 33703

Не дырка, а целая дырища :D вся вторая половинка - сплошная дыра, повторяющиеся числа. Надо теперь подкорректировать программу, чтобы вторая половинка тоже проверялась на уникальность.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение14.08.2013, 05:36 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Цитата:
2 8.15 Dmitry Kamenetsky Adelaide, Australia 14 Aug 2013 02:28
3 7.13 Wes Sampson La Jolla, California, United States 13 Jul 2013 01:27
4 6.31 Tristrom Cooke Adelaide, Australia 12 Aug 2013 22:48
5 6.18 Dmitry Ezhov Sterlitamak, Russia 13 Aug 2013 23:57


О-о-о! dimkadimon сделал 8+ :D
dmd тоже с новым решением.

Рада за обоих Дмитриев. Так держать! :wink:

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение14.08.2013, 10:37 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Ура. Я наконец нашёл решения для N=17 и 19. Ну хотя бы до 10 баллов добраться...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 27, 28, 29, 30, 31, 32, 33 ... 67  След.

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



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

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


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

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