2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 47, 48, 49, 50, 51, 52, 53 ... 67  След.
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение02.09.2013, 12:28 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Первое точное покрытие Массива №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).

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение02.09.2013, 13:36 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Вспомнила, что я умею строить обычные МК :D
Построила такой МК из чисел Массива №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 простое, то наибольшее число этой диагонали можно поместить в правый нижний угол.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение02.09.2013, 14:33 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #759849 писал(а):
Надо доказать гипотезу, которую выдвинул whitefox: любой набор из 4-х попарно ортогональных точных покрытий массива из 49 чисел даёт пандиагональный квадрат.


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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение02.09.2013, 17:32 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
А вы не бойтесь, докажите, что неверна :-)

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение02.09.2013, 18:13 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение02.09.2013, 18:21 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение02.09.2013, 19:20 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Pavlovsky
Pavlovsky в сообщении #759783 писал(а):
Поделитесь пожалуйста превдарительными результатами своих исследований. Насколько вероятно найти решение 733 для N=7, за реальное время?

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

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

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

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

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

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

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

Pavlovsky в сообщении #759866 писал(а):
Боюсь, что эта гипотеза неверна.

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

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

(Nataly-Mak)

Nataly-Mak в сообщении #759784 писал(а):
whitefox
вся надежда на вас :wink:
Я пока не писала программу для создания покрытий, а надо бы.

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение02.09.2013, 19:45 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #759944 писал(а):
Если что-то не ясно в уже изложенном, спросите. Постараюсь пояснить.

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

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

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

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение02.09.2013, 19:59 
Заслуженный участник
Аватара пользователя


19/12/10
1546
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 писал(а):
А я, между прочим, спросила. Мои вопросы не столь важны?

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение02.09.2013, 20:10 


02/11/12
141
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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение02.09.2013, 20:54 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
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-го порядка из различных простых чисел; думаю, что одновременно два человека не могли ошибиться).

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение02.09.2013, 22:06 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Пример решения $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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение03.09.2013, 08:10 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Пытаюсь освоить процедуру построения пандиагонального квадрата 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

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

Изображение

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение03.09.2013, 09:32 
Заблокирован
Аватара пользователя


22/03/08

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

Изображение

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение03.09.2013, 10:23 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #759849 писал(а):
Надо доказать гипотезу, которую выдвинул whitefox: любой набор из 4-х попарно ортогональных точных покрытий массива из 49 чисел даёт пандиагональный квадрат.

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 47, 48, 49, 50, 51, 52, 53 ... 67  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group