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

[Nataly-Mak]

Первое точное покрытие Массива №2 сочинила:

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

Итак, если пандиагональный квадрат 7-го порядка из различных простых чисел, собранных в Массиве №2, существует, то он может иметь, к примеру, такие строки:

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

Строки как строки хотя последняя строка мне не очень нравится.
А вот теперь задача потруднее: надо найти второе точное покрытие Массива №2 ортогональное уже найденному покрытию. Это покрытие будет того же вида (0 1 4 0 2).

[Ну, как писал whitefox, два ортогональных покрытия для квадрата 7-го порядка по программе находятся мгновенно. Значит, это ещё лёгкая задача.]

Дальше совсем сложно: найти ещё два покрытия так, чтобы все 4 покрытия были попарно ортгональны. Последние два покрытия будут вида (0 0 5 1 1).

[Nataly-Mak]

Вспомнила, что я умею строить обычные МК
Построила такой МК из чисел Массива №2.
И вот имеем два ортогональных покрытия Массива №2:

Строки - покрытие вида (0 0 5 1 1)
127 13  31  101 227 229 5   
67  211 157 197 7   71  23  
131 193 83  11  113 29  173 
179 3   103 191 107 41  109 
59  79  149 97  43  139 167 
19  53  73  89  199 61  239 
151 181 137 47  37  163 17  

Столбцы - покрытие вида (0 1 4 0 2)
151  19  59  179  131  67  127 
 181  53  79  3  193  211  13 
 137  73  149  103  83  157  31 
 47  89  97  191  11  197  101 
 37  199  43  107  113  7  227 
 163  61  139  41  29  71  229 
 17  239  167  109  173  23  5

А покрытия-то получились нужного вида. Это очень интересно!
Но в магическом квадрате ещё и главные диагонали тоже годные цепочки, имеем по одной цепочке в последних двух покрытиях:

127 211 83 191 43 61 17

(цепочка вида 3)
и

151 53 149 191 113 71 5

(цепочка вида 5)
Ну и вот. Есть два ортогональных покрытия и по одной цепочке в двух последних покрытиях. Всё правильное и всё нужного вида.
Осталось найти по 6 недостающих цепочек в последних двух покрытиях с соблюдением всех условий. Но это непростая задача.

Как писать программу нахождения набора из 4-х попарно ортогональных покрытий, пока не придумала

-- Пн сен 02, 2013 15:15:39 --

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

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

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

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

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

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

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

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

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

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

Вот этот алгоритм превращения 4-х попарно ортогональных покрытий в пандиагональный квадрат хочу рассмотреть внимательнее.

Надо доказать гипотезу, которую выдвинул whitefox: любой набор из 4-х попарно ортогональных точных покрытий массива из 49 чисел даёт пандиагональный квадрат.

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

whitefox
мне непонятно, почему:

Цитата:

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

[Pavlovsky]

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

Надо доказать гипотезу, которую выдвинул whitefox: любой набор из 4-х попарно ортогональных точных покрытий массива из 49 чисел даёт пандиагональный квадрат.

Боюсь, что эта гипотеза неверна.

[Nataly-Mak]

А вы не бойтесь, докажите, что неверна

Надеюсь, все понимают важность этой гипотезы.
Другими словами это выглядит так: чтобы пандиагональный квадрат 7-го порядка из заданного массива, состоящего из 49 чисел, существовал, необходимо существование набора из 4 точных попарно ортогональных покрытий этого массива.
Является ли это условие достаточным?
Если является, тогда достаточно найти один набор из 4-х точных попарно ортогональных покрытий данного массива - и пандиагональный квадрат будет у нас в кармане.

Pavlovsky
для опровержения гипотезы достаточно привести всего один контрпример.
Дайте пример набора из 4 точных попарно ортогональных покрытий Массива №2 (или Массива №1), из которых пандиагональный квадрат 7-го порядка сделать невозможно.

[Pavlovsky]

Давайте сначала построим хотя бы один набор 4-х ортогональных разбиений. А там будем решать можно ли из него построить пандиагональный квадрат.

