Н. Макарова

 

ЕЩЁ РАЗ ОБ АЛГОРИТМЕ РОССЕРА

 

 

Утомившись от решения задачи построения наименьшего пандиагонального квадрата 6-го порядка из чисел Смита (об этой задаче хочу написать отдельную статью), решила отвлечься от неё и вернулась к замечательному алгоритму Россера для построения пандиагональных квадратов простых порядков с помощью примитивного квадрата. Напомню, что в проработке этого алгоритма и вообще всей статьи Россера [1] сыграл огромную роль В. Павловский. Он первый разобрал этот алгоритм и изложил его на форуме Портала ЕН [2]. Начинал он с самого меньшего порядка – 5. Им был найден наименьший пандиагональный квадрат данного порядка из простых чисел, построенный с применением алгоритма Россера. Это был замечательный результат! Дальше мы уже сообща начали изучать этот алгоритм и всю теорию Россера о дьявольских квадратах. К нам подключился С. Беляев. Ему удалось разработать замечательный алгоритм построения пандиагональных квадратов 6-го порядка (алгоритм изложен на форуме dxdy.ru). Для данного порядка в статье Россера нет алгоритма построения. И ещё в статье Россера нет алгоритма построения нетрадиционных пандиагональных квадратов 9-го порядка. Такие алгоритмы разработаны мной.

Всё это подробно описано в статьях цикла «Нетрадиционные пандиагональные квадраты».

 

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

 

На форуме dxdy.ru В. Павловский опубликовал последовательность пандиагональных квадратов 5-го порядка из простых чисел ([3]). Вот фрагмент этой последовательности:

 

395 = 5 7 11 13 17 23 31 37 41 43 53 67 71 73 83 97 101 103 113 127 131 137 167 197 227
403 = 7 13 17 19 23 29 31 37 41 43 47 53 61 67 73 103 113 127 137 139 149 157 163 173 193
409 = 5 7 11 13 29 31 41 43 47 53 59 61 71 73 79 83 97 101 109 127 157 163 181 193 211
413 = 5 11 23 29 31 37 41 47 53 59 67 71 73 79 83 89 97 109 113 131 139 149 157 173 199
419 = 5 13 19 23 29 31 37 47 53 59 67 71 73 83 89 97 103 107 113 137 149 157 163 173 197
425 = 5 7 11 13 17 23 41 43 53 61 67 71 73 83 97 101 103 113 127 131 137 157 167 197 227
431 = 5 7 11 13 17 19 31 37 41 43 47 53 71 73 97 101 103 107 127 137 167 173 179 233 263
433 = 11 13 17 19 31 37 41 43 53 59 61 67 73 83 97 107 109 127 137 139 149 157 163 179 193
437 = 7 11 13 17 23 29 37 41 43 47 53 59 67 73 97 101 103 107 131 137 163 167 179 223 257
441 = 5 11 23 29 31 37 41 47 53 59 67 71 83 89 97 101 107 113 131 137 149 157 167 173 227

.  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  

 

567 = 5 11 17 23 37 41 43 47 53 59 71 73 79 83 103 131 137 167 173 197 227 233 263 269 293
569 = 11 13 17 19 41 43 53 59 67 73 83 97 107 109 137 139 149 163 167 173 179 193 197 263 293
571 = 11 13 19 29 31 37 59 61 67 71 73 79 89 101 103 107 109 137 149 179 223 241 271 283 313
573 = 11 17 23 29 31 41 43 47 53 59 61 71 73 83 101 113 131 137 151 191 239 251 269 281 359
575 = 11 17 23 29 31 41 43 47 61 67 71 79 83 97 101 107 113 127 163 167 251 257 271 307 311
577 = 11 17 23 29 37 41 43 53 67 73 79 101 103 113 127 151 157 163 167 179 181 193 229 241 307
581 = 11 13 17 19 23 29 41 47 59 61 71 89 101 103 113 131 137 139 149 167 223 229 271 313 349

 

 

