Магические квадраты

[Nataly-Mak]

Эка вы раздухарились

[svb]

Garik2 в сообщении #347396 писал(а):

чтобы я нажал пуск и все пошло автоматически? Не хочу я копаться в данных и что-то отлаживать.

Выкладываю программу Наталии с новым ограничением и откомпилированную новым компилятором, теперь она работает быстрее раз в 20:
http://narod.ru/disk/24322403000/PAN6W4.rar.html
А чтобы не было скучно выводятся $A4$ и $A5$

[Garik2]

Да, но нужно по проге указать магическую сумму. Какую же?

[svb]

Garik2 в сообщении #348723 писал(а):

Да, но нужно по проге указать магическую сумму. Какую же?

Нет, ничего не нужно - там все внутри программы. Распаковать и запустить, если квадрат будет найден, то сумма у него будет $<8340$, т.е. самой маленькой на данный момент. Но Вы в общем-то уже запускали ее раньше, только с другим ограничением.

[Nataly-Mak]

Вчера искала в сети нетрадиционные пандиагональные квадраты. Нашла:
http://www.iatp.am/slkuni/gre-la.htm

Приведены два пандиагональных квадрата 6-го порядка:

1 43 19 13 41 33     
34 12 48 15 5 36     
3 21 44 10 30 42     
37 9 17 49 7 31     
35 45 14 16 38 2     
40 20 8 47 29 6  

28 1 26 36 8 21
3 35 7 27 23 25
34 24 22 2 29 9
4 32 19 12 39 14
13 17 15 37 5 33
38 11 31 6 16 18

Интересно, что оба квадрата составлены из 18 комплементарных пар. Если применить к этим квадратам преобразование обратное преобразованию 3-х квадратов, получаются квадраты ассоциативные, но не пандиагональные. Например, из первого квадрата получаем такой ассоциативный квадрат:

1 43 19 33 41 13
34 12 48 36 5 15
3 21 44 42 30 10
40 20 8 6 29 47
35 45 14 2 38 16
37 9 17 31 7 49

Константа ассоциативности и магическая константа этого квадрата такие же, как у квадрата Журбы, однако этот квадрат не является идеальным.
Квадрат подобен квадрату, полученному svb (из 18 комплементарных пар).

Как я поняла, в следующем алгоритме svb используются три группы чисел, одна группа – это по-прежнему комплементарные числа, а две другие группы – это “псевдокомплементарные” числа. То есть (если я правильно понимаю) в этих группах тоже находятся комплементарные числа, только сумма двух взаимно-дополнительных чисел не такая, как для комплементарных пар чисел в первой группе. В одной группе эта сумма меньше, а в другой больше на ту же самую величину; суммы комплементарных пар всех трёх групп связаны соотношением: S_a + S_b = 2S_c.

Такая идея: нельзя ли пойти дальше по этому пути и использовать 9 групп комплементарных чисел?

Интересно исследовать известный пандиагональный квадрат 6-го порядка из последовательных чисел с магической константой 930: есть ли в нём хоть какие-то комплементарные пары? Предполагаю, что нет.
Ещё надо посмотреть, какой ему соответствует шаблон. Поскольку в нём не используется простое число 3, то этот шаблон должен состоять из вычетов 1 и 5 (по модулю 6). Все шаблоны для пандиагональных квадратов 6-го порядка из простых чисел у нас найдены (приведены выше).

Меня по-прежнему интересует вопрос: как составлен этот квадрат, по какому алгоритму.
Ну, составить обычный МК 6-го порядка из данного набора последовательных простых чисел просто. Но вот пандиагональный… По программе, основанной на общей формуле, можно его составить (maxal это подтвердил), но уж очень долго работает эта программа. Нет ли более эффективного алгоритма построения такого квадрата?

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

_________

Нашла ещё три примитивных квадрата 5х5 из различных чисел с константой 1579. Если кто заинтересуется этой задачей, могу выложить эти три квадрата.
Ещё раз постановка задачи:
требуется построить 4 примитивных квадрата 5х5 из простых чисел с одинаковой константой так, чтобы все 4 квадрата были составлены из различных чисел. Это нужно для составления наименьшего пандиагонального квадрат 10-го порядка из простых чисел (по решётке Россера).
На сегодня Павловским найден пандиагональный квадрат 10-го порядка из прсотых чисел с магической константой 3594. Этот квдарат составлен из 4 пандиагональных квадратов 5х5 с магической константой 3594/2=1797.
Пандиагональный квадрат 5-го порядка получается из примитивного квадрата с помощью известного преобразования. Так что достаточно найти 4 примитивных квадрата 5х5.

[Nataly-Mak]

Шаблон известному пандиагональному квдарату из последовательных простых чисел соответствует такой:

