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

[Nataly-Mak]

Если кому наскучило искать оптимальное решение для N=7, переходите, пожалуйста, к поиску оптимального решения для N=8
Это чётный порядок, может быть, тут всё проще окажется.

Начну с наименьшего обычного магического квадрата 8-го порядка из различных простых чисел:

3 19 59 61 233 239 257 283
193 271 157 139 199 41 53 101
241 311 263 167 11 43 29 89
5 17 37 79 173 269 281 293
331 109 227 137 127 73 67 83
7 23 31 197 149 251 317 179
163 223 229 277 71 131 47 13
211 181 151 97 191 107 103 113
S=1154

Построения этого квадрата описано в статье.
Ранжированный массив простых чисел, из которых составлен этот квадрат:

3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199  211  223  227  229  233  239  241  251  257  263  269  271  277  281  283  293  311  317  331

Цитата:

Другой массив простых чисел для квадрата 8-го порядка у меня тоже с ходу не сформировался. Возможно, есть варианты, но сразу их не видно.

(из указанной статьи)
Как утверждает программа whitefox, массив для данной магической константы всего один. Значит, недаром у меня второй массив не сформировался. Будем считать, что два человека независимо друг от друга установили, что такой массив один. Это уже хорошо, проверять надо всего один массив.

Теперь покажу своё лучшее решение - пандиагональный квадрат с магической константой 1584:

5 13 463 293 443 283 53 31
313 379 71 73 89 79 191 389
23 211 167 331 199 353 149 151
449 239 41 97 59 127 349 223
19 47 439 269 457 317 29 7
241 383 109 103 17 83 229 419
101 139 181 311 277 281 163 131
433 173 113 107 43 61 421 233
S=1584

И наконец, лучшее решение Jarek:

5,37,107,157,229,311,271,131, 
73,239,397,173,197,13,113,43, 
293,313,11,97,181,149,103,101, 
223,83,151,71,53,241,233,193, 
167,127,179,31,277,317,61,89, 
67,59,139,281,269,109,17,307, 
137,349,257,211,19,29,199,47, 
283,41,7,227,23,79,251,337
S=1248

Всё готово, можно начинать поиск оптимального решения
Понятно, что потенциальные магические константы для квадратов 8-го порядка, составленных из различных простых чисел, будут чётные.
Я начала бы сразу с проверки магической константы 1154. Как уже отмечено, проверить надо всего один массив. В статье Россера много чего написано о пандиагональных квадратах 8-го порядка, надо всё это внимательно изучить.
Можно поколдовать с вычетами по модулю 6 или по другим модулям. Можно ещё что-нибудь придумать оригинальное

[whitefox]

Условие аксиомы П3 является необходимым для того, чтобы из четырёх попарно ортогональных точных покрытий составился пандиагональный магический квадрат. Но, видимо, не достаточным.

[Pavlovsky]

Вроде созрел для реализации алгоритмов. Начну с поиска для нечетных N. Хотя есть идеи и по четным N.

Одна из идей наглядно видна на примере этого магического квадрата:

5 13 463 293 443 283 53 31
313 379 71 73 89 79 191 389
23 211 167 331 199 353 149 151
449 239 41 97 59 127 349 223
19 47 439 269 457 317 29 7
241 383 109 103 17 83 229 419
101 139 181 311 277 281 163 131
433 173 113 107 43 61 421 233

19-5=457-443=14

[dimkadimon]

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

19-5=457-443=14

А что дальше? Вроде эти числа нельзя поменять местами потому что нарушаться некоторые диагонали...

[Nataly-Mak]

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

Одна из идей наглядно видна на примере этого магического квадрата:

19-5=457-443=14

Pavlovsky
этот квадрат, между прочим, построен по алгоритму, использующему псевдокомплементарные числа (автор алгоритма для n=6 svb).
Идея, конечно, видна

У меня уже бродит в голове мысль попробовать этот алгоритм для магической константы 1154. Совсем не исключено, что он сработает.
Только вот программу придётся заново писать, старая пропала.

P.S. Ссылку на статью, где описан данный алгоритм, и подробные пояснения для dmd я приводила в этой теме.

[Pavlovsky]

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

