Макарова Н.

 

 

НАИМЕНЬШИЕ МАГИЧЕСКИЕ КВАДРАТЫ ИЗ ПРОСТЫХ ЧИСЕЛ

 

Часть I

 

Данная страница является продолжением страниц:

 

http://www.natalimak1.narod.ru/netrpr.htm

http://www.natalimak1.narod.ru/netrpr1.htm

http://www.natalimak1.narod.ru/netrpr2.htm

 

 

Здесь будет рассмотрено построение наименьших магических квадратов из простых чисел в классическом определении, то есть без использования числа 1. Такие магические квадраты порядков 3 и 4 известны давно. Наименьший магический квадрат 5-го порядка был построен недавно, о чём автор квадрата А. Лелеченко сообщил на форуме dxdy.ru. Всё это уже было рассказано в указанных выше статьях. Мне предстоит начать с построения наименьшего магического квадрата из простых чисел 6-го порядка.

 

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

В центр матрицы 6х6 помещён наименьший магический квадрат 4-го порядка из простых чисел в классическом определении, а элементы окаймления – неизвестные величины (рис. 1).

 

 

Рис. 1

 

Обозначим сумму двух противолежащих элементов (в строках, в столбцах и в главных диагоналях квадрата) S. Записав условия магичности квадрата 6х6, получим следующую систему уравнений:

 

x₁ + x₂ + x₃ + x₄ + x₅ + x₆ = S + 120

x₁ + x₂₀ + x₁₉ + x₁₈ + x₁₇ + x₁₆ = S + 120

x₆ + x₇ + x₈ + x₉ + x₁₀ + x₁₁ = S + 120

x₁₁ + x₁₂ + x₁₃ + x₁₄ + x₁₅ + x₁₆ = S + 120

x₂ + x₁₅ = S

x₃ + x₁₄ = S

x₄ + x₁₃ = S

x₅ + x₁₂ = S

x₇ + x₂₀ = S

x₈ + x₁₉ = S

x₉ + x₁₈ = S

x₁₀ + x₁₇ = S

x₁ + x₁₁ = S

x₆ + x₁₆ = S

 

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

 

   

 

Рис. 2

 

Я задала другие значения для свободных переменных и получила такое решение системы:

 

x₁₀ = 1, x₁₁ = 2, x₁₂ = 4, x₁₃ = 6, x₁₄ = 8, x₁₈ = 9, x₁₉ = 10, x₂₀ =12

x₁ = 58, x₂ = -68, x₃ = 52, x₄ = 54, x₅ = 56, x₆ = 28, x₇ = 48, x₈ = 50, x₉ = 51,

x₁₅ = 128, x₁₆ = 32, x₁₇ = 59

 

Магический квадрат, соответствующий этому решению, изображён на рис. 3.

 

 

Рис. 3

 

Чтобы избавиться от отрицательного элемента -68, увеличим все элементы квадрата на 69. В результате получим магический квадрат, изображённый на рис. 4.

 

 

Рис. 4

 

Вряд ли возможно решить полученную систему уравнений в простых числах. Следовательно, данный алгоритм не привёл к решению поставленной задачи, но дал интересный метод построения нетрадиционных окаймлённых магических квадратов 6-го порядка.

 

После неудачи с приведённым алгоритмом я вспомнила про свой давнишний алгоритм построения традиционных магических квадратов 6-го порядка. Этот алгоритм я реализовала ещё на старой ЭВМ. Программа прекрасно строила традиционные магические квадраты 6-го порядка. Алгоритм был такой: с помощью функции случайных чисел формируется набор из 6 строк, состоящих из различных чисел, так что сумма чисел в каждой строке равна 111. Понятно, что числа эти выбираются случайным образом из массива первых 36 натуральных чисел. Получив такой набор, программа выполнила первый этап и переходит ко второму этапу: пытается превратить данный набор из 6 строк в полумагический квадрат, то есть добиться того, чтобы суммы чисел в столбцах тоже были равны 111 (это достигается путём перестановки чисел в строках). Этот этап выполним не для любого набора из 6 строк. Если же полумагический квадрат получить удаётся, программа переходит к третьему этапу: пытается превратить полумагический квадрат в магический, то есть добиться того, чтобы суммы чисел в главных диагоналях квадрата тоже были равны 111. Этот этап тоже не всегда выполним. Но если он выполнен, то магический квадрат построен. Покажу один из традиционных магических квадратов 6-го порядка, построенный по этой программе ещё на старой ЭВМ (рис. 5):

 

 

