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

[Nataly-Mak]

Так вот и сделала аналогичную общую формулу. Но для порядка 5 формула получилась типа 8 + 17 (только 8 свободных переменных), а для порядка 6 формула типа 16 + 20. Разницу замечаете? Что 8 переменным пробежать циклы (вложенные) от 1 до 25, а что 16 переменным пробежать циклы (вложенные) от 1 до 36.

Для порядка 5 программа шутя отрабатывает все 8 циклов.

-- Чт авг 19, 2010 15:18:52 --

Выложила программу на сайте:
http://www.natalimak1.narod.ru/mk/PAN6OB.rar

В архиве две программы.

1. PAN6FORM.EXE
Это программа-тест. В ней заданы конкретные значения для перменных первых 7 циклов. Программа мгновенно строит пандиагональный квадрат из массива, который находится в файле MK3.txt.
Построенный квадрат записывается в файл MK1.txt и выводится на экран.

2.PAN6OB.EXE
Это общий вариант программы. Здесь отрабатывают все циклы. На экран я вывела печать значений переменной одного цикла, который и не бежит, и совсем не стоит, то есть вполне нормально двигается, это цикл по свободной переменной A9.
Для запуска программы необходимо в файл MK3.txt записать заданный массив чисел вместо того, который там записан сейчас.
Например, можно ввести массив чисел, из которых составлен наименьший МК 6-го порядка из простых чисел с магической константой 432 (он показан чуть выше).
Можно оставить тот же самый массив, который сейчас записан в файле MK3.txt, пусть отработает для этого массива. Тем более, для этого массива пандиагональный квадрат точно существует. Вот пусть программа его найдёт, без подсказок

Необходимо сделать замечание: я не варьирую самую первую свободную переменную, то есть пишу для неё: for a2=1 to 1. Считаю, что из-за пандиагональности это должно сработать. Правильно я рассуждаю?
Таким образом, фактически циклов 15.
Так что возможен такой исход (в случае, если мои рассуждения неверны): программа для тестируемого массива полностью отработает, а квадрат не найдёт. Но вроде бы правильные рассуждения: ведь поскольку квадрат пандиагональный, то в ячейке с этой свободной переменной можно поставить любое значение (с помощью параллельного переноса на торе).

Приглашаю всех опробовать работу программы. Могу заинтересовавшимся выложить и исходный текст программы на Бейсике.

[Nataly-Mak]

Вспомнила замечательную теорию 12d3.

Рассмотрим наименьший МК из простых чисел:

3 5 47 109 131 137
89 73 53 97 61 59
151 167 83 7 11 13
71 41 107 103 67 43
17 19 29 79 139 149
101 127 113 37 23 31

Если записать числа этого квдарата по модулю 9, получится такой квадрат:

3 5 2 1 5 2
8 1 8 7 7 5
7 5 2 7 2 4
8 5 8 4 4 7
8 1 2 7 4 5
2 1 5 1 5 4

То есть весь массив состоит из следующих чисел (по модулю 9):

1,1,1,1,1
2,2,2,2,2,2
3
4,4,4,4,4
5,5,5,5,5,5,5,5
7,7,7,7,7,7
8,8,8,8,8

Магическая константа квадрата S = 0(mod 9).

Можно ли расположить эти числа в квадрате так, чтобы суммы по всем разломанным диагоналям тоже были равны 0(mod 9)?

svb
вы, помнится, очень хорошо разобрались с этой теорией. Подумайте над этой задачкой, пожалуйста. Вы вообще почему-то перестали работать. Жара закончилась, а вы всё отлыниваете. Делаю вам замечание

Pavlovsky
на форуме Портала ЕН где-то промелькнуло утверждение:
необходимым условием для построения пандиагонального квадрата 6-го порядка является следующее условие: сумма всех чисел массива делится на 36.
Это точно?
Если брать только что рассмотренный массив, для него это условие выполняется.

[Pavlovsky]