Вроде эти числа нельзя поменять местами потому что нарушаться некоторые диагонали

Если одновременно поменять местами 19 и 5; 457 и 443, тогда сумма диагоналей и колонок не изменится. Изменится сумма в первой и пятой строках. Сумма первой строки увеличится на 28, сумма пятой строки уменьшится на 28.

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

этот квадрат, между прочим, построен по алгоритму, использующему псевдокомплементарные числа (автор алгоритма для n=6 svb).

Ну вот опять SVB у меня идею украл.

[Nataly-Mak]

А я ищу решение $S=741$ по программе whitefox.



Почти 10 часов работает программа, проверено около 17 млн. полумагических квадратов, около 5 млн. магических квадратов.
Д-а-а-а, пандиагональные квадраты из различных простых чисел - редкие жемчужины среди полумагических и магических квадратов

[Nataly-Mak]

По Россеру для пандиагональных квадратов 8-го порядка (и вообще любого чётного порядка) есть такое необходимое условие: массив, состоящий из 64 чисел, должен иметь хотя бы одно разбиение на 4 (непересекающиеся) группы чисел с суммой равной 2S (S - магическая константа квадрата).

В решении Jarek $S=1248$ это выглядит так:



Эти 4 группы чисел располагаются по решёткам. Можно назвать это условие правилом решёток.
На иллюстрации вы видите 4 группы чисел, расположенных в решётках (числа одной группы окрашены в одинаковый цвет). Сумма чисел в каждой решётке равна 2496.

Теперь надо проверить, имеет ли хотя бы одно такое разбиение массив чисел, дающих магическую константу 1154. Если не имеет, то построить пандиагональный квадрат 8-го порядка из чисел данного массива невозможно.

Эх, если бы такое разбиение было одно Тогда бы можно было быстренько сделать перебор по решёткам для этого разбиения. Боюсь, что таких разбиений будет море.
А может, и не одного нет Надо проверить.

[Nataly-Mak]

Сегодня решила поискать по своей программе решение $S=733$ из чисел Массива №1. Долго программа работала, наконец, нашла решение с 6 дырками:



Элементов больше 239 нет, с этим всё в порядке, однако отрицательное число присутствует. В общем, плохое приближение к решению, но оно у меня пока единственное.

[Nataly-Mak]

Есть преобразование пандиагональных квадратов нечётных порядков "строки-диагонали".

Решила попробовать поменять соответствующим образом 4 приведённых выше точных попарно ортогональных покрытия и построить из них пандиагональный квадрат.
Теперь покрытие для строк покрывает прямые диагонали, покрытие для столбцов покрывает обратные диагонали и наоборот. То есть строки и столбцы меняются местами с диагоналями (строки с прямыми диагоналями, столбцы - с обратными).

Пандиагональный квадрат получился такой:

3 181 251 163 67 83 7
149 103 109 5 131 179 79
223 29 197 13 113 73 107
151 59 23 157 173 139 53
61 137 31 311 43 71 101
127 227 97 89 37 11 167
41 19 47 17 191 199 241

Сравните с решением Jarek (из которого были сделаны покрытия):

3 43 103 11 197 241 157
173 181 71 109 167 13 41
19 139 251 101 5 127 113
73 47 53 163 61 131 227
97 107 17 151 67 137 179
79 89 223 191 59 83 31
311 149 37 29 199 23 7

Главная прямая диагональ (3 181 251 163 67 83 7) превратилась в новом квадрате в строку.
Все разломанные прямые диагонали тоже превратились в строки. А все обратные диагонали превратились в столбцы. Изоморфный квадрат, если считать данное преобразование изоморфизмом (у Россера в Теореме 3.3 преобразование Q, как мне подсказал Pavlovsky).
Всё чётко и... дьявольски красиво

-- Ср сен 04, 2013 22:55:09 --

Программа mertz выдала решение $S=733$ с 3 дырками, 3 двойняшки



Посмотрите, сколько элементов больше 239 (я вижу три таких элемента: 271, 283 и 313), это фактически тоже дырки, ибо запрещённые для решений с магической константой 733 числа.