Рис. 5

 

Я решила применить этот алгоритм для построения нетрадиционного наименьшего магического квадрата 6-го порядка из простых чисел. О возможной минимальной магической константе такого квадрата я уже писала, она равна 432. Выбрала массив из 36 простых чисел, так чтобы сумма чисел в этом массиве была равна 432 * 6 = 2592. Вот этот массив:

 

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, 167

 

Далее из чисел данного массива сгенерированы все строки по 6 чисел, так что сумма чисел в строке равна 432. На следующем этапе сформированы наборы по 6 строк, так что все числа в этом наборе различны. Нашла пять нужных наборов по 6 строк. Вот эти наборы:

 

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

 

3 13 19 109 139 149              3 19 61 109 113 127

5 7 23 79 151 167                  5 7 13 89 151 167

11 17 29 107 131 137            11 17 29 107 131 137

31 37 41 83 113 127              23 31 37 53 139 149

43 47 67 71 101 103              41 43 47 97 101 103

53 59 61 73 89 97                  59 67 71 73 79 83

 

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

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

 

 

Рис. 6

 

Ещё удалось превратить в магический квадрат четвёртый набор, получено даже два неэквивалентных варианта. Остальные три набора не дали магических квадратов. На рис. 7 – 8 вы видите два магических квадрата, полученных из четвёртого набора.

 

 

Рис. 7

 

 

Рис. 8

 

Для квадрата, изображённого на рис. 6, покажу 23 варианта, полученные с помощью М-преобразований. Как известно, любой магический квадрат 6-го порядка образует группу из 24 магических квадратов (считая его самого) эквивалентных относительно М-преобразований. Характерной особенностью всех квадратов такой группы является одинаковый набор чисел в строках, в столбцах и в обеих главных диагоналях квадратов. Показываю всю группу полностью, как она записана программой в файл, в том числе и базовый квадрат с рис. 6 (вариант № 1).

 

№ 1                                        № 2                                       № 3                                        № 4

3  5  47  109  131  137            3  5  109  47  131  137          3  47  5  131  109  137           3  47  131  5  109  137

            89  73  53  97  61  59            89  73  97  53  61  59             151  83  167  11  7  13           151  83  11  167  7  13    

            151  167  83  7  11  13           71  41  103  107  67  43        89  53  73  61  97  59             17  29  139  19  79  149

            71  41  107  103  67  43         151  167  7  83  11  13          17  29  19  139  79  149         89  53  61  73  97  59

            17  19  29  79  139  149         17  19  79  29  139  149        71  107  41  67  103  43         71  107  67  41  103  43    

            101  127  113  37  23  31       101  127  37  113  23  31      101  113  127  23  37  31       101  113  23  127  37  31    

 

№ 5                                        № 6                                        № 7                                        № 8    

 3  109  5  131  47  137          3  109  131  5  47  137            3  131  47  109  5  137          3  131  109  47  5  137

            71  103  41  67  107  43         71  103  67  41  107  43         17  139  29  79  19  149         17  139  79  29  19  149    

            89  97  73  61  53  59             17  79  139  19  29  149         151  11  83  7  167  13           71  67  103  107  41  43    

            17  79  19  139  29  149         89  97  61  73  53  59             71  67  107  103  41  43         151  11  7  83  167  13    

            151  7  167  11  83  13           151  7  11  167  83  13           89  61  53  97  73  59             89  61  97  53  73  59    

            101  37  127  23  113  31       101  37  23  127  113  31       101  23  113  37  127  31       101  23  37  113  127  31    

 

