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

[Nataly-Mak]

Алгоритмы Россера, конечно, классные. Однако не стоит останавливаться только на этих алгоритмах. Есть и другие алгоритмы. Об одном из них я уже говорила, это алгоритм svb для N=6.
Я сначала нашла решение для N=8 по алгоритму Россера (решётки), а потом разработала новый алгоритм и нашла лучшие решения.

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

е х1 х2 х3 х4
х5 х6 а х7 х8
х9 х10 х11 х12 в
х13 d х14 х15 х16
х17 х18 х19 с х20

Сразу отмечу: переменные a,b,c,d,e,x18,x19,x20,S (магическая константа квадрата) независимые (свободные), остальные переменные зависимые.

x1 = x20 - d + c 
x2 = S - x19 - b - x20 + d - x18 - c
x3 = b + x18 - a
x4 = x19 - e + a
x5 = d + x18 - a
x6 = x19 + b - e
x7 = e + x20 - d
x8 = S - x19 - b - x20 - x18 
x9 = x20 + a - d
x10 = S - x18 - c - x19 - b - x20 + e
x11 = -a + x18 + c
x12 = d - e + x19
x13 = c + x19 - e
x14 = -d + b + x20
x15 = S - x18 - c - x19 - b - x20 + a
x16 = x18 + e - a
x17 = S - x18 - x19 - x20 - c

Можно сразу задать магическую константу квадрата S; тогда останется 8 свободных переменных.
Все свободные переменные должны перебираться, все зависимые переменные вычисляются по значениям, принимаемым свободными переменными.
Эту формулу легко реализовать.
Но уже для порядка 6 всё становится намного сложнее - в реализации.
Однако не всё безнадёжно.

И вот чтобы найти нерегулярный пандиагональный квадрат 7-го порядка, надо как раз отвлечься от примитивных квадратов (тут уже ничего выжать невозможно: минимальный регулярный квадрат найден!) и попробовать искать квадрат по общей формуле.
По крайней мере, идеальные квадраты 7-го порядка по общей формуле находятся довольно быстро (есть и у меня такие решения, и у alexBlack).

Примечание: общая формула пандиагонального квадрата 7-го порядка есть в моей статье.

[Pavlovsky]

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

Pavlovsky
сообщении #729858]здесь
я привела решение вашей задачи для идеального квадрата 7-го порядка.
Вы это читали?
Но идеальный квадрат является пандиагональным!
Ваша задача решена?

Читал. Задача не решена. Внимательно прочитайте условия задачи.
Я так понимаю, для N=7 регулярный квадрат с константой 1597 минимален. Для решения поставленной мной задачи, осталось найти нерегулярный квадрат с константой меньше 1597. Или доказать, что это невозможно.

[Nataly-Mak]

Прочитала внимательно условие задачи:

Цитата:

Найти пандиагональный МК 7х7 из различных простых чисел с магической константой C и доказать, что не существует регулярного (по Россеру) пандиагонального МК 7х7 из различных простых чисел с константой равной или меньшей C. Или доказать, что это невозможно.

И что же конкретно вас не устраивает в решении задачи, приведённом мной?

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

Прошу ваши контраргументы.

[dimkadimon]

Pavlovsky

Чем отличаются регулярные решения от нерегулярных?

[Nataly-Mak]

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

Pavlovsky

Чем отличаются регулярные решения от нерегулярных?

Хотя вопрос не ко мне, попробую ответить.
Регулярный пандиагональный квадрат (по Россеру) может быть получен из примитивного квадрата. Другими словами: каждому регулярному пандиагональному квадрату обязательно соответствует примитивный квадрат (этот примитивный квадрат можно получить из пандиагонального преобразованием, обратным преобразованию Россера).

Если мы возьмём нерегулярный пандиагональный квадрат, то ему не соответствует примитивный квадрат. Другими словами: из чисел, составляющих нерегулярный пандиагональный квадрат, нельзя построить примитивный квадрат (хотя это верно и не всегда; например, в случае классических пандиагональных квадратов из чисел от 1 до $n^2$ можно построить как регулярные, так и нерегулярные пандиагональные квадраты).

Кажется, в статье Россера есть ещё определение регулярных и нерегулярных пандиагональных квадратов. Но я понимаю эти квадраты так, как написала.

[dimkadimon]

Значит регулярные квадраты существуют для всех простых N>3? А если взять несколько регулярных квадратов и их "склеить", как например в решении N=10 мы склеили четыре 5х5, то результат уже нерегулярный квадрат?

[Pavlovsky]

Понятие "Регулярный пандиагональный квадрат" введено в статье Россера.

Кратко:
Регулярный пандиагональный квадрат - это квадрат, который можно получить преобразованием (Россера) примитивный квадрат -> пандиагональный квадрат.

В статье доказано, что все пандиагональные квадраты порядков 4,5 - регулярные. Для N>5 существуют как регулярные квадраты, так и нерегулярные. В статье есть тонкости, поэтому будем считать N простым числом.

Все известные мне решения (N=7,11,13,17,19) с минимальной константой, являются регулярными квадратами (получены преобразованием из примитивного квадрата).

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