Решений с двумя дырками у меня не появилось ни разу.
Программа whitefox решения с дырками не выводит Вот кручу целый день (больше 14 часов) программу поиска решения 741, сколько там дырок было...одному Богу известно. И нормального решения (без дырок) тоже нет. Ужас! Проверено более 25 млн. полумагических квадратов!

-- Ср сен 04, 2013 23:10:52 --

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

Вот мои результаты. Искал 749 6 дней и так не нашёл, зато нашёл 1138 решений с одной ошибкой. Теперь начал искать 743, пока нашёл 58 решений с одной ошибкой.

dimkadimon
огромная просьба к вам: если не трудно, проверьте, пожалуйста, нет ли у вас решений, в которых одной дыркой является число 1.
Как я уже писала выше, такие решения нужны для головоломки на сайте primepuzzles.net (составление пандиагональных квадратов из различных простых чисел плюс число 1).

-- Ср сен 04, 2013 23:19:04 --

Для n=4-6 я нашла наименьшие квадраты в этой головоломке, а для n=7 вот такое решение:

1 229 79 419 179 443 227
167 521 191 97 211 31 359
307 13 311 107 509 269 61
449 257 139 271 109 293 59
73 389 41 401 197 127 349
149 67 337 151 353 137 383
431 101 479 131 19 277 139
S=1577

Это регулярный пандиагональный квадрат. Решение, конечно, не наименьшее, наверняка существует нерегулярное решение с меньшей магической константой.
Ссылка на головоломку.

[Nataly-Mak]

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

По Россеру для пандиагональных квадратов 8-го порядка (и вообще любого чётного порядка) есть такое необходимое условие: массив, состоящий из 64 чисел, должен иметь хотя бы одно разбиение на 4 (непересекающиеся) группы чисел с суммой равной 2S (S - магическая константа квадрата).

Теперь надо проверить, имеет ли хотя бы одно такое разбиение массив чисел, дающих магическую константу 1154. Если не имеет, то построить пандиагональный квадрат 8-го порядка из чисел данного массива невозможно.

Написала программку на скорую руку, запустила; первый набор из 16 чисел с суммой 2308 программа нашла быстро:

3  5  7  11  13  17  19  23  127  271  277  283  293  311  317  331

Выбросила из массива эти 16 чисел и снова запустила программу в надежде найти второй набор. Программа уже 2 часа работает и не выдаёт второй набор

Конечно, первый набор может быть не только такой, их может быть много. И для каждого первого набора надо искать второй набор. Но что-то сильно мне подозрительно, что даже второй набор с ходу не находится. Если исключить ошибку в программе, это очень плохой признак. А может, наоборот - хороший Если массив не разбивается на 4 группы чисел с суммой 2308, сразу его отбрасываем, а вместе с ним и константу 1154.

Ох, вижу один баг в программе
Сейчас исправлю, может, что-нибудь и найду.
Вот так на скорую руку писать программы

-- Чт сен 05, 2013 08:41:11 --

Исправила ошибку.
Второй набор из 16 чисел с суммой 2308 нашёлся мгновенно:

29  31  37  41  43  47  53  59  167  239  241  251  257  263  269  281

Сейчас выброшу эти числа из массива и попробую найти третий набор.

-- Чт сен 05, 2013 08:51:14 --

Третий набор тоже нашёлся мгновенно:

61  67  71  73  79  83  89  97  173  193  199  211  223  227  229  233

Ну, а четвёртый набор получается автоматически из оставшихся 16 чисел.
Необходимое условие выполнено, одно разбиение найдено.

Внимание, вопрос!
Сколько всего будет разбиений данного массива из 64 чисел на 4 (непересекающиеся) группы с суммой равной 2308

Предполагаю, что очень много.

[Pavlovsky]

Для четных N получается забавный алгоритм. Покажу на примере N=8.

Пусть у нас есть 64 числа из которых мы хотим построить пандиагональный квадрат.
1) Разобъем эти числа на 16 групп по 4 числа. Каждая группа из 4-х чисел (будем называть ее комплементарной) должна удовлетворять условию: A+B=C+D. A+B (C+D) будем называть комплементарной суммой четверки. Итого у нас получилось 16 чисел(комплиментарных сумм).
2) Построим из этих чисел пандиагональный квадрат 4х4.
3) Из квадрата 4х4 строим квадрат 8х8. Каждая комплементарная четверка будет расположена в решетке L(4). В нем сумма чисел в любой диагонали будет равняться магической сумме. Сумма чисел в строках (колонках) с номерами I и I+4 будет равняться удвоенной магической сумме.
4) Переставляя числа в комплементарных четверках, можно попытаться добиться, чтобы и во всех строках (колонках) у нас была магическая сумма. Сделать это вроде реально. У нас достаточно степеней свободы.

