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

[Pavlovsky]

dimkadimon Вас опередили. Это открытие сделал svb. Смотрите его статью. Прикинул алгоритм использующий эти квадраты с нулевой магической суммой. Условное название алгоритма "Блуждающая дырка" или для тех кто знаком с радиотехникой "pn-переход". Нужно теперь его кодить. Правда этот алгоритм не перевый в очереди. Решил вернуться к регулярным квадратам и получить приличные результаты для N=13,17,19.

[Nataly-Mak]

Ага, так значит всё-таки квадраты с нулевой магической константой
Я тоже это сразу же предположила после сообщения Jarek

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

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

Вот в этом квадрате, как я понимаю, есть одна "блуждающая дырка" - 91

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

То есть пока она не блуждающая, а стоит на месте, но можно сделать её блуждающей

[Pavlovsky]

Jarek Wroblewski продолжает зверствовать. Предел моих мечтаний удержаться на уровне 6.00 балла.

-- Пн авг 12, 2013 08:12:00 --

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

То есть пока она не блуждающая, а стоит на месте, но можно сделать её блуждающей

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

-- Пн авг 12, 2013 08:25:28 --

Кто нибудь решает задачу построения квадратов с минимальным количеством ненулевых ячеек? В выходные поигрался немного в Excel никаких интересных идей не родилось. Есть гипотеза, что для составных N, можно построить решения из N+2 ненулевых ячеек. Решения dimkadimon увы далеки от теоретического минимума и их практически невозможно применить на практике. Естественно кроме вот этого:

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

Для N=10 нашёл хорошее решения с 12 ненулевыми ячейками, решил пока не показывать

[dimkadimon]

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

Кто нибудь решает задачу построения квадратов с минимальным количеством ненулевых ячеек? В выходные поигрался немного в Excel никаких интересных идей не родилось. Есть гипотеза, что для составных N, можно построить решения из N+2 ненулевых ячеек. Решения dimkadimon увы далеки от теоретического минимума и их практически невозможно применить на практике. Естественно кроме вот этого:

У меня прогрес в этой области:

N=12, non-zero=24
N=14, non-zero=16

Правда считаю этот подход тупиковым, так как я даже не могу найти решение для N=11

[Pavlovsky]

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

Правда считаю этот подход тупиковым, так как я даже не могу найти решение для N=11

Для N=11, мне удалось найти решение в районе 14000. Самое забавное в качестве начального был взят квадрат с магической суммой 1300000(миллион триста тысяч)!
Алгоритм блуждающей дырки должен дать гораздо лучшие результаты. Мы создаем дырки квадратом с 11 ненулевыми ячейками, при этом уменьшаем магическую константу. Затем эти дырки пытамеся замазать квадратами с 8 ненулевыми ячейками с нулевой магической суммой.

-- Пн авг 12, 2013 10:08:41 --

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

Правда считаю этот подход тупиковым

Тогда опубликуй самые вкусные решения:
N=10, non-zero=12
N=14, non-zero=16

[dimkadimon]

Эх ну да ладно. Я сам всё равно не буду ими пользоваться. Вот они красавцы:

N=10, S=2, non-zero=12
(0,0,0,0,0,0,2,0,0,0),
(0,0,0,2,0,0,0,0,0,0),
(2,0,0,0,0,0,0,0,0,0),
(0,0,1,0,0,0,0,1,0,0),
(0,0,0,0,0,2,0,0,0,0),
(0,0,0,0,0,0,0,0,2,0),
(0,2,0,0,0,0,0,0,0,0),
(0,0,0,0,2,0,0,0,0,0),
(0,0,1,0,0,0,0,1,0,0),
(0,0,0,0,0,0,0,0,0,2)