Первое число – это магическая константа квадрата, далее следует массив чисел, из которых составлен квадрат. Собственно самих квадратов здесь нет, их надо составить из данного массива чисел. Но составить квадрат из заданного массива, состоящего из 25 чисел, совсем просто, можно воспользоваться и общей формулой пандиагонального квадрата 5-го порядка.  Сложность задачи как раз в нахождении таких массивов, из которых пандиагональный квадрат составляется.

 

Интересно отметить, что у Павловского нет ни одного квадрата, содержащего число 3. Мне удалось построить пандиагональные квадраты, содержащие число 3. Покажу несколько таких квадратов.

 

S = 523

 

3  283  163  31  43

            127  13  41  269  73

            307  59  37  109  11

            19  107  277  97  23

            67  61  5  17  373

 

S = 547

 

3  211  193  31  109

            157  13  107  173  97

            277  59  61  139  11

            43  137  181  163  23

 67  127  5  41  307

 

S = 607

 

3  271  193  31  109

            157  13  107  233  97

            337  59  61  139  11

            43  137  241  163  23

            67  127  5  41  367

 

                        S = 613

 

3  373  163  31  43

            127  13  41  359  73

            397  59  37  109  11

 19  107  367  97  23

 67  61  5  17  463

 

                        S = 619

 

3  103  337  37  139

            307  13  137  89  73

            223  59  43  283  11

            19  281  97  193  29

            67  163  5  17  367

 

                        S = 637

 

3  127  337  31  139

            331  13  137  89  67

            223  29  61  313  11

            43  311  97  163  23

            37  157  5  41  397

 

                        S = 643

 

3  103  397  31  109

            367  13  107  89  67

            193  53  37  349  11

            19  347  97  157  23

            61  127  5  17  433

 

                        S = 817

 

3  103  571  31  109

            541  13  107  89  67

            193  53  37  523  11

            19  521  97  157  23

            61  127  5  17  607

 

S = 823

 

3  283  397  31  109

367  13  107  269  67

            373  53  37  349  11

            19  347  277  157  23

61  127  5  17  613

 

                        S = 853

 

3  103  577  31  139

            541  13  137  89  73

            223  59  37  523  11

            19  521  97  193  23

            67  157  5  17  607

 

Павловский утверждает в сообщении на форуме, что для любой нечётной магической константы S>581 пандиагональный квадрат 5-го порядка из простых чисел существует. Однако это утверждение не доказано.

 

Завершая рассказ о построении пандиагональных квадратов 5-го порядка, покажу матричное преобразование, которое эквивалентно преобразованию Россера. Мне всегда удобнее пользоваться матричным преобразованием, поэтому я сочинила такие преобразования для построения пандиагональных квадратов всех порядков с использованием примитивных квадратов. На рис. 1 вы видите матрицу примитивного квадрата A(a_ij).

 

 

Рис. 1

 

На рис. 2 показана матрица пандиагонального квадрата, полученного из данного примитивного квадрата преобразованием Россера.

 

 

Рис. 2. Преобразование, превращающее примитивный квадрат 5х5 в пандиагональный

 

Пример.

Пусть мы имеем такой примитивный квадрат (рис. 3):

 

 

Рис. 3. Примитивный квадрат

 

Применим к этому примитивному квадрату матричное преобразование, показанное на рис. 2. Получим следующий пандиагональный квадрат (рис. 4):

 

 

Рис. 4. Пандиагональный квадрат

 

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

 

 

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

 

Эти квадраты не эквивалентны.

 

В программу построения примитивного квадрата 5-го порядка сразу вставляю преобразование в матричной форме, превращающее примитивный квадрат в пандиагональный, и программа выдаёт готовые пандиагональные квадраты. Очень удобно пользоваться матричным преобразованием.

 