№ 9                                        № 10                                      № 11                                      № 12

 73  89  53  97  59  61            73  89  97  53  59  61            73  53  89  59  97  61             73  53  59  89  97  61

            5  3  47  109  137  131           5  3  109  47  137  131           167  83  151  13  7  11           167  83  13  151  7  11    

            167  151  83  7  13  11           41  71  103  107  43  67         5  47  3  137  109  131           127  113  31  101  37  23

            41  71  107  103  43  67         167  151  7  83  13  11           127  113  101  31  37  23       5  47  137  3  109  131    

            127  101  113  37  31  23       127  101  37  113  31  23       41  107  71  43  103  67         41  107  43  71  103  67

            19  17  29  79  149  139         19  17  79  29  149  139         19  29  17  149  79  139         19  29  149  17  79  139

 

№ 13                                      № 14                                      № 15                                      № 16

 73  97  89  59  53  61            73  97  59  89  53  61            73  59  53  97  89  61             73  59  97  53  89  61

            41  103  71  43  107  67         41  103  43  71  107  67        127  31  113  37  101  23       127  31  37  113  101  23

            5  109  3  137  47  131           127  37  31  101  113  23       167  13  83  7  151  11           41  43  103  107  71  67

            127  37  101  31  113  23       5  109  137  3  47  131           41  43  107  103  71  67         167  13  7  83  151  11   

            167  7  151  13  83  11           167  7  13  151  83  11           5  137  47  109  3  131           5  137  109  47  3  131

            19  79  17  149  29  139         19  79  149  17  29  139         19  149  29  79  17  139         19  149  79  29  17  139

 

№ 17                                      № 18                                      № 19                                      № 20

            83  151  167  11  13  7           83  151  11  167  13  7           83  167  151  13  11  7           83  167  13  151  11  7

            47  3  5  131  137  109           47  3  131  5  137  109           53  73  89  59  61  97             53  73  59  89  61  97

            53  89  73  61  59  97             29  17  139  19  149  79         47  5  3  137  131  109           113  127  31  101  23  37    

            29  17  19  139  149  79         53  89  61  73  59  97             113  127  101  31  23  37       47  5  137  3  131  109

            113  101  127  23  31  37       113  101  23  127  31  37       29  19  17  149  139  79         29  19  149  17  139  79   

            107  71  41  67  43  103         107  71  67  41  43  103         107  41  71  43  67  103         107  41  43  71  67  103

 

 

№ 21                                      № 22                                      № 23                                      № 24                          

            83  11  151  13  167  7           83  11  13  151  167  7          83  13  167  11  151  7           83  13  11  167  151  7

            29  139  17  149  19  79         29  139  149  17  19  79        113  31  127  23  101  37       113  31  23  127  101  37

            47  131  3  137  5  109           113  23  31  101  127  37       53  59  73  61  89  97             29  149  139  19  17  79    

            113  23  101  31  127  37       47  131  137  3  5  109           29  149  19  139  17  79         53  59  61  73  89  97

            53  61  89  59  73  97             53  61  59  89  73  97             47  137  5  131  3  109           47  137  131  5  3  109  

            107  67  71  43  41  103         107  67  43  71  41  103         107  43  41  67  71  103         107  43  67  41  71  103

 

В свою очередь, каждый квадрат этой группы порождает группу из 8 квадратов (включая его самого) эквивалентных относительно основных преобразований. Следовательно, квадрат с рис. 6 имеет 192 варианта эквивалентных относительно основных преобразований и М-преобразований. То же самое можно сказать и о квадратах с рис. 7 – 8.

 

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

http://www.research.att.com/~njas/sequences/A164843

 

Приведу фрагмент из этой статьи (рис. 9):

 

 

Рис. 9

 

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

 

***

 

Теперь переходим к построению наименьшего магического квадрата 7-го порядка. Алгоритм тот же самый.

Если сложить первые 49 простых чисел, начиная с числа 3, получится сумма равная 5115. Следовательно, минимальная магическая константа квадрата 7-го порядка из простых чисел в классическом определении не может быть меньше 731. Это ориентир в решении поставленной задачи.