N=14, S=2, non-zero=16
(0,0,0,0,0,0,0,0,0,0,0,0,2,0),
(0,0,1,0,0,0,0,0,0,1,0,0,0,0),
(0,0,0,0,0,2,0,0,0,0,0,0,0,0),
(0,0,0,0,0,0,0,0,2,0,0,0,0,0),
(0,0,0,0,0,0,0,0,0,0,0,2,0,0),
(2,0,0,0,0,0,0,0,0,0,0,0,0,0),
(0,0,0,2,0,0,0,0,0,0,0,0,0,0),
(0,0,0,0,0,0,2,0,0,0,0,0,0,0),
(0,0,1,0,0,0,0,0,0,1,0,0,0,0),
(0,0,0,0,0,0,0,0,0,0,0,0,0,2),
(0,0,0,0,0,0,0,0,0,0,2,0,0,0),
(0,0,0,0,0,0,0,2,0,0,0,0,0,0),
(0,0,0,0,2,0,0,0,0,0,0,0,0,0),
(0,2,0,0,0,0,0,0,0,0,0,0,0,0)

Кстати я только сейчас заметил что эти решения очень похожи - имеют квадрат из единиц.

[Pavlovsky]

Спасибо, царский подарок. Обязательно воспользуюсь.

-- Пн авг 12, 2013 12:04:35 --

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

эти решения очень похожи - имеют квадрат из единиц

Действительно структура квадратов идентична. Похоже подобную структуру можно реализовать для всех порядков 2K, где K>=5 и K простое число.

[dimkadimon]

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

dimkadimon Вас опередили. Это открытие сделал svb. Смотрите его статью. Прикинул алгоритм использующий эти квадраты с нулевой магической суммой. Условное название алгоритма "Блуждающая дырка" или для тех кто знаком с радиотехникой "pn-переход". Нужно теперь его кодить. Правда этот алгоритм не перевый в очереди. Решил вернуться к регулярным квадратам и получить приличные результаты для N=13,17,19.

Страно что svb не воспользовался этой идеей. Получить регулярные решения не так просто как кажется. Я смог найти только N=13. Улучшил S в сто раз, а получил только 0.01 балла. А вот N=17 и 19 так и не смог найти.

[Nataly-Mak]

dimkadimon
вы у нас в лидерах

Цитата:

1 15.00 Jarek Wroblewski Wroclaw, Poland 12 Aug 2013 02:14
2 7.30 Dmitry Kamenetsky Adelaide, Australia 12 Aug 2013 08:22

Это очень хороший результат, если учесть результаты всех конкурсантов, кроме Jarek.
Алгоритм Jarek пока остаётся для меня загадкой.

svb, как всегда, оригинальничает. Бог его знает, какими идеями он воспользовался и не воспользовался. Мог бы с успехом поучаствовать в конкурсе

[dmd]

Господа, объясните пожалуйста ваш метод блуждающих дырок на конкретном простом примере.

[Pavlovsky]

Пусть у нас есть основной пандиагональный квадрат, где все числа простые и различны. Кроме одной ячейки с непростым числом 91 (назовем эту ячейку дыркой).

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

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

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

Вспомогательный квадрат применяется следующим образом. Если к ячейкам основного квадрата для которых во вспомогательном квадрате стоит 1, прибавить константу. А из ячеек, для которых во вспомгательном квадрате стоит -1, вычтем константу. То у нас снова получится пандиагональный квадрат, причем магическая константа не изменится. Если подобрать константу так, что во всех изменных ячейках будут стоять простые различные числа, включая ячейку с дыркой, то задача решена. Мы построили квадрат из простых чисел. Но рассчитвать, что задача будет так легко решаться не приходится. Поэтому делаем так. Подбираем константу так чтобы в ячейке с дыркой стояло простое число, но резрешаем чтобы дырка появилась в другой ячейке. Повторяем итеративно процедуру уже с новой дыркой. И так пока не построим квадрат состоящий из различных простых чисел.

PS Алгоритм еще не реализован. Так что говорить о его эффективности пока рано.

[Nataly-Mak]

Взяла своё решение для N=14 --- очень плохое, $S=362710$, и применила к нему квадрат dimkadimon, вкусный
Много отнять не получилось, всего уменьшила S на 400; при этом образовалось несколько дырок (я не проверяла, какие числа стали не простые, поэтому не знаю точно, сколько дырок, но они есть! Это не готовое решение, это полуфабрикат.).

