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

[whitefox]

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

Поясните, как это проверяется.

Изложу позже. Обеденный перерыв заканчивается.

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

Вы можете представить себе все точные покрытия, сделанные из 393510 цепочек? Я, честно говоря, не могу.

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

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

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

Да это так.
Дайте мне пару ортогональных покрытий, и я представлю полумагический квадрат.

Архимед писал(а):

Дайте мне точку опоры, и я переверну Землю.

[Nataly-Mak]

Вот нашла два ортогональных покрытия (всё из того же моего решения - обычный МК с магической константой 733).

Первое покрытие (строки):

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

Второе покрытие (столбцы):

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

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

3 5 7 23 223 233 239
37
151
53
199
79 
211

Верно?
Пошла дальше писать

Получилось:

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

Да, с полумагическими квадратами всё просто.
Недаром svb начинал именно с полумагических квадратов свои исследования по базисам.

[whitefox]

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

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

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

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

Для каждой найденной трансверсали можно рассмотреть (N-1)! различных перестановок её элементов. Каждая перестановка однозначно определяет почти магический квадрат (то есть полумагический квадрат у которого главная диагональ тоже магическая). Остаётся только проверить все эти квадраты на пандиагональность.

Но, на самом деле, нет необходимости рассматривать все (N-1)! перестановок. Изоморфизм позволяет существенно сократить объём работы. Например, при N=7 достаточно рассмотреть 90 паросочетаний, для каждого проверить побочную диагональ, и только для магических побочных диагоналей выполнить ещё 8 М-преобразований полученного магического квадрата, проверяя каждый изоморф на пандиагональность. При больших N сокращение объёма работы будет более значительным.

[Nataly-Mak]

Спасибо. Мудрёно, сразу не понять
Термин "трансверсаль", кажется, встречала у alexBlack (что-то было связано с латинскими квадратами), но тогда тоже не вникала.

А как вы смотрите на идею генерировать сразу набор 4-х попарно ортогональных покрытий?
И затем проверять его на возможность получения пандиагонального квадрата?
Как получить полумагический квадрат из двух ортогональных покрытий, вы рассказали.
А как проверить набор 4-х попарно ортогональных покрытий на возможность сделать из них пандиагональный квадрат? Это требует бльшого объёма перебора?

[mertz]

new version. It is a little faster. The program would be much faster if the 2D and 3D arrays where made into 1D arrays. The program is to complex for me to change. Parameters that control the inner loops can really effect speed. I am not sure if Jarek tuned the parameters for N=7 or for general use.

https://www.dropbox.com/s/utxwf45xo83ry6l/Pan.exe

[Nataly-Mak]

Сейчас работаю с программой поиска решения $S=733$ по общей формуле со случайным выбором первых 10 свободных переменных. На полный перебор остаются 13 свобдных переменных. Вставила в программу автоматическую генерацию вектора номеров 10 свободных переменных (вектор K в моём описании выложенной выше программы).
Процесс идёт быстро. Сначала вставила выход при найденных 35 элементах квадрата. Это получила довольно быстро:

 199  0  41  223  5  0  3 
 0  61  23  151  233  149  0 
 239  0  47  11  173  0  211 
 0  101  0  109  0  43  0 
 71  37  163  83  59  181  139 
 7  107  0  67  0  127  191 
 29  179  0  89  0  167  131 

Теперь поставила выход при получении решения с двумя дырками.

Думаю, что шансы получить решение $S=735$ намного выше, чем для решения $S=733$. Но это всего лишь рабочая гипотеза.

-- Чт авг 29, 2013 23:39:02 --

mertz
спасибо, что вы работаете над улучшением программы.
Скачала новую версию. Завтра буду искать решения.
У меня параллельно работает моя программа. Две программы мой компьютер тянет

Будем надеяться, то Jarek поможет нам, когда вернётся с отдыха.

[Nataly-Mak]

Оказывается, мы не одиноки...

Цитата:

7x7 749 Wes Sampson La Jolla, California, United States 30 Aug 2013 01:24

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

Радостно очень! Спасибо, Wes Sampson!

Пространство поиска ещё уменьшилось. Осталось всего 8 потенциальных магических констант.

[mertz]

This is a different version and has a new name. I adjusted the internal parameters. It is about 3 times faster. It does more searches, but does not search as deep.

https://www.dropbox.com/s/pvpcyeuf9fb8355/Pan2.exe

[Nataly-Mak]

mertz
вы неутомимы
Скачала новую версию. Да, программа работает заметно быстрее.
Сегодня буду искать решение $S=743$.

-- Пт авг 30, 2013 09:19:59 --

Искала в теме "Магические квадраты" теоретическое доказательство 12d3 несуществования магического квадрата 7-го порядка из чисел Смита с магической константой 3719 (оказывается, порядок квадрата был тоже 7, а не 6, как я написала выше; забыла немножко).
Пока не добралась до этого доказательства, по пути мне попалось другое доказательство, оно тоже проведено методом, который использовал 12d3.

svb в сообщении #308796 писал(а):

Несколько слов о невозможности квадрата 5858