Вот что смущает, минимальные известные магические суммы для пандиагонального МК 6х6 630, а для МК 7х7 1649. Почему такой большой разрыв? Наверно из-за того, что при поиске МК 7х7 мы наложили требование регулярности по Россеру?! Тем самым исскуственно сузили круг поиска. Всвязи с этим, возникают задачи:

1)Для программистов. Найти нерегулярный пандиагональный МК 7х7 с магической суммой значительно меньше 1649.

2)Для математиков доказать или опровергнуть гипотезу.
Гипотеза. Пусть задано простое число N>5 и задано некторое подмножество множества натуральных чисел. Пусть пострены все пандиагональные МК NxN из N^2 различных чисел из заданного подмножеста. Тогда если среди всех построенных МК, K минимальная магическаяч сумма, тогда существует регулярный пандиагональный МК NxN с магической суммой K.

-- Чт авг 19, 2010 17:44:37 --

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

Pavlovsky
на форуме Портала ЕН где-то промелькнуло утверждение:
необходимым условием для построения пандиагонального квадрата 6-го порядка является следующее условие: сумма всех чисел массива делится на 36.
Это точно?
Если брать только что рассмотренный массив, для него это условие выполняется.

Это условие следует из теорем 2.4 и 2.5. Это условие является только необходимым. То есть если сумма набора делится на 36, это не гарантирует постороение МК.

[Nataly-Mak]

Совершенно верно. Я тоже предполагаю, что наверняка существуют пандиагональные квадраты порядка 7 с меньшей магической суммой. Ведь наименьший обычный МК 7-го порядка имеет магическую сумму 733.
Вполне возможно, что эти пандиагональные квадраты не строятся из примитивного квадрата, то есть не являются регулярными (по Россеру).

-- Чт авг 19, 2010 16:49:18 --

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

Это условие следует из теорем 2.4 и 2.5. Это условие является только необходимым. То есть если сумма набора делится на 36, это не гарантирует постороение МК.

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

[Pavlovsky]

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

Вспомнила замечательную теорию 12d3.
Если записать числа этого квдарата по модулю 9, получится такой квадрат:

Лучше брать по модулю 6

Тогда у нас получится следующий набор остатков:
3 1шт
-1 19шт
1 16шт

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

-- Чт авг 19, 2010 18:06:55 --

Добавлю. Число 3 плохое. При поиске минимальных МК его лучше не использовать.

-- Чт авг 19, 2010 18:19:01 --

Забавно. Пусть у нас есть набор чисел из которых мы хотим построить МК. Возьмем остатки от деления по mod(k), тогда сумма остатков должна равняться 0mod(k), для любого k.

Получился алгоритм предварительного тестирования набора на возможность построить МК. Причем этот тест годится для любых видов МК (полумагические, магические, пандиагональные) и любых видов чисел (простые, Смита и т.д.)

[Garik2]

Прогу общую запустил. Что такое А9 ?
Я не вижу на каком внешнем цикле нахожусь без движений. Это конечно нехорошо.
Могу только сказать, что цикл от 1 до 36 у меня на экране проходит в среднем за 2 сек.

[Nataly-Mak]

Pavlovsky
очень интересны ваши наблюдения.
Действительно, по модулю 6 удобнее.
И тест для массива чисел интересный. Получается, что это необходимое условие. Если оно не выполняется, то из чисел массива нельзя построить МК - никакой. Правильно я поняла?

Garik2
Да почти все внешние циклы без движения
Цикл по переменной A9 - это первый цикл, который движется.
A9 - это одна из свободных переменных (см. общую формулу). Я прямо так и обозначила свободные переменные, как они обозначены в формуле. Перед A9 ещё такие свободные переменные (это всё внешние циклы по отношению к A9): A2, A3, A4, A5, A6, A7, A8. При этом, как я уже сказала, по переменной A2 я цикл фактически убрала (A2=1). Значит, осталось 6 внешних циклов.
Для какого массива вы запустили программу?
Программу-тест проверили?

[Garik2]