[dimkadimon]

Interesting question: if I generate two random primes p1 and p2 then what is the most likely value for abs(p1-p2)?

-- 26.06.2013, 13:17 --

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

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

Уверен что такие есть, но их сложно найти. Хотя может Jarek уже нашёл...

[Nataly-Mak]

dimkadimon
Алгоритм Россера, заключающийся в превращении примитивного квадрата в пандиагональный, работает для N, являющихся простым числом (N>3).
Всё, сказанное выше о регулярных и нерегулярных пандиагональных квадратах, относится к квадратам такого порядка.

[В стаье Россера есть и другие примеры превращения примитивного квадрата в пандиагональный (для других порядков N), но только для классических квадратов.]

Я показала в своих работах, что этот алгоритм (превращение примитивного квадрата в пандиагональный) применим и к квадратам других порядков, но преобразование в некоторых случаях уже будет не таким, как у Россера (см. тему "Антимагические квадраты"). Или же должны быть наложены дополнительные условия для примитивного квадрата, например, ассоциативность. Из ассоциативных примитивных квадратов чётного порядка можно получать совершенные магические квадраты, а нечётного порядка - идеальные магические квадраты.

[Pavlovsky]

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

Хотя может Jarek уже нашёл...

Осмелюсь предположить, что нет. Поиск регулярных квадратов очень упрощает задачу. Но даже при таком допущении задача для больших N очень трудная. Поиск нерегулярных квадратов непосильная задача даже для N=7.

[Nataly-Mak]

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

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

Хотя может Jarek уже нашёл...

Осмелюсь предположить, что нет. Поиск регулярных квадратов очень упрощает задачу. Но даже при таком допущении задача для больших N очень трудная. Поиск нерегулярных квадратов непосильная задача даже для N=7.

Хе-х...
А я осмелюсь предположить, что нашёл. Его решение для N=13, скорее всего, уже нерегулярный пандиагональный квадрат, потому что примитивный квадрат 13-го порядка с таким маленьким индексом построить очень и очень трудно, может, даже невозможно.
Минимум J. K. Andersen - это индекс 1394767 (хотя он и не доказал, что этот индекс минимальный).
Jarek уменьшил это значение для магической константы пандиагонального квадрата почти в 70 раз!

[Pavlovsky]

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

Interesting question: if I generate two random primes p1 and p2 then what is the most likely value for abs(p1-p2)?

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

[dimkadimon]

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

Я показала в своих работах, что этот алгоритм (превращение примитивного квадрата в пандиагональный) применим и к квадратам других порядков, но преобразование в некоторых случаях уже будет не таким, как у Россера (см. тему "Антимагические квадраты"). Или же должны быть наложены дополнительные условия для примитивного квадрата, например, ассоциативность. Из ассоциативных примитивных квадратов можно получать совершенные магические квадраты.

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

[Nataly-Mak]

dimkadimon
я уже написала, что показала преобразования в теме "Антимагические квадраты".
Теперь присовокупила и ссылку на эту тему, если вы её ещё не нашли.
Квадраты Стенли, которые рассматриваются в указанной теме, есть не что иное, как примитивные квадраты по Россеру.

Кстати, ассоциативные квадраты Стенли строить намного проще, чем обычные (не ассоциативные).

-- Ср июн 26, 2013 09:15:11 --

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

Поиск нерегулярных квадратов непосильная задача даже для N=7.

Ничего непосильного
Берём общую формулу пандиагонального квадрата 7-го порядка, пишем программу и - впрерёд! Для кластеров - проще пареной репы
Сразу начинаем проверку для магических констант S<1597, естественно, с шагом 2, так как магические константы квадратов 7-го порядка из различных простых чисел могут быть только нечётными.

-- Ср июн 26, 2013 09:20:03 --

А между тем в театре магических действий уже видна реальная борьба

Цитата:

2 9.13 Wes Sampson La Jolla, California, United States 25 Jun 2013 14:19
3 9.09 Dmitry Kamenetsky Adelaide, Australia 26 Jun 2013 05:00

dimkadimon
опять улучшили N=13?

-- Ср июн 26, 2013 09:23:55 --

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

Interesting question: if I generate two random primes p1 and p2 then what is the most likely value for abs(p1-p2)?

Если я правильно поняла ваш вопрос, вас интересует структура примитивного квадрата.
Посмотрите эту головоломку:
http://www.primepuzzles.net/puzzles/puzz_682.htm
(автор головоломки Jarek Wroblewski; опубликовано сразу после моей головоломки о квадратах Стенли - #681).

[dimkadimon]

Nataly-Mak

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

1 2 101 103 202 203
4 5 104 106 205 206
7 8 107 109 208 209
13 14 113 115 214 215
16 17 116 118 217 218
19 20 119 121 220 221

С помощью преобразования превращаю этот ассоциативный квадрат Стенли в совершенный магический квадрат:

1 220 103 19 202 121
218 5 116 206 17 104
13 208 115 7 214 109
203 20 101 221 2 119
16 205 118 4 217 106
215 8 113 209 14 107