Если рассмотреть квадрат с магической суммой 5858 по модулю 9, воспользовавшись методом 12d3, можно увидеть распределение остатков:
0 - 7 шт.
3 - 1 шт.
4 - 37 шт.
6 - 16 шт.
8 - 3 шт.
В каждом ряду суммы этих остатков могут принимать значения 8, 17, 26, 35, 44, 53 .. (=8 (mod 9)). Оценим максимальную сумму, она меньше 8+8+8+6+6+6+6+6=54, но не может быть =53. Сумма остатков=271, т.е. мы можем написать:
$8x+17y+26z+35u+44t=271$,
где x,y,z,u,t - количества рядов с соответствующими суммами, $x+y+z+u+t=8$, исключив $u$ можно переписать:
$3x+2y+(z-t)=1$
при этом $u+y=8-x-z-t=1$, т.к. 3 всего одна, т.е. $t=7-x-z$, или
$2x+y+z=4$
Итого, 3 решения:
$1. x=2, z=0, t=5$ примем y=0, u=1, другой вариант хуже
$2. x=1, z=2, t=4$
$3. x=0, z=4, t=3$
Но t не может быть больше 3, т.к. 8-ок всего 3, и при t=3 в каждую строку с суммой 44 может входить только одна 8 (и обязательно входит). С учетом этого максимальное число 4-ок в строках:
8 - 2 (0 0 0 0 0 0 4 4)
26 - 5 (0 0 4 4 4 4 4 6)
35 - 5 (3 4 4 4 4 4 6 6)
44 - 3 (4 4 4 6 6 6 6 8)
Для оставшегося решения максимальное число 4-ок:
3. 0*2+4*5+3*3+1*6=35
А у нас 37, т.е. решения нет.

Ниже приведены все возможные строки

0 0 0 0 0 0 0 8  ( 8)
0 0 0 0 0 0 4 4  ( 8)
0 0 0 0 0 3 6 8  (17)
0 0 0 0 3 4 4 6  (17)
0 0 0 4 4 4 6 8  (26)
0 0 0 4 4 6 6 6  (26)
0 0 3 4 4 8 8 8  (35)
0 0 3 4 6 6 8 8  (35)
0 0 3 6 6 6 6 8  (35)
0 0 4 4 4 4 4 6  (26)
0 3 4 4 4 4 8 8  (35)
0 3 4 4 4 6 6 8  (35)
0 3 4 4 6 6 6 6  (35)
0 4 4 6 6 8 8 8  (44)
0 4 6 6 6 6 8 8  (44)
0 6 6 6 6 6 6 8  (44)
3 4 4 4 4 4 4 8  (35)
3 4 4 4 4 4 6 6  (35)
4 4 4 4 4 8 8 8  (44)
4 4 4 4 6 6 8 8  (44)
4 4 4 6 6 6 6 8  (44)
4 4 6 6 6 6 6 6  (44)

Такое вот теоретическое доказательство и никаких переборов не надо. Помимо перебора существует математика.
[Здесь доказывается невозможность построить магический квадрат 8-го порядка из чисел Смита с магической константой 5858.]

Давайте подумаем все вместе над вопросом существование/несуществования пандиагонального квадрата 7-го порядка из различных простых чисел с магической константой 733. Есть всего два массива простых из 49 чисел, которые надо подвергнуть анализу.

[whitefox]

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

А как проверить набор 4-х попарно ортогональных покрытий на возможность сделать из них пандиагональный квадрат? Это требует бльшого объёма перебора?

Перебор не большой, особенно если N простое.
Поясню алгоритм для этого случая.

Четыре покрытия можно объединить в пары только тремя способами.
Вот их-то и придётся перебрать.

Пусть нам даны две пары покрытий.
Любую из пар выберем в качестве "рядов" (строки и столбцы), во второй паре будут, соответственно, диагонали.

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

Это сразу даёт ещё два числа в двух других углах, и вместе с ними побочную диагональ.

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

Продолжая в том же духе заполним весь квадрат, если это возможно.

[Nataly-Mak]

whitefox
спасибо за пояснения.
Так это хорошо, что проверка набора из 4-х покрытий на предмет построения из них пандиагонального квадрата занимает не так много времени. К тому же, N у нас сейчас как раз простое.

Тогда сам Бог велит попробовать алгоритм:
1. генерируем набор из 4-х попарно ортогональных покрытий;
2. проверяем возможность построения из этих покрытий пандиагонального квадрата.

Вы писали, что два ортогональных покрытия генерируются мгновенно. А 4 попарно ортогональных покрытия?

[whitefox]

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

Но в отличии от полумагических квадратов, случайный пандиагональный квадрат не генерится мгновенно, да и вообще не генерится (хотя вероятность этого не равна нулю).

[Nataly-Mak]

whitefox в сообщении #758909 писал(а):

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

Это гипотеза? Над доказательством думали?

Цитата:

Но в отличии от полумагических квадратов, случайный пандиагональный квадрат не генерится мгновенно, да и вообще не генерится (хотя вероятность этого не равна нулю).

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