нет, не стал тест проверять. Какой смысл? Разорхивация ничего худого не делает.
Я запустил то, что у Вас было. Ничего не менял и не вставлял. Просто хочу посмотреть на скорость счета, чтобы понять: реально ли за мой век довести дело до конца?
Пока что в МК1 0 байтов информации...

[Nataly-Mak]

А для какого массива запустили программу? Для того, который был записан в MK3.txt?
Ага, поняла
Ну, в MK1.txt появится информация только тогда, когда квадрат будет найден. Программа работает до первого найденного квадрата. Квадрат появится и на экране и программа выйдет в "Конец программы".

[Garik2]

Ок! Хорошо что не "Конец Света".

[svb]

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

svb
вы, помнится, очень хорошо разобрались с этой теорией. Подумайте над этой задачкой, пожалуйста. Вы вообще почему-то перестали работать. Жара закончилась, а вы всё отлыниваете. Делаю вам замечание

Сегодня, можно сказать, первый хороший день и весь день я провозился с пандиагональными квадратами 6 порядка. Смотрел любопытные картинки. У квадратов 6 порядка имеются любопытные элементы, которые можно взять за базис:
$\left( {\begin{array}{*{20}c} 0 & 1 & { - 1} & 0 & 1 & { - 1} \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & { - 1} & 1 & 0 & { - 1} & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array}} \right)$ и $\left( {\begin{array}{*{20}c} 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & { - 1} & 0 & 0 \\ { - 1} & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & { - 1} & 0 & 0 \\ { - 1} & 0 & 0 & 1 & 0 & 0 \\ \end{array}} \right)$
Как легко видеть, они образуют пространство размерности 12 (включаем все плавающие на торе элементы), т.е. "немного" не дотягивают до положенных 15. Но натянутое на эти элементы векторное пространство очень любопытно. Прежде всего, посмотрите на угловой квадрат $3 \times 3$. Элементы первого вида порождают квадраты типа
$\left( {\begin{array}{*{20}c} A & A \\ { - A} & { - A} \\ \end{array}} \right)$
где $A$ - квадраты с нулевыми строками, а элементы второго вида порождают квадраты типа
$\left( {\begin{array}{*{20}c} B & { - B} \\ B & { - B} \\ \end{array}} \right)$
где $B$ - квадраты с нулевыми столбцами. Линейные комбинации подобных квадратов и дают некоторое подпространство в пространстве пандиагональных квадратов:
$\left( {\begin{array}{*{20}c} {A + B} & {A - B} \\ { - A + B} & { - A - B} \\ \end{array}} \right)$
Прежде всего меня заинтересовало, можно ли получить квадраты со всеми различными элементами - нужно было просто проверить. Пусть итоговый квадрат имеет вид:
$\left( {\begin{array}{*{20}c} {{\bf x1}} & {{\bf x2}} & {{\bf x3}} & {{\bf x4}} & {{\bf x5}} & {x6} \\ {{\bf y1}} & {{\bf y2}} & {{\bf y3}} & {{\bf y4}} & {{\bf y5}} & {y6} \\ {{\bf z1}} & {{\bf z2}} & {z3} & {z4} & {z5} & {z6} \\ * & * & * & * & * & * \\ * & * & * & * & * & * \\ * & * & * & * & * & * \\ \end{array}} \right)$
где жирным шрифтом выделены 12 независимых параметров. Остальные вычисляются по формулам:
$z3=-x1-x2-x3-y1-y2-y3-z1-z2$
$z4=x1+y1+z1-x4-y4$
$z5=x2+y2+z2-x5-y5$
$x6=-x1-x2-x3-x4-x5$
$y6=-y1-y2-y3-y4-y5$
$z6=-z1-z2-z3-z4-z5$
Теперь мне нужно было на чем-нибудь проверить, я взял у Наталии квадрат, привел его к нулевой сумме (отнял 25) и получил
$\left( {\begin{array}{*{20}c} { - 24} & {22} & { - 19} & {23} & { - 20} & * \\ {10} & { - 8} & 5 & { - 9} & 6 & * \\ {11} & { - 13} & * & * & * & * \\ \end{array}} \right)$
Итоговый пандиагональный квадрат (уже добавил 25):
$\left( {\begin{array}{*{20}c} 1 & {47} & 6 & {48} & 5 & {43} \\ {35} & {17} & {30} & {16} & {31} & {21} \\ {36} & {12} & {41} & 8 & {40} & {13} \\ 2 & {45} & 7 & {49} & 3 & {44} \\ {34} & {19} & {29} & {15} & {33} & {20} \\ {42} & {10} & {37} & {14} & {38} & 9 \\ \end{array}} \right)$
Пока все.