Пример. Квадрат 4х4:

462 330 492 300
330 462 300 492
300 492 330 462
492 300 462 330

Из которого можно получить пандиагональный квадрат 8х8, представленный Наталией:

005 013 463 293 443 283 053 031
313 379 071 073 089 079 191 389
023 211 167 331 199 353 149 151
449 239 041 097 059 127 349 223
019 047 439 269 457 317 029 007
241 383 109 103 017 083 229 419
101 139 181 311 277 281 163 131
433 173 113 107 043 061 421 233

[Nataly-Mak]

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

Внимание, вопрос!
Сколько всего будет разбиений данного массива из 64 чисел на 4 (непересекающиеся) группы с суммой равной 2308

Предполагаю, что очень много.

Вот 20 первых наборов (поставила счётчик, чтобы нашлось 20 наборов):

(Оффтоп)

3  5  7  11  13  17  19  23  127  271  277  283  293  311  317  331 
 3  5  7  11  13  17  19  23  131  263  281  283  293  311  317  331 
 3  5  7  11  13  17  19  23  131  269  277  281  293  311  317  331 
 3  5  7  11  13  17  19  23  137  257  281  283  293  311  317  331 
 3  5  7  11  13  17  19  23  137  263  277  281  293  311  317  331 
 3  5  7  11  13  17  19  23  137  269  271  281  293  311  317  331 
 3  5  7  11  13  17  19  23  139  271  277  281  283  311  317  331 
 3  5  7  11  13  17  19  23  149  251  277  281  293  311  317  331 
 3  5  7  11  13  17  19  23  149  257  269  283  293  311  317  331 
 3  5  7  11  13  17  19  23  149  257  271  281  293  311  317  331 
 3  5  7  11  13  17  19  23  149  263  269  277  293  311  317  331 
 3  5  7  11  13  17  19  23  151  257  269  281  293  311  317  331 
 3  5  7  11  13  17  19  23  151  269  271  277  283  311  317  331 
 3  5  7  11  13  17  19  23  157  241  277  283  293  311  317  331 
 3  5  7  11  13  17  19  23  157  251  269  281  293  311  317  331 
 3  5  7  11  13  17  19  23  157  257  263  281  293  311  317  331 
 3  5  7  11  13  17  19  23  157  263  271  277  283  311  317  331 
 3  5  7  11  13  17  19  23  157  271  277  281  283  293  317  331 
 3  5  7  11  13  17  19  23  163  241  271  283  293  311  317  331 
 3  5  7  11  13  17  19  23  163  251  263  281  293  311  317  331

Pavlovsky
алгоритм у вас уже есть, ждём оптимальное решение для N=8, например, $S=1154$

[Pavlovsky]

Я уже начал писать алгоритм для нечетных N.
Для четных N это пока наметки алгоритма. Например возникает вспомогательная задача.

Дано: Пусть у нас есть 64 числа из которых мы хотим построить пандиагональный квадрат.
Необходимо. Разобить эти числа на 16 групп по 4 числа. Каждая группа из 4-х чисел должна удовлетворять условию: A+B=C+D.

В качестве исходного массива чисел можно взять такой (взято из статьи Наталии Макаровой):

3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 311 317 331

[Nataly-Mak]

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

Я уже начал писать алгоритм для нечетных N.

А, ну тогда ждём оптимальное решение для N=7.
Какой алгоритм решили реализовать?

Я никак не могу начать писать программу нахождения набора из 4-х точных попарно ортогональных покрытий Массива №2. Вроде всё понятно и в то же время не знаю, с чего начать Можно пачками генерировать пары ортогональных покрытий. Но вот как к ним построить ещё два ортогональных покрытия?.. Теоретически-то понятно. Реализовать надо.