[Nataly-Mak]

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

А набор из 4-х точных попарно ортогональных покрытий я вам могу привести, разумеется, для другого массива. Сможете сделать из него пандиагональный квадрат?
Как верно заметил whitefox, надо проследить за выполненнием изложенного им алгоритма до конца. Для начала надо понять этот алгоритм во всех деталях. Я вот задала вопрос об одном непонятном мне моменте, жду ответа.

Кстати, что там у Россера по этому поводу есть? Ведь набор из 4-х точных попарно ортогональных покрытий массива - это по Россеру 4 пути (строки, столбцы, диагонали, 'диагонали').

[whitefox]

Pavlovsky

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

Поделитесь пожалуйста превдарительными результатами своих исследований. Насколько вероятно найти решение 733 для N=7, за реальное время?

(забавная очепятка)

превдарительными -- превосходные дарительные?

Ваши очепятки всегда талантливы
Вы их специально придумываете? :-)

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

Если что-то не ясно в уже изложенном, спросите. Постараюсь пояснить.

Имхо, 100% вероятность найти решение N7S733, либо доказать его отсутствие за реальное время. ( Ещё раз -- имхо, имхо, имхо . . . )

-- 02 сен 2013, 20:25 --

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

Боюсь, что эта гипотеза неверна.

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

-- 02 сен 2013, 20:29 --

(Nataly-Mak)

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

whitefox
вся надежда на вас
Я пока не писала программу для создания покрытий, а надо бы.

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

[Nataly-Mak]

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

Если что-то не ясно в уже изложенном, спросите. Постараюсь пояснить.

А я, между прочим, спросила. Мои вопросы не столь важны?

Цитата:

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

Я начала, и кое-что сделала:
1. нашла все шаблоны из вычетов по модулю 6;
2. сделала разбиение обоих массивов на 5 подбаз. Кстати, выложила разбиение для Массива №2, да только оно никому не нужно, судя по тому, что его никто не скачал.
3. Научилась мгновенно находить пару ортогональных точных покрытий массива.
4. Попыталась разобрать ваш алгоритм превращения набора из 4-х точных попарно ортогональных покрытий массива в пандиагональный квадрат. Задала вопрос, ответ на который не получила.

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

P.S. Разрешаю вам не читать больше мои длинные сообщения и с полным правом (по разрешению) игнорировать все мои вопросы. Обещаю делать то же самое.

[whitefox]

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

whitefox
мне непонятно, почему:

Цитата:

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

Россер доказал, что одним из изоморфных преобразований пандиагонального квадрата является умножение по модулю N индексов всех элементов квадрата на число взаимнопростое с N.
Таких чисел $\varphi(\mathrm N)$.
Если $\mathrm N$ простое, то $\varphi(\mathrm N)=\mathrm N-1$.

Будем нумеровать строки и столбцы с нуля, тогда элементы главной диагонали имеют индексы {00, 11, 22, . . . , (N-1)(N-1)}. При умножении по модулю N этих индексов на любое число взаинопростое с N, элементы главной диагонали будут переставлены (кроме элемента с индексом 00).
Пусть наибольший элемент главной диагонали имеет индекс $\mathrm{QQ}$ (по условию, наименьший элемент главной диагонали имеет индекс 00), при $\mathrm N$ простом найдётся такое число $\mathrm K$ взаимнопростое с $\mathrm N$, что $\mathrm Q\cdot \mathrm K\equiv \mathrm N-1\pmod{\mathrm N}$.

-- 02 сен 2013, 21:01 --

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

А я, между прочим, спросила. Мои вопросы не столь важны?

Пока я писал ответ лично Вам, Вы успели обидеться.
А на что?
Что не ответил Вам первой?
Но ответ на Ваш вопрос пространнее прочих, и требовал обдумывания.

[mertz]

Last version. You can select the number of holes (faults) you want to see. Removed extra messages going to log. I will release the Visual Studio project and a Linux project soon.

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

[Nataly-Mak]