1 1 5 5 1 5
1 5 5 1 1 5
1 1 5 5 1 5
1 5 5 1 1 5
1 1 5 5 1 5
1 5 5 1 1 5

А вот комлементарные пары чисел в этом квадрате есть, например, такая группа пар с суммой 318:

67 251, 79 239, 89 229, 107 211, 127 191, 137 181, 139 179, 151 167

Может быть, это не случйно, и алгоритм построения этого квадрата тоже как-то связан с комплементарными парами чисел?

-- Чт сен 02, 2010 10:08:31 --

Интересно!
Запускаю программу svb (реализация последнего алгоритма для трёх групп комплементарных пар чисел), ввожу в программу значение S_c = 310, (S_c = S/3). Программа не долго думая начинает выводить пандиагональные квадраты из простых чисел с магической константой S = 930:

  13  67 211 307  19 313
 269 263 113  17 239  29
 223  79 157 181 151 139
  43 251  37 257 283  59
 293  71 281  41  47 197
  89 199 131 127 191 193
S=930
  19  67 211 313  13 307
 269 263 113  17 239  29
 223  79 151 181 157 139
  37 257  43 251 283  59
 293  71 281  41  47 197
  89 193 131 127 191 199
S=930
  13 223 211 151  19 313
 269 263 113  17 239  29
  67  79 157 181 307 139
 199 251  37 257 127  59
 293  71 281  41  47 197
  89  43 131 283 191 193 

. . . . . .

Программу прервала. Любопытно, найдёт ли программа известный пандиагональный квадрат из последовательных простых чисел? Думаю, должна

[svb]

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

Такая идея: нельзя ли пойти дальше по этому пути и использовать 9 групп комплементарных чисел?

Рассмотрим общий случай:

  p1  p2  p3 -p1 -p2 -p3      
  p4  p5  p6 -p4 -p5 -p6      
  p7  p8  p9 -p7 -p8 -p9      
 -p1'-p2'-p3' p1' p2' p3'     
 -p4'-p5'-p6  p4' p5' p6'     
 -p7'-p8'-p9' p7' p8' p9'     

где в обозначениях элементов показаны группы "псевдокомлементарности". Эти группы всегда "ходят парами", т.е., если имеется группа с отклонением от комплементарности равным $p$, то обязательно имеется группа с отклонением $-p$. Это следует из свойств решеток $L(2)$ по Россеру. Не все $pi$ оказываются независимыми, на самом деле они зависят от 4-х параметров:
$p1=-y-t$, $p2=x$, $p3=-y-u$
$p4=u$, $p5=x+y+u+t$, $p6=t$
$p7=-x-t$, $p8=y$, $p9=-x-u$
Вот, пожалуй, и все о "псевдокомплементарных" группах. Для любой выбранной конфигурации затем можно осуществлять перебор элементов, которые берутся из соответствующих групп. Этих элементов 18, но с 6 ограничениями магичности, т.е. всего 12 независимых элементов.

p.s. Подчеркну, что в таблице стоят обозначения групп, а не конкретные элементы. Далее, любой пандиагональный квадрат обязательно принадлежит одной из описанных конфигураций.

[Nataly-Mak]

Наконец-то я вникла в алгоритм svb с тремя группами комплементарных пар чисел окончательно.
Покрутила сейчас его программу для простых чисел и вот:

17  53  47 173  23 197
 109 103  97  43 151   7
 179  29 131  89  11  71
  37 107  13 113 157  83
 127  19 163  61  67  73
  41 199  59  31 101  79
S=510
  23 173  47  53  17 197
 151 103  97  43 109   7
  11  29 131  89 179  71
 157 113  13 107  37  83
 127  61 163  19  67  73
  41  31  59 199 101  79
S=510
  23 173  47  53  17 197
 151  43  97 103 109   7
  11  89 131  29 179  71
 157 113  13 107  37  83
  67  61 163  19 127  73
 101  31  59 199  41  79
S=510
. . . . . . . . . . .

Это у нас вроде минимальный? Остались под вопросом две потенциальные константы: 486 и 498. Осилим?

[Nataly-Mak]

Покрутила программу svb для магической константы 498, ничего не нашлось
Наверное, зря для этой константы крутила, потому что S_c = 166 имеет только 5 комплементарных пар чисел (так говорит программа), а их должно быть как минимум 6.

Сейчас ещё для константы 486 покручу.

maxal
вы проверили несколько потенциальных магических констант (438, 450, 462, 474). Не могли бы вы ещё оставшиеся две константы проверить?

-- Чт сен 02, 2010 16:07:04 --

Прокрутила для константы 486, тоже ничего не нашлось.
Итак, вопрос для констант 486 и 498 остаётся открытым.