Мне удалось сформировать массив из 49 простых чисел с суммой чисел равной 5131. Эта сумма кратна 7 и числа данного массива, вероятно, могут составить магический квадрат 7-го порядка с константой равной 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, 233, 239.

 

При построении квадрата 7-го порядка я не стала генерировать все строки из чисел данного массива с суммой чисел в строке, равной 733, потому что таких строк получается очень много и обработка полученного массива строк затруднительна. Я придумала хитрый ход: сразу стала генерировать нужный набор из 7 строк, используя функцию случайных чисел. Такой набор для порядка 7 генерируется за несколько секунд. И первый же набор превратился в магический квадрат. Сначала показываю сгенерированный набор из 7 строк, сумма в каждой строке набора равна 733, все числа набора различны (то есть в наборе содержатся все 49 чисел показанного выше массива простых чисел):

 

3 5 7 23 223 233 239

11 13 17 103 193 197 199

19 29 31 71 181 191 211

37 41 43 97 163 173 179

47 53 59 101 149 157 167

61 67 73 113 131 137 151

79 83 89 107 109 127 139

 

Теперь показываю магический квадрат, полученный из данного набора строк (рис. 10). Отмечу, что третий этап – превращение набора строк в магический квадрат – выполняется с помощью комбинации двух приёмов: перестановки строк и перестановки чисел в строках.

 

Квадрат № 1

 

 

Рис. 10

 

Выполняя программу дальше, я получила ещё три неэквивалентных варианта данного магического квадрата. Покажу эти варианты (рис. 11 – 13):

 

 

Рис. 11

 

 

Рис. 12

 

 

Рис. 13

 

Вполне возможно, что есть ещё варианты, я не выполнила программу до конца.

 

Теперь покажу квадрат № 2, построенный из другого набора простых чисел с такой же магической константой (рис. 14).

 

Квадрат № 2

 

 

Рис. 14

 

Мне удалось найти четыре неэквивалентных варианта данного магического квадрата. Они показаны на рис. 15 – 18. Разумеется, это не все возможные варианты.

 

 

Рис. 15

 

 

Рис. 16

 

 

Рис. 17

 

 

Рис. 18

 

Все представленные квадраты (рис. 14 – 18) получены из одного набора строк, поэтому наборы чисел в строках этих квадратов одинаковы.

Как видите, для построения магического квадрата было достаточно получить всего один набор из 7 строк.

 

Для наименьшего квадрата 8-го порядка всё выполняю точно так же. Определяю возможную минимальную магическую константу, она равна 1154. Формирую массив из простых чисел так, что сумма чисел этого массива равна 1154*8 = 9232. Генерирую набор из 8 строк так, что сумма чисел в каждой строке равна 1154 и все числа в наборе различны. Вот сгенерированный набор:

 

3  19  59  61  233  239  257  283

5  17  37  79  173  269  281  293

7  23  31  149  179  197  251 317

11  29  43  89  167  241  263  311

13  47  71  131  163  223  229  277

41  53  101  139  157  193  199  271

67  73  83  109  127  137  227  331

97  103  107  113  151  181  191  211

 

На рис. 19 изображён магический квадрат, построенный из данного набора строк.

 

 

Рис. 19

 

Для этого квадрата я не стала искать варианты, так как программа выполняется довольно долго. Другой массив простых чисел для квадрата 8-го порядка у меня тоже с ходу не сформировался. Возможно, есть варианты, но сразу их не видно.

 

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

 

5 43 73 79 181 241 317 373 419

233 269 251 113 367 11 101 163 223

157 47 211 383 59 173 271 191 239

337 227 29 83 17 277 347 131 283

397 257 7 293 359 167 3 19 229

53 421 103 281 307 127 139 263 37

193 179 353 151 311 149 23 41 331

433 199 313 61 107 401 67 13 137

349 197 379 31 109 97 409 89 71

 

На рис. 20 вы видите магический квадрат, построенный из данного набора строк.

 

Квадрат № 1

 

 

Рис. 20

 

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

 

13 17 59 131 151 241 331 379 409

