Дьявольские магические квадраты из простых чисел

[Pavlovsky]

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

уметь генерить исходный нулевой квадрат.

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

[Nataly-Mak]

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

Вот и всё.

[dimkadimon]

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

Переносом на торе получаем 49 квадратов. Альфа-преобразованием (Россер) умножаем количество квадратов на 6. Через каждую ячейку будет проходить 48 квадратов. Вполне достаточно.

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

1 -1
-1 1

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

[dmd]

Ловим дырку.

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]

[Nataly-Mak]

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

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

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

Цитата:

2 7.46 Dmitry Kamenetsky Adelaide, Australia 13 Aug 2013 01:10

[Jarek]

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

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

1 -1
-1 1

Now you know my secret algorithm

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

[Nataly-Mak]

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

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

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

Цитата:

6 5.99 Valery Pavlovsky Ekaterinburg, Russia 12 Aug 2013 00:39

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

[Pavlovsky]

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

Ловим дырку.

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

[Nataly-Mak]

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

[Pavlovsky]

Nataly-Mak в сообщении #754350 писал(а):

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

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

[dimkadimon]

Jarek в сообщении #754348 писал(а):

Now you know my secret algorithm

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.

[Jarek]

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.

[Nataly-Mak]

Поработала над ассоциативным квадратом Стенли 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

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

[Nataly-Mak]

Цитата:

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+
dmd тоже с новым решением.

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

[dimkadimon]

Ура. Я наконец нашёл решения для N=17 и 19. Ну хотя бы до 10 баллов добраться...