mertz
спасибо за новую версию программы; скачала, запустила поиск решения S=733. Решение с 3 дырками нашлось за несколько секунд. Решений с 2 и с 1 дыркой пока нет.
Очень хорошо, что вы сделали поиск для магической константы 733; это оптимальное решение, надо именно с него начинать поиск, я так считаю.

-- Пн сен 02, 2013 22:12:39 --

mertz в сообщении #759545 писал(а):

Jarek's "primes" are not primes. It is a list of numbers that I can not explain. I do not understand any of the work you are doing. I am just taking his program and playing with it.

mertz
вы можете показать этот список здесь?

Очень важно уменьшить массив чисел, которые участвуют в построении квадрата.
Сейчас я снова вижу в решении число 283, которое не может содержаться в решении с магической константой 733.

Что даёт нам такой поиск решений, в которых есть не только ошибки, но и запрещённые (слишком большие) простые числа? Это напрасная трата времени.
Надо задать в программе массив из 51 числа, который я привела выше. Тогда программа будет искать реальные решения или близкие к реальным.

Повторю объединённый массив простых чисел для поиска решения $S=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 223 227 229 233 239

Это всё! Больше никакие простые числа в решении с магической константой 733 присутствовать не могут (если ни я, ни whitefox не ошиблись в том, что существует только два массива простых из 49 чисел, пригодных для построения пандиагонального квадрата 7-го порядка из различных простых чисел; думаю, что одновременно два человека не могли ошибиться).

[Nataly-Mak]

Пример решения $S=733$, найденный по моей программе

В решении 7 дырок, зато нет чисел больше максимального числа массива 239.

73  201*  109  61  167  119*  3 
101  17  173  5  191  89  157 
211  147*  137  53  31  27*  127 
43  71  27*  199  183*  197  13 
131  11  149  179  29  41  193 
151  239  67  7  113  97  59 
23  47  71*  229  19  163  181 

Наконец-то у меня получилось решение без отрицательных чисел, что тоже хорошо.

[Nataly-Mak]

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

Вот такой набор прокрытий:

№1 - строки

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

№2 - столбцы

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

№3 - вторые диагонали

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

№4 - первые диагонали

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

Массив:

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  197  199  223  227  241  251  311

На мой взгляд всё должно определяться одной главной диагональю. Только вот как расположить элементы в этой диагонали - надо определять перебором. Перебор будет небольшой, минимальный элемент в диагонали можно зафиксировать (имеем право это сделать, так как квадрат пандиагональный). Для перебора остаётся 720 вариантов (все перестановки из 6 элементов).
Я пока не делала перебор, а расположила элементы в первой главной диагонали так, как они расположены в готовом решении (решение мне известно, из него я и сделала покрытия):

3 181 251 163 67 83 7

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



Думаю, что и дальше всё должно определиться однозначно.

[Nataly-Mak]

Продолжила заполнение вручную визуально, вот что получилось:



Да, уже очевидно, что всё это заполняется однозначно и до конца.

Так как же всё-таки: может ли набор из 4-х точных попарно ортогональных покрытий массива из 49 различных чисел
не превратиться в пандиагональный квадрат

[Pavlovsky]

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

Надо доказать гипотезу, которую выдвинул whitefox: любой набор из 4-х попарно ортогональных точных покрытий массива из 49 чисел даёт пандиагональный квадрат.

Задача имеет очень забавную интерепретацию из раздела конечные геометрии. Может кого из теоретиков заинтересует такая постановка?

Дано: Конечная геометрия, в которой $N^2$ точек и 4N прямых. Через каждую точку проходит ровно 4 прямых. На каждой прямой лежит ровно N точек. Прямые можно разбить на 4 класса паралельных прямых по N прямых в каждом классе. Естественно выполняются аксиомы:
П1 Паралельные прямые не пересекаются.
П2 Непаралельные прямые пересекаются ровно в одной точке.

Необходимо: Сформулировать дополнительное условие (аксиому) гарантирующее укладку вышеописанной геометрии на торе.