6247 6091 14621 359 29669 59399 72623 61001 5101 269 18427 967 34667 52869
6857 18461 503 459 44257 50387 69431 56671 307 397 687 2927 59113 51853
68443 60887 9901 409 13913 829 39951 59119 2657 251 20627 14627 25463 45233
69197 56437 607 1697 593 1663 65707 69941 317 19 12347 24317 32587 26881
36761 53279 8663 14519 16421 461 21283 45119 73243 61027 5387 271 19197 6679
59167 51499 12161 24077 677 811 32353 26647 69497 57737 313 433 7187 19751
26083 45259 68729 60889 10671 6121 16007 839 42767 67547 4457 353 12241 347
32653 27947 69203 56473 6907 18521 647 1309 71011 75557 491 571 443 577
22013 15107 38561 53181 277 239 17041 487 21569 45121 74213 66739 7481 281
12091 25367 59341 52051 257 337 743 1877 32359 26683 75797 74561 367 479
12527 349 27253 50971 70823 60899 13487 14549 17807 941 34381 52867 5077 379
449 613 38953 44771 69257 56519 12211 24137 421 1861 59107 51817 557 1637
9281 383 13627 827 39181 53007 563 241 18211 6199 23663 45131 76829 75167
541 631 187 1627 59407 53117 263 373 7043 18701 32413 26729 81101 80177

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

Кстати, методом решёток можно и лучше решение построить для N=14, если с дырками (лучше --- с меньшей магической константой). Примитивные квадраты 7х7 первые два получаются легко, а последние два можно строить с дырками. Потом компоновать квадрат 14х14 по решёткам, вот и будет хороший исходный квадрат с дырками.

[dmd]

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

Еще вычитать можно константу не больше минимального числа в ячейке под -1 (без тройки). Т.е. в данном примере минимальное число 13, значит максимальная константа 13-3=10.

Иллюстрация размножение дырок всеми четными константами (ноль - дырка):

? a=0;print(isprime(233+a),isprime(389-a),isprime(409+a),isprime(13-a),isprime(91+a),isprime(79-a),isprime(61+a),isprime(83-a))
11110111
? a=2;print(isprime(233+a),isprime(389-a),isprime(409+a),isprime(13-a),isprime(91+a),isprime(79-a),isprime(61+a),isprime(83-a))
00010000
? a=4;print(isprime(233+a),isprime(389-a),isprime(409+a),isprime(13-a),isprime(91+a),isprime(79-a),isprime(61+a),isprime(83-a))
00000001
? a=6;print(isprime(233+a),isprime(389-a),isprime(409+a),isprime(13-a),isprime(91+a),isprime(79-a),isprime(61+a),isprime(83-a))
11011110
? a=8;print(isprime(233+a),isprime(389-a),isprime(409+a),isprime(13-a),isprime(91+a),isprime(79-a),isprime(61+a),isprime(83-a))
10010100
? a=10;print(isprime(233+a),isprime(389-a),isprime(409+a),isprime(13-a),isprime(91+a),isprime(79-a),isprime(61+a),isprime(83-a))
01111011

-- Пн авг 12, 2013 18:57:39 --

Хотя если совокупно изменить знаки у единичек, то максимальная константа будет 61-3=58

? forstep(a=0,58,2,print(isprime(233-a),isprime(389+a),isprime(409-a),isprime(13+a),isprime(91-a),isprime(79+a),isprime(61-a),isprime(83+a)))
11110111
00001010
10010100
10010001
01101010
10010100
01101000
00000011
00010000
00011111
01101011
10000100
00011111
00100001
00010100
01111111
01001010
10010100
10100000
00001010
10010000
11100010
01001011
00010000
00011111
01101010
10000100
11011011
00100011
00010110

[Pavlovsky]

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

Дырка то не одна появляется, дырки будут множиться.

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

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

Нужны получается множество вспомогательных квадратов с нулевой суммой. Как их генерировать? Это они базисные?

Берем квадрат

0 -1 1 0 0 0 0
1 0 0 -1 0 0 0
-1 0 0 1 0 0 0
0 1 -1 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

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

[dmd]

Pavlovsky
Спасибо. Теперь в принципе стало понятно. Осталось найти соответствующие формулы переноса на торе и альфа-преобразования. А, и еще уметь генерить исходный нулевой квадрат.