Попробовала по новой программе искать четыре пандиагональных квадрата 5-го порядка с одинаковой магической константой, но составленные из различных чисел (нет одинаковых чисел во всех четырёх квадратах). Это нужно для построения пандиагонального квадрата 10-го порядка с помощью решётки Россера. Но об этом подробно расскажу в части статьи «Нетрадиционные пандиагональные квадраты», посвящённой квадратам 10-го порядка (она у меня уже давно на очереди).

Лучший результат пока достигнут Павловским, он построил этим методом пандиагональный квадрат 10-го порядка с магической константой 3594. Для этого были найдены четыре пандиагональных квадрата 5-го порядка с магической константой 1797.

 

Теперь перехожу к квадратам 7-го порядка. Здесь всё совершенно аналогично. Однако есть очень важный момент. Если для порядка 5, пользуясь методом Россера, мы не теряем пандиагональные квадраты, то для порядка 7 всё иначе. С помощью примитивных квадратов мы строим только регулярные пандиагональные квадраты 7-го порядка. Нерегулярные пандиагональные квадраты остаются вне пространства пандиагональных квадратов, получаемых из примитивных квадратов. Но огромное преимущество применения примитивных квадратов в том, что они позволяют уменьшить количество свободных переменных в два раза, в общей формуле пандиагонального квадрата 7-го порядка 24 свободных переменных (при заданной магической константе), в алгоритме Россера (применение примитивного квадрата) всего 12 свободных переменных. Понятно, что это даёт колоссальный выигрыш во времени выполнения программы.

 

Этим методом было построено немало пандиагональных квадратов 7-го порядка. Первые такие квадраты построил С. Беляев. Его наименьший квадрат имел магическую константу 1895. Затем Павловский улучшил этот результат, построив квадрат с магической константой 1649 (рис. 6).

 

 

Рис. 6. Пандиагональный квадрат В. Павловского

 

Мне удалось по новой программе построить пандиагональный квадрат с магической константой 1597 (рис. 7).

 

 

Рис. 7. Наименьший пандиагональный квадрат 7-го порядка из простых чисел

 

На рис. 8 показан соответствующий этому пандиагональному квадрату примитивный квадрат.

 

 

Рис. 8. Примитивный квадрат

 

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

 

Точно так же я составила для превращения примитивных квадратов 7х7 в пандиагональные квадраты матричное преобразование, смотрите рис. 9.

 

 

Рис. 9. Преобразование, превращающее примитивный квадрат 7х7 в пандиагональный

 

Здесь тоже интересна задача поиска четырёх пандиагональных квадратов 7-го порядка с одинаковой магической константой, составленных из разных чисел. Из таких квадратов можно построить пандиагональный квадрат 14-го порядка по решётке Россера. Я пока не решала эту задачу.

 

Далее этим же методом мне удалось построить пандиагональные квадраты 11-го и 13-го порядков из простых чисел, но об этом расскажу в следующих статьях цикла «Нетрадиционные пандиагональные квадраты». Построить примитивные квадраты из простых чисел для данных порядков не просто, в отличие от примитивных квадратов порядков 5, 7.

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

 

Наименьшим пандиагональным квадратам из простых чисел посвящена статья OEIS A179440 [4].

 

 

Литература и Веб-сайты

 

 

[1] THE ALGEBRAIC THEORY OF DIABOLIC MAGIG SQUARES. By Barkley Rosser and R. J. Walker

http://narod.ru/disk/23700701000/Rosser1939.rar.html

Примечание: статья переведена на русский язык С. В. Беляевым. Перевод здесь: http://svb.hut.ru/DOWN/Rosser_ru.pdf

[2] Форум Портала ЕН. http://e-science.ru/forum/index.php?showtopic=20405&st=20

[3] Научный форум dxdy.ru. http://dxdy.ru/topic12959.html

[4] Статья в OEIS. https://oeis.org/A179440

 

 

22 апреля 2011 г.

г. Саратов

 

 

На главную страницу:

http://www.klassikpoez.narod.ru/index.htm

 

Пишите мне: natalimak1@yandex.ru