[whitefox]

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

Это гипотеза? Над доказательством думали?

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

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

Ага, значит, найти набор из 4-х попарно ортогональных покрытий не так просто.
А алгоритм поиска у вас есть?

Алгоритм есть, но реализовывать его не стал.

Это поиск с возвратом.

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

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

Если в базе нет такого разбиения -- делаем откат.

[Nataly-Mak]

whitefox в сообщении #758918 писал(а):

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

Это гипотеза? Над доказательством думали?

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

Напрасно не думали. Это очень важная гипотеза! Её желательно доказать.
Если она будет доказана, тогда построение пандиагонального квадрата будет равносильно поиску набора из 4-х попарно ортогональных покрытий.

Цитата:

Алгоритм есть, но реализовывать его не стал.

Это поиск с возвратом.

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

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

Если в базе нет такого разбиения -- делаем откат.

И алгоритм поиска набора 4-х попарно ортогональных покрытий очень простой и понятный.
За чем дело стало?

-- Пт авг 30, 2013 11:04:21 --

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

Давайте подумаем все вместе над вопросом существование/несуществования пандиагонального квадрата 7-го порядка из различных простых чисел с магической константой 733. Есть всего два массива простых из 49 чисел, которые надо подвергнуть анализу.

Массив №1:

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 233 239

Состоит из следующих вычетов по модулю 9:

вычет 0 - нет
1 - 8 шт
2 - 8 шт
3 - 1 шт
4 - 8 шт
5 - 9 шт
6 - нет
7 - 7 шт
8 - 8 шт

$S=733=4(\mod9) $

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

-- Пт авг 30, 2013 11:16:22 --

Массив №2 для той же магической константы 733:

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 227 229 239

Состоит из следующих вычетов по модулю 9:

вычет 0 - нет
1 - 8 шт
2 - 9 шт
3 - 1 шт
4 - 9 шт
5 - 9 шт
6 - нет
7 - 6 шт
8 - 7 шт

-- Пт авг 30, 2013 11:25:10 --

mertz
у меня почему-то только два потока работают вместо 4



-- Пт авг 30, 2013 11:37:30 --

Вот нашла, наконец, и доказательство 12d3:

12d3 в сообщении #307628 писал(а):

Итак, очевидно приведенный набор с константой 3719 единственен. Если мы рассмотрим остатки чисел по модулю 9 в данном наборе, то увидим такое распределение остатков:
0 - 6 штук.
3 - 1 штука.
4 - 27 штук.
6 - 8 штук.
8 - 1 штука.
Остаток от нашей константы 3719 равен 2.
Теперь нам надо найти, какие наборы из 7 остатков могут давать в сумме остаток 2. Тут небольшой перебор, его можно провести ручками, можно на компьютере перебрать, я приведу сразу результат:

4 4 6 6 6 6 6
4 4 4 6 6 6 8
3 4 4 4 4 4 6
0 6 6 6 6 6 8
0 3 4 4 6 6 6
0 3 4 4 4 6 8
0 0 3 6 6 6 8
0 0 4 4 4 4 4
0 0 0 4 4 6 6
0 0 0 4 4 4 8
0 0 0 0 6 6 8
0 0 0 0 3 4 4
0 0 0 0 0 3 8

Всего получается 13 вариантов строчек.
Теперь надо выбрать 7 строчек так, чтобы суммарное кол-во остатков каждого типа в этих строчках было равно кол-ву остатков во всем наборе(указанному выше).
Я тут перебирал ручками, используя тот факт, что остатков 4 в наборе очень много. Получил всего один вариант набора из 7 строк.
4 4 6 6 6 6 6 - 2 штуки
0 0 4 4 4 4 4- 3 штуки
4 4 4 6 6 6 8- 1 штука
3 4 4 4 4 4 6 - 1 штука

(Оффтоп)

Небольшое отступление. Тут видно, что генерировать наборы из 7 строк надо, выбирая строчки из этих групп. А если делать перебор по всем строкам, это будет намного дольше. у меня сгенерировалось не менее 10000 наборов из 7 строк. Один из них:

4 22 438 483 825 861 1086 
58 85 627 645 690 762 852 
27 94 265 648 778 922 985 
121 166 274 576 729 895 958 
346 378 454 535 634 666 706 
202 319 517 636 654 663 728 
355 382 391 526 562 588 915 

Очевидно, такое же распределение должно быть для столбцов.
У нас должно быть три строки с нулями. и три столбца с нулями. Рассмотрим клетки, которые находятся в строках без нулей, но в столбцах с нулями. В этих клетках могут быть только четверки, ибо в столбцах с нулями, кроме нулей находятся только четверки. То есть получаем, что в каждой строке без нулей находится минимум 3 четверки, что противоречит найденному распределению остатков. То есть, даже ПМК построить из данного набора нельзя.

Имеем два аналогичных доказательства для магических квадратов 7-го и 8-го порядков (для порядка 8 см. выше). Но это были обычные магические квадраты.
Теперь у нас пандиагональный квадрат 7-го порядка. Можно ли для него применить такое же доказательство?