[Nataly-Mak]

svb
вы привели схему, в которую наконец-то отлично вписывается известный пандиагональный квадрат 6-го порядка из последовательных простых чисел, вот этот:

67 193 71 251 109 239
139 233 113 181 157 107
241 97 191 89 163 149
73 167 131 229 151 179
199 103 227 101 127 173
211 137 197 79 223 83

Очень долго я не могла понять, как же построен этот квадрат.
По вашей схеме всё получается чётко:

группа p1: 67, 229 (отклонение -14)
группа –p1: 251, 73 (отклонение +14)
группа p2: 193, 151 (отклонение +34)
группа –p2: 109, 167 (отклонение -34)
и так далее.

Проверила все 9 групп (я считаю две группы с одинаковым отклонением в плюс и в минус за одну группу, например: p1 и -p1; если считать все группы, то их будет 18).

Осталось реализовать этот алгоритм. Как вы пишете, в этом алгоритме всего 12 независимых элементов. Этот момент не совсем уловила. В трёх строках у нас 18 элементов. С условием магичности этих строк остаётся 15 элементов. Как вы исключили ещё 3 элемента? Кроме того, не поняла, как вы вывели зависимость между группами (от 4 параметров).
Одним словом, пока у меня реализация этого алгоритма прозрачно не просматривается. Но, может быть, вы сами его реализуете? Алгоритм очень красивый и обещает дать хорошие результаты.

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

[svb]

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

Как вы пишете, в этом алгоритме всего 12 независимых элементов. Этот момент не совсем уловила. В трёх строках у нас 18 элементов. С условием магичности этих строк остаётся 15 элементов. Как вы исключили ещё 3 элемента?

А столбцы? Пример
$S=(p1)+(p4)+(p7)+(-p1')+(-p4')+(-p7')=(p1)+(p4)+(p7)+(Sc-p1-(-p1))+(Sc-p4-(-p4)+(Sc-p7-(-p7))=3Sc-p1-p4-p7+(p1)+(p4)+(p7)+(p7)-(-p1)-(-p4)-(-p7)$
$Sc$ - сумма обыкновенной комплементарной пары = $S/3$

Извините эа не очень удачные обозначения - $(p1)$ это выборка элемента из группы $p1$. Соотношения между $pi$ получены аналогично, но уже забыл как

p.s. Рассматривая суммы по различным диагоналям.

[Nataly-Mak]

Пока у меня туман
Но вот смотрю и смотрю на вашу схему.
1. Если все 16 свободных переменных (которые мы имеем в общей формуле) распределить на 4 группы (по решётке), то в каждой группе из 4 элементов независимых элементов останется 3; так и получается как раз 12 независимых переменных. Тут вроде всё правильно.
2. Ещё интереснее следующее:
мы строим пандиагональный квадрат по решётке Россера из квадратов 2х2, но, конечно, не пандиагональных, а таких, что сумма чисел в этих квадратах равна 2S_c = 2S/3, S - магическая константа квадрата, S_c - константа комплементарности (в ваших обозначениях).
Вот примеры таких квадратов 2х2 из приведённого выше пандиагонального квадрата:

67 251
73 229

193 109
167 151

Вот если мы наберём из заданного массива чисел 9 таких квадратов 2х2 (все из различных чисел), то пандиагональный квадрат возможно и составится из таких квадратов.
Однако, это необходимое условие, но вряд ли достаточное.
Но уже немножко ясно, что надо искать

[svb]

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

Однако, это необходимое условие, но вряд ли достаточное.

Если будут выполнены условия для $pi$, то этого будет достаточно.
Можно их выписать в следующем виде:
$p1+p5+p9=0$
$p3+p5+p7=0$
$p1-p6-p8=0$
$p9-p2-p4=0$
$p3-p4-p8=0$
$p7-p2-p6=0$
- одно из них лишнее, т.к. они зависимые.

-- Чт сен 02, 2010 19:52:15 --

Возможно, что отталкиваясь от квадратов $2x2$ можно будет построить более эффективный алгоритм.

[Nataly-Mak]

Ага, сообразила, что выписанные вами условия - это условия для отклонений от константы комплементарности в 9 группах p_i.

Программу поиска 9 квадратов 2х2 написала, квадраты находятся довольно быстро. Осталось ввести условия, которым должны удовлетворять эти квадраты, то есть как раз условия для отклонений. Ну, вот сейчас условия введу и программа уже задумается (предвижу!)

Вы пишете программу реализации этого алгоритма? Пишите! Нельзя оставить такой замечательный алгоритм не реализованным.

[svb]

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

Программу поиска 9 квадратов 2х2 написала, квадраты находятся довольно быстро.

Ужасает большое количество подобных наборов.