353 149 293 271 73 349 3 197 43

179 283 157 5 109 227 401 137 233

139 83 223 359 181 173 269 113 191

163 11 97 367 41 337 211 311 193

373 239 281 7 61 19 101 229 421

167 37 67 23 307 313 317 103 397

463 383 47 71 29 199 251 257 31

389 107 277 53 263 79 127 347 89

 

На рис. 21 изображён магический квадрат, построенный из данного набора строк. Магическая константа квадрата такая же.

 

Квадрат № 2

 

 

Рис. 21

 

Понятно, что существует ещё очень много подобных квадратов, ведь я превратила в магический квадрат всего два набора из 9 строк. Но интересно найти хотя бы одно решение задачи. Варианты уже не так интересны. Их, конечно, можно найти, но это требует много времени.

 

Осталось показать построение наименьших магических квадратов 10-го порядка из простых чисел. Минимальная магическая константа квадрата порядка 10 равна 2470. Я сформировала два разных массива простых чисел с суммой равной 2470*10 = 24700. Сгенерировав из каждого массива по одному набору из 10 строк, построила два наименьших магических квадрата 10-го порядка. Вот первый набор из 10 строк:

 

5  13  29  151  311  313  373  379  409  487

            71  563  331  139  251  383  107  41  277  307

            167  37  11  491  461  43  149  523  317  271

            113  83  19  419  97  367  443  467  431  31

            79  241  283  229  103  479  61  223  269  503

            353  347  433  163  131  23  199  179  449  193

            47  263  547  239  73  7  463  401  197  233

            521  89  3  257  359  191  439  137  421  53

            349  389  127  293  101  397  157  109  211  337

            173  281  59  509  17  499  67  457  227  181

 

На рис. 22 вы видите магический квадрат, построенный из данного набора строк.

 

 

Рис. 22

 

Из другого набора простых чисел сгенерирован следующий набор строк:

 

3 13 17 19 263 359 373 419 463 541

61 83 449 7 491 487 5 509 41 337

71 199 439 271 127 149 389 113 431 281

269 167 443 23 53 311 307 379 421 97

457 131 137 227 467 331 107 461 109 43

89 151 233 523 211 197 397 67 499 103

367 401 163 347 353 139 223 59 101 317

179 409 181 37 257 251 433 29 173 521

73 157 277 47 479 193 283 349 229 383

11 31 79 191 239 241 293 313 503 569

 

На рис. 23 изображён полученный из данного набора строк магический квадрат.

 

 

Рис. 23

 

Все показанные магические квадраты внесены в указанную выше статью в Энциклопедии последовательностей. Повторю ссылку на эту статью:

 

http://www.research.att.com/~njas/sequences/A164843

 

Таким образом, последовательность минимальных магических констант магических квадратов из простых чисел в классическом определении имеет вид:

 

177  120  233  432  733  1154  1731  2470

 

Последние пять членов этой последовательности найдены мной. Я нашла и следующие три члена данной последовательности, для квадратов порядков 11 – 13, и построила соответствующие магические квадраты. Смотрите продолжение здесь:

 

http://www.natalimak1.narod.ru/sqmin2.htm

 

 

 

ЛИТЕРАТУРА

 

 

[1] Мартин Гарднер. Математические досуги. – М.: Мир, 1972

[2] Ю. В. Чебраков. Магические квадраты. Теория чисел, алгебра, комбинаторный анализ. – С. – Петербург, 1995

[3] Ю. В. Чебраков. Теория магических матриц. Выпуск ТММ-1. – С. -Петербург, 2008. (электронная версия книги: http://chebrakov.narod.ru/ )

[4] Н. В. Макарова. Волшебный мир магических квадратов. http://narod.ru/disk/5834353000/Magic_squares.pdf.html

[5] Н. В. Макарова. Простые числа. Математическая новелла. http://www.natalimak1.narod.ru/prost.htm  или http://narod.ru/disk/10037356000/prost.pdf.html

 

 

3 - 16 сентября 2009 г.

г. Саратов

 

 

       Пишите мне!

Приглашаю всех на форум!

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