[Nataly-Mak]

svb
моё замечание возымело действие

Алгоритм супер! Правда, до конца не вникла, но вижу, что очень хорош.
Как я поняла, в вашей формуле всего 12 свободных элементов вместо моих 16. Это огромное преимущество.

Сейчас ещё посмотрела. Закралось сомнение: не является ли этот алгоритм действенным только для совершенных квадратов 6-го порядка? Это пока неуверенное сомнение. Не получилось ли у вас подпространство совершенных квадратов?
Вы неудачно выбрали квадрат для проверки, этот квадрат (исходный) идеальный. И полученный вами пандиагональный (и совершенный!) квадрат элементарно получается из исходного квадрата преобразованием 3-х квадратов.
Просьба: проверьте работу алгоритма на единственном известном пандиагональном, но не ассоциативном, квадрате из последовательных простых чисел с магической константой 930:

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

Я пока до конца не поняла алгоритм, поэтому не могу сама проверить. Надо вникнуть.

А я вот собралась составить пандиагональный квадрат из элементов 1, 3, 5, найдя остатки по модулю 6 для наименьшего пандиагонального квадрата из простых чисел (с магической константой 432). Может быть, это тоже что-нибудь даст.

[svb]

Другими словами:
1. Пусть имеется 18 пар $x1+y1=m, ..., x18+y18=m$, $m$ - четное
2. Магическая сумма $S=3*m$
3. Выбираем две групы по 9 чисел из различных пар с суммой в каждой группе равной $9m/2$:
$a1+...+a9=b1+...+b9=9m/2$
4. Расположим эти 18 чисел в таблицу
$a1+a2+a3+b1+b2+b3=S$
$a4+a5+a6+b4+b5+b6=S$
$a7+a8+a9+b7+b8+b9=S$
чтобы выполнялись равенства по столбцам:
$a1+a4+a7=b1+b4+b7$
$a2+a5+a8=b2+b5+b8$
5. Получаем пандиагональный квадрат:
$\left( {\begin{array}{*{20}c} {a1} & {a2} & {a3} & {b1} & {b2} & {b3} \\ {a4} & {a5} & {a6} & {b4} & {b5} & {b6} \\ {a7} & {a8} & {a9} & {b7} & {b8} & {b9} \\ {b1'} & {b2'} & {b3'} & {a1'} & {a2'} & {a3'} \\ {b4'} & {b5'} & {b6'} & {a4'} & {a5'} & {a6'} \\ {b7'} & {b8'} & {b9'} & {a7'} & {a8'} & {a9'} \\ \end{array}} \right)$

А независимых переменных вместе с магической суммой 13.

[Nataly-Mak]

Спасибо за подробное изложение формулы.

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

Надо проверить на простом пандиагональном квадрате работу вашего алгоритма.

Начала читать ваше изложение алгоритма: "Пусть имеется 18 пар чисел..."
Так это и значит, что вы строите квадрат из комплементарных пар чисел! Правильно?
Но это значит, что можно построить сначала ассоциативный квадрат (а при построении этого квадрата да, кажется, у меня и было 12 свободных элементов), а потом превратить его в пандиагональный с помощью преобразования 3-х квадратов. По этому алгоритму я уже построила пандиагональный квадрат с магической константой 630 (он составлен из 18 комплементарных пар простых чисел с суммой в паре 210).

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

[svb]

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

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

Этот набор не подходит для данного алгоритма, еще три степени свободы не задействованы