Н. Макарова

 

НЕТРАДИЦИОННЫЕ ПАНДИАГОНАЛЬНЫЕ КВАДРАТЫ

 

Часть II

 

Прежде чем приступать к алгоритмам построения нетрадиционных пандиагональных квадратов порядков 8 – 9, необходимо сделать дополнение к первой части статьи. Как я говорила, исследования продолжаются как мной, так и моими коллегами по форуму dxdy.ru, и получены очень интересные результаты.

 

Сначала небольшое добавление к описанному в первой части статьи методу построения идеальных квадратов 6-го порядка, основанному на построении примитивного квадрата. Примитивный квадрат получается просто: берутся семь арифметических прогрессий с одинаково разностью, первые члены которых тоже образуют арифметическую прогрессию. В полученном из этих прогрессий примитивном квадрате 7х7 вычёркиваются 4-ый столбец и 4-ая строка, и примитивный квадрат 6х6 готов. Далее применяем к этому примитивному квадрату матричное преобразование (оно показано в первой части статьи) и получаем идеальный квадрат 6-го порядка.

Обозначим: a – первый член первой арифметической прогрессии, b – разность прогрессий, c – разность прогрессии, которую образуют первые члены прогрессий, S – магическая константа квадрата. Тогда для идеального квадрата, построенного данным методом, выполняется условие:

 

a + 3(b + c) = S/6

 

По этой формуле можно подобрать значения параметров a, b, c по заданной магической константе квадрата. Пусть, например, мы хотим построить идеальный квадрат с дьявольской магической константой – 666. Я выбрала такие значения параметров: a = 3, b = 10, c = 26. Идеальный квадрат получился такой (рис. 1):

 

 

Рис. 1

 

Ещё одно свойство идеальных квадратов 6-го порядка, получаемых по данному алгоритму, забыла отметить в первой части статьи. Это свойство было отмечено в статье, посвящённой построению нетрадиционных пандиагональных квадратов порядка n = 4k + 2, подобных квадрату Журбы [1]. Если применить к идеальному квадрату, полученному по данному алгоритму, преобразование трёх квадратов, получается совершенный квадрат. Определение совершенных магических квадратов вы найдёте в моих статьях, посвящённых классическим совершенным квадратам, например, в [2]. На рис. 1а изображён совершенный квадрат 6-го порядка, полученный из квадрата с рис. 1 указанным преобразованием.

 

 

Рис. 1а

 

Интересная задача: можно ли построить совершенный квадрат 6-го порядка из простых чисел или из чисел Смита?

 

Далее расскажу о замечательном алгоритме, разработанном С. Беляевым. Изложу алгоритм кратко, подробное изложение, представленное автором алгоритма, смотрите на форуме dxdy.ru.

В этом алгоритме используется понятие решёток Россера (с этим можно познакомиться в статье Россера, ссылка на неё приведена в первой части статьи) и псевдокомплементарных пар чисел.

Понятие комплементарных пар читателям уже хорошо известно. Построенный мной пандиагональный квадрат 6-го порядка из простых чисел с магической константой 630 составлен как раз из 18 комплементарных пар. Будем обозначать в дальнейшем S_c константу комплементарности, она равна сумме чисел в комплементарной паре. Для ассоциативного квадрата константа комплементарности является константой ассоциативности. Для квадрата 6-го порядка S_c = S/3, где S - магическая константа квадрата.

Показанный на рис. 1 идеальный квадрат тоже составлен из 18 комплементарных пар чисел, константа комплементарности в этом квадрате равна 222, это и константа ассоциативности данного квадрата.

Псевдокомплементарные пары чисел – это такие пары, сумма чисел которых отличается от константы комплементарности на некоторую постоянную величину, называемую в дальнейшем отклонением от комплементарности или (для краткости) просто отклонением.

 

На рис. 2 представлена общая схема пандиагонального квадрата 6-го порядка, предложенная С. Беляевым. В этой схеме p_i обозначают отклонения от комплементарности.

 

 

Рис. 2

 

При этом отклонения связаны следующими соотношениями:

 

p₁ + p₅ + p₉ = 0

p₃ + p₅ + p₇ = 0

p₁ – p₆ – p₈ = 0

p₉ – p₂ – p₄ = 0

p₃ – p₄ – p₈ = 0

p₇ – p₂ – p₆ = 0

 

Из девяти отклонений четыре являются независимыми, остальные пять можно выразить через выбранные независимые отклонения.

Обозначим a_i – элементы группы псевдокомплементарных пар с отклонением p_i, b_i – элементы группы псевдокомплементарных пар с отклонением –p_i, i = 1, 2, …, 9. Тогда показанная на рис. 2 конфигурация будет выглядеть так (рис. 3):

 

 

Рис. 3

 

Элементы со штрихом связаны с элементами a_i, b_i следующими соотношениями (это элементы из одной псевдокомплементарной пары):

 

a_i + a_i’ – S_c = p_i

b_i + b_i’ – S_c = -p_i

 

Интересно отметить, что квадраты, составленные из 18 комплементарных пар, тоже вписываются в эту схему, в этом случае все отклонения от комплементарности равны 0. Например, идеальный квадрат с рис. 1 можно привести к представленной конфигурации, если применить к нему преобразование 3-х квадратов (см. рис. 1а).

 

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

 

 

Рис. 4

 

Имеем: S_c = 930/3 = 310.

 

p₁ = 67 + 229 – 310 = -14

p₂ = 193 + 151 – 310 = 34

p₃ = 71 + 179 – 310 = -60

p₄ = 139 + 101 – 310 = -70

p₅ = 233 + 127 – 310 = 50

p₆ = 113 + 173 – 310 = -24

p₇ = 241 + 79 - 310 = 10

p₈ = 97 + 223 – 310 = 10

p₉ = 191 + 83 – 310 = -36

 

Отмечу критерий для отклонений: квадрат, составленный из отклонений, является пандиагональным квадратом с магической константой равной 0. На рис. 5 вы видите квадрат, составленный из отклонений для приведённого на рис. 4 пандиагонального квадрата.

 

 

Рис. 5

 

Отсюда и получены условия, связывающие отклонения.

 

Алгоритм Беляева имеет огромное преимущество перед общей формулой пандиагонального квадрата в том, что в этой схеме всего 12 независимых переменных (при заданной магической константе), а в общей формуле 16 независимых переменных. Это значительно облегчает программную реализацию алгоритма. Однако здесь надо ещё задать комплект из четырёх независимых отклонений. Чтобы получить все пандиагональные квадраты с заданной магической константой, надо перебрать все возможные комплекты отклонений, что сделать тоже непросто. По общей формуле задаётся только магическая константа и массив чисел, больше ничего не надо задавать. Ну, задачу получить все пандиагональные квадраты мы и не ставим, нам достаточно получить один квадрат.

Для некоторых магических констант пришлось обработать несколько тысяч комплектов отклонений, чтобы получить хоть один пандиагональный квадрат. Например, пандиагональный квадрат из простых чисел с магической константой 498 получился только на пятой тысяче комплектов отклонений. Причём программа полного перебора выдала всего два квадрата! Покажу эти квадраты (так записан результат работы программы Беляева в файл, указаны базовые отклонения p₂, p₄, p₆, p₈ для каждого квадрата):

 

 13  29  73 139 191  53

151 167  97  17   5  61

109  41  19 127  71 131

 31  11 163 149 101  43

157 113  67   7  47 107

 37 137  79  59  83 103

  1: S=498  p2,4,6,8=-36 -8 38 -42

 

 67 103   7  13 157 151

 29 139 197  43  53  37

107   5  89  41 173  83

181  11 127  71  61  47

 97 109  19 163  31  79

 17 131  59 167  23 101

  1: S=498  p2,4,6,8=-2 26 110 -138

 

Сначала я формировала комплекты отклонений кратных 6 (было замечено, что с такими отклонениями группы псевдокомплементарных пар чисел содержат достаточно много пар). С такими отклонениями квадрат не получился. Тогда я стала формировать произвольные чётные отклонения. На второй тысяче таких комплектов отклонений квадраты построились.

 

В Интернете нашла два нетрадиционных пандиагональных квадрата 6-го порядка, составленные из произвольных натуральных чисел [3]. Эти квадраты тоже вписываются в указанную схему с отклонениями равными 0, то есть они составлены из 18 комплементарных пар натуральных чисел. Константа комплементарности в первом квадрате равна 50, во втором -  40. Вы видите эти квадраты на рис. 6 – 7.

 

 

Рис. 6

 

 

Рис. 7

 

Квадрат, изображённый на рис. 7,  имеет магическую константу 120, это наименьший пандиагональный квадрат 6-го порядка из произвольных натуральных чисел. С минимально возможной для пандиагонального квадрата 6-го порядка магической константой 114 невозможно составить пандиагональный квадрат из различных натуральных чисел. С повторяющимися числами можно составить такой квадрат. По своему алгоритму для идеальных квадратов я составила идеальный квадрат 6-го порядка с магической константой 114 с повторением чисел (рис. 8).

 

 

Рис. 8

 

Интересно отметить, что, применив к квадратам, изображённым на рис. 6 – 7, преобразование обратное преобразованию трёх квадратов, получим ассоциативные квадраты, но уже не пандиагональные. Например, ассоциативный квадрат, полученный из квадрата с рис. 6, показан на рис. 9.

 

 

Рис. 9

 

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

 

Общая схема Беляева имеет частные варианты. Некоторые из них приведены на форуме. Покажу ещё один вариант. В этом варианте всего шесть групп псевдокомплементарных чисел: с отклонениями p₁, p₂, p₃ и с отклонениями с обратным знаком –p₁, -p₂, -p₃. На рис. 10 представлена данная конфигурация:

 

 

Рис. 10

 

При этом независимыми являются только два отклонения: p₁ и p₃; отклонение p₂ = p₁ + p₃.

 

Обозначим: a_i, i = 1, 2, 3 - элементы группы с отклонением p₁, b_i, i = 1, 2, 3 - элементы группы с отклонением –p₁ и далее c_i, d_i, e_i, g_i, i = 1, 2, 3 - элементы групп с отклонениями p₂, -p₂, p₃, -p₃  соответственно. Конфигурация с рис. 10, заполненная элементами, выглядит следующим образом (рис. 11):

 

Рис. 11

 

Элемент и соответствующий элемент со штрихом - это "парные" элементы, то есть числа из одной псевдокомплементарной пары.

Реализовала эту схему и проверила её на пандиагональном квадрате из простых чисел с магической константой 930. Отклонения выбрала такие: p₁ = 20, p₂ = 70, p₃ = 50. Группы псевдокомплементарных пар содержат 24, 10, 13, 18, 22, 9 пар. Программа нашла первый квадрат за 3 минуты. Вы видите этот квадрат на рис.12.

 

Рис. 12

 

С. Беляев реализовал свой алгоритм и получил по своей программе наименьший пандиагональный квадрат 6-го порядка из простых чисел с магической константой 486 (рис. 13). Мой прогноз о существовании пандиагонального квадрата с меньшей магической константой, чем построенный мной квадрат, оказался верным.

 

 

Рис. 13

 

Ряд потенциальных магических констант пандиагональных квадратов 6-го порядка из простых чисел:

 

486, 498, 510, 522, 534, 546, 558, 570, 582, 594, 606, 618, …

 

Квадраты с константами 486, 498, 510, 522, 558 и 594 уже построены.

 

По программе Беляева удалось построить и несколько пандиагональных квадратов 6-го порядка из смитов с магическими константами меньше той, с которой был ранее найден пандиагональный квадрат Алексеевым. Наименьшая магическая константа, для которой удалась построить пандиагональный квадрат из смитов, равна 5964 (рис. 14). Но нет уверенности в том, что это действительно наименьшая константа.

 

 

Рис. 14

 

Напомню, что наименьший магический квадрат 6-го порядка из смитов имеет константу 2472.

 

Я тоже написала программу для алгоритма Беляева. Приведу один из квадратов, полученных по моей программе (рис. 15). Этот квадрат имеет магическую константу 630, то есть ту же константу, что и построенный мной ранее пандиагональный квадрат, составленный из 18 комплементарных пар чисел. Теперь квадрат составлен из чисел псевдокомплементарных пар, но имеются и комплементарные пары чисел, так как есть одно отклонение от комплементарности равное 0. Комплект отклонений для этого квадрата:

 

p₁ = -36, p₂ = -24, p₃ = 78, p₄ = 60, p₅ = 0, p₆ = -54, p₇ = -78, p₈ = 18, p₉ = 36

 

 

Рис. 15

 

***

 

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

 

Я рассмотрела приведённый в статье Россера классический нерегулярный пандиагональный квадрат 7-го порядка (см. рис. 16) и на основе этого квадрата построила нетрадиционные нерегулярные пандиагональные квадраты.

 

 

Рис. 16

 

Чтобы понять “анатомию” этого магического квадрата, я разложила его на два ортогональных латинских квадрата. На рис. 17 вы видите первый латинский квадрат. Как и следовало ожидать, этот латинский квадрат является обобщённым.

 

 

Рис. 17

 

Далее всё очень просто, составляем вспомогательную таблицу из 7 арифметических прогрессий длины 7 с одинаковой разностью b, эта таблица, кстати, является примитивным квадратом:

 

a₁, a₁ + b, a₁ + 2b, a₁ + 3b, a₁ + 4b, a₁ + 5b, a₁ + 6b

a₂, a₂ + b, a₂ + 2b, a₂ + 3b, a₂ + 4b, a₂ + 5b, a₂ + 6b

a₃, a₃ + b, a₃ + 2b, a₃ + 3b, a₃ + 4b, a₃ + 5b, a₃ + 6b

a₄, a₄ + b, a₄ + 2b, a₄ + 3b, a₄ + 4b, a₄ + 5b, a₄ + 6b

a₅, a₅ + b, a₅ + 2b, a₅ + 3b, a₅ + 4b, a₅ + 5b, a₅ + 6b

a₆, a₆ + b, a₆ + 2b, a₆ + 3b, a₆ + 4b, a₆ + 5b, a₆ + 6b

a₇, a₇ + b, a₇ + 2b, a₇ + 3b, a₇ + 4b, a₇ + 5b, a₇ + 6b

 

Прогрессии не могут быть любыми, первые члены a₃, a₄, a₅, a₆ должны удовлетворять следующему условию:

 

(2)                                 a₃ + a₆ = a₄ + a₅.

 

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

Составив вспомогательную таблицу, пронумеруем элементы этой таблицы в естественном порядке, начиная с первого элемента первой строки, и заполним матрицу 7х7 элементами этой таблицы в соответствии с квадратом, приведённым на рис. 16; числа в этом квадрате суть номера элементов вспомогательной таблицы.  Пандиагональный квадрат готов!

Приведу два примера. Сначала я построила квадрат из произвольных натуральных чисел.

 

Пример 1. Первые члены арифметических прогрессий образуют арифметическую прогрессию с разностью 10, а сами прогрессии с разностью b = 1. Первый член первой прогрессии a₁ = 1. Нерегулярный пандиагональный квадрат, построенный из чисел этих прогрессий, изображён на рис. 18.

 

 

Рис. 18

 

Пример 2.  В этом примере построен нерегулярный пандиагональный квадрат из простых чисел. Для этого выбраны 7 арифметических прогрессий длины 7 с разностью 210, первые члены которых удовлетворяют условию (2).

 

a1: 179, 389, 599, 809, 1019, 1229, 1439

a2: 199, 409, 619, 829, 1039, 1249, 1459

a3: 47, 257, 467, 677, 887, 1097, 1307

a4: 22697, 22907, 23117, 23327, 23537, 23747, 23957

a5: 182537, 182747, 182957, 183167, 183377, 183587, 183797

a6: 205187, 205397, 205607, 205817, 206027, 206237, 206447

a7: 881, 1091, 1301, 1511, 1721, 1931, 2141

 

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

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

 

 

Рис. 19

 

Магическая константа равна 416137. Можно ли построить нерегулярный пандиагональный квадрат 7-го порядка из простых чисел с меньшей магической константой? Предлагаю читателям исследовать этот вопрос.

 

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

 

 

Рис. 20

 

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

 

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

 

 

Рис. 21

 

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

Однако наименьший магический квадрат 7-го порядка из простых чисел имеет магическую константу 733. Вроде бы есть ещё возможность уменьшить магическую константу пандиагонального квадрата. Но сделать это непросто.

 

В последовательности A179440 в OEIS на сегодня есть магические константы пандиагональных квадратов из простых чисел порядков 4 – 8. При этом только для порядков 4 – 6 доказана минимальность магических констант. Для квадратов порядков 7 – 8 результаты улучшены, но минимальность полученных квадратов не доказана. На сегодня последовательность магических констант выглядит так:

 

240, 395, 486, 1649, 1584.

 

В OEIS пока не изменены магические константы квадратов порядков 6 – 8. там последовательность такая:

 

240, 395, 630, 1895, 2640.

 

Результат для пандиагонального квадрата 8-го порядка мне удалось улучшить, разработав новый алгоритм. Об этом в следующей части статьи.

 

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

И не удаётся построить идеальные квадраты 7-го прядка из простых чисел и из смитов.

 

ДОБАВЛЕНИЕ (15 - 16 октября 2010 г.)

 

Удалось построить идеальный квадрат 7-го порядка из простых чисел, в котором только одно число не является простым. Сначала покажу примитивный квадрат, построенный программой (рис. 22):

 

 

Рис. 22

 

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

 

 

Рис. 23

 

Число 5243 в этом идеальном квадрате не является простым.

 

А теперь представлю тот же самый примитивный квадрат в другом виде, это будет под моё преобразование, с помощью которого я раньше строила классические идеальные квадраты 7-го порядка из обратимых квадратов (рис. 24):

 

 

Рис. 24

 

Этот примитивный квадрат отличается от примитивного квадрата с рис. 22 переставленными столбцами. Но квадрат на рис. 24 симметрический: сумма любых двух элементов, расположенных симметрично относительно центра квадрата, равна одной и той же величине – константе ассоциативности будущего идеального квадрата. Мы имеем полный аналог обратимого квадрата. Теперь применим к этому примитивному квадрату матричное преобразование, которое вы видите на рис. 25, это преобразование используется для превращения обратимого квадрата 7х7 в классический идеальный квадрат 7-го порядка.

 

 

Рис. 25

 

На рис. 26 показан готовый идеальный квадрат.

 

 

Рис. 26

 

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

 

Проанализировав полученный нетрадиционный идеальный квадрат 7-го порядка, я получила достаточное условие для построения такого квадрата. Раньше было сказано, что идеальный квадрат 7-го порядка можно построить из семи арифметических прогрессий длины 7 с одинаковой разностью, первые члены которых тоже образуют арифметическую прогрессию. Затем я показала на форуме dxdy.ru, что арифметические прогрессии достаточно взять такие, что их первые члены a_i удовлетворяют следующему условию:

 

a₁ + a₇ = a₂ + a₆ = a₃ + a₅ = 2a₄

 

Не буду здесь дублировать этот пример. Читатели сами могут построить идеальный квадрат 7-го порядка из арифметических прогрессий указанного вида или посмотреть пример на форуме dxdy.ru в теме “Магические квадраты” [6].

 

Теперь достаточное условие в общем виде: для построения идеального квадрата 7-го порядка достаточно найти 7 последовательностей вида a_i, a_i+1, a_i+2, a_i+3, a_i+4, a_i+5, a_i+6, i = 1, 8, 15, ..., 43, удовлетворяющих следующим условиям:

 

a_i + a_i+6 = a_i+1 + a_i+5 = a_i+2 + a_i+4 = 2a_i+3

a₁ + a₄₃ = a₈ + a₃₆ = a₁₅ + a₂₉ = 2a₂₂

 

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

Достаточность этого условия доказана построением идеального квадрата 7-го порядка из последовательностей такого вида (см. рис. 26).

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

 

***

 

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

 

5857  6793  7717  7753  7789  8713  9649

                                   11827  12763  13687  13723  13759  14683  15619

                                   17377  18313  19237  19273  19309  20233  21169

24007  24943  25867  25903  25939  26863  27799

                                   30637  31573  32497  32533  32569  33493  34429

                                   36187  37123  38047  38083  38119  39043  39979

                                   42157  43093  44017  44053  44089  45013  45949

 

Константа ассоциативности равна 51806, магическая константа равна 25903*7 = 181321.

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

 

 

Рис. 27

 

Конечно, о минимальности квадрата ничего не могу сказать. Программу крутила очень долго, проверяла потенциальные магические константы сначала подряд, затем выборочно, потом снова подряд. Вполне возможно, что пропустила идеальный квадрат с меньшей магической константой. Но теперь можно заново перепроверить все потенциальные константы, начиная с найденной магической константы и двигаясь вниз. Может быть, займусь этим на досуге.

 

ДОБАВЛЕНИЕ (3 ноября 2010 г.)

 

Поскольку исследования продолжаются, получаются новые результаты, поэтому появляются добавления. Конечно, это нарушает целостность статьи, делает её не совсем удобной для чтения, но ничего пока не могу изменить. Новые результаты ведь надо добавлять в статью. Так что прошу читателей не сетовать на эти неудобства.

 

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

 

Теперь расскажу о построении пандиагональных квадратов 7-го порядка из чисел Смита (смитов). Я раньше пыталась решить эту задачу путём достраивания примитивного квадрата 5х5 до примитивного квадрата 7х7, не получилось.

Напомню, что один пандиагональный квадрат 7-го порядка из смитов построен мной давно из чисел 7 арифметических прогрессий длины 7 с одинаковой разностью (прогрессии найдены участником форума dxdy.ru). Этот квадрат показан в первой части настоящей статьи (см. рис. 48). Магическая константа квадрата огромная – 331495678.

 

Недавно мне удалось построить несколько примитивных квадратов 7х7 путём смешанного достраивания. Идея такова: выполняется достраивание примитивного квадрата 5х5 до некоторого прямоугольника nxm, в котором есть и смиты, и не смиты. Этот алгоритм я разработала при построении примитивного квадрата 11-го порядка из простых чисел. Затем полученная матрица превращается в матрицу из нулей и единиц (нули соответствуют не смитам, а единицы – смитам), из этой матрицы выделяется квадрат 7х7, состоящий из единиц. Превратив единицы в соответствующие числа, получим искомый примитивный квадрат 7х7, полностью состоящий из смитов.

Этим методом мне сначала удалось получить примитивный квадрат 6х7 из смитов (рис. 28).

 

 

Рис. 28

 

Попыталась достроить к этому прямоугольнику одну строку “чистым” достраиванием, получилось. На рис. 29 вы видите готовый примитивный квадрат 7х7:

 

 

Рис. 29

 

Примечание: “чистым” достраиванием я называю такое достраивание, при котором разрешаются только смиты (или только простые числа).

 

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

 

 

Рис. 30

 

Магическая константа этого квадрата равна 1470655.

 

Далее я продолжила поиск новых примитивных квадратов 7х7 методом смешанного достраивания. Мне удалось получить несколько таких квадратов, которые дали пандиагональные квадраты с меньшими магическими константами. Все эти квадраты показаны на форуме dxdy.ru. Покажу здесь квадрат с самой маленькой магической константой из всех полученных. На рис. 31 вы видите примитивный квадрат 7х7, а на рис. 32 полученный из него пандиагональный квадрат 7-го порядка из смитов с магической константой 749062.

 

 

Рис. 31

 

 

Рис. 32

 

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

 

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

 

***

 

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

 

 

Пока не удалось построить ни одного пандиагонального квадрата 9-го порядка из простых чисел. Сложная задача! Приглашаю читателей принять участие в её решении.

 

 

 

 

 

 

 

 

 

 

 

Построению нетрадиционных совершенных квадратов посвящена отдельная статья [7].

 

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

 

ДОБАВЛЕНИЕ (11 ноября 2010 г.)

 

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

 

58 121 382 562 23818 37678 54418

202 265 526 706 23962 37822 54562

454 517 778 958 24214 38074 54814

1858 1921 2182 2362 25618 39478 56218

16222 16285 16546 16726 39982 53842 70582

180022 180085 180346 180526 203782 217642 234382

381298 381361 381622 381802 405058 418918 435658

 

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

 

 

Рис. 33

 

Удалось построить пандиагональные квадраты 8-го и 12-го порядков из смитов и 16-го порядка из простых чисел с применением решёток Россера [8]. Магические константы полученных квадратов внесены в таблицы, показанные выше.

 

ДОБАВЛЕНИЕ (24 марта 2011 г.)

 

Опять возвращаюсь к идеальным квадратам 7-го порядка. В проводимом мной на форуме dxdy.ru конкурсе “Нетрадиционные пандиагональные квадраты” была предложена следующая задача:

 

Задача № 4

 

Для построения идеального квадрата 7-го порядка достаточно найти 7 последовательностей вида a_i, a_i+1, a_i+2, a_i+3, a_i+4, a_i+5, a_i+6, i = 1, 8, 15, ..., 43, удовлетворяющих следующим условиям:

 

a_i + a_i+6 = a_i+1+ a_i+5 = a_i+2 + a_i+4= 2a_i+3,

a₁ + a₄₃ = a₈ + a₃₆ = a₁₅ + a₂₉ = 2a₂₂

 

Пример идеального квадрата 7-го порядка из последовательностей (простых чисел), удовлетворяющих указанному условию:

 

20233 27799 30637 37123 44017 7753 13759

43093 7717 13723 19309 26863 34429 36187

25939 33493 39979 42157 6793 13687 19273

5857 12763 19237 25903 32569 39043 45949

32533 38119 45013 9649 11827 18313 25867

15619 17377 24943 32497 38083 44089 8713

38047 44053 7789 14683 21169 24007 31573

 

Магическая константа квадрата равна 181321. Автор квадрата Н. Макарова.

 

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

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

 

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

 

________________________

 

Первую часть этой задачи сразу же решил М. Алексеев. Он привёл контрпример, доказывающий, что указанные условия не являются необходимыми для построения идеального квадрата 7-го порядка. Построенный им идеальный квадрат вы видите на рис. 34.

 

 

Рис. 34

 

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

 

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

 

 

Рис. 35

 

На рисунке выделены синим цветом независимые переменные, их 12 штук.

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

 

1 этап. Задаём независимые переменные a₄, a₅, a₈, a₉, a₁₂, x₁₆, вычисляем одну зависимую переменную – x₂;

2 этап. Задаём независимые переменные a₃, a₁₀, a₁₁, x₁₇, вычисляем две зависимых переменных – x₅, x₁₅;

3 этап. Задаём одну независимую переменную – x₂₇, вычисляем одну зависимую переменную – x₇;

4 этап. Задаём одну независимую переменную – a₆, вычисляем все остальные зависимые переменные.

 

Другие варианты не пробовала, а надо бы.

Программа выполняется долго. Протестировала её на классическом идеальном квадрате. Квадрат построился такой (рис. 36):

 

 

Рис. 36

 

Очень легко по полученной общей формуле построить нетрадиционный идеальный квадрат из произвольных натуральных чисел. Задаём произвольные значения независимых переменных и магическую константу квадрата, по формуле вычисляем значения зависимых переменных, и квадрат готов. Сначала, конечно, в квадрате могут оказаться отрицательные числа, см. рис. 37.

 

 

Рис. 37

 

Для построения этого квадрата были заданы такие значения независимых переменных: a₄ = 137, a₅ = 12, a₈ = 144, a₉ =38, a₁₂ = 129, x₁₆ = 87, a₃ = 23, a₁₀ = 174, a₁₁ = 109, x₁₇ = 202, x₂₇ = 159, a₆ = 194. Магическая константа задана равной 777; понятно, что по магической константе сразу определяется центральный элемент квадрата, он равен S/7.

Теперь освободимся от отрицательных чисел, прибавив ко всем элементам квадрата, например, 408. Готовый нетрадиционный идеальный квадрат 7-го порядка из произвольных натуральных чисел вы видите на рис. 38.

 

 

Рис. 38

 

Получился квадрат аналогичный квадрату М. Алексеева (рис. 34).

 

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

Как всегда, приглашаю читателей принять участие в решении этой задачи.

В конкурсной задаче предлагалось найти наименьший идеальный квадрат 7-го порядка из смитов. Эта задача тоже пока не решена.

 

ДОБАВЛЕНИЕ (30 марта 2011 г.)

 

Продолжаю работать над построением идеального квадрата 7-го порядка из простых чисел. Мне прислал свою общую формулу для такого квадрата Алексей Чернов. Вот эта формула:

 

m0 = -m48+2/7*S

m1 = -m47+2/7*S

m2 = -m46+2/7*S

m3 = -m45+2/7*S

m4 = -m44+2/7*S

m5 = -m43+2/7*S

m6 = +m43+m44+m45+m46+m47+m48-5/7*S

m7 = -m41+2/7*S

m8 = -m40+2/7*S

m9 = -m39+2/7*S

m10 = -m38+2/7*S

m11 = -m37+2/7*S

m12 = -m36+2/7*S

m13 = +m36+m37+m38+m39+m40+m41-5/7*S

m14 = +m40+m41+m46+m47+m48-4/7*S

m15 = -m36+m39+m40+m41-m43-m44+m45+m46+2*m47+m48-4/7*S

m16 = -m37+m38+m39+m40-m43+2*m46+m47+m48-4/7*S

m17 = +m37+m39+m43+m45+m47-4/7*S

m18 = +m36+m37+m38-m39+m44-m45-m46-2*m47-m48+3/7*S

m19 = -m38-m39-2*m40-m41+m43-2*m46-2*m47-m48+10/7*S

m20 = -m37-m38-m39-m40-m41-m45-m46-m47-m48+10/7*S

m21 = -m22-m23-m24-m25-m26-m27+S

m22 = -m38-2*m39-2*m40-2*m41+m43+m44-m45-3*m46-3*m47-2*m48+15/7*S

m23 = +m36+m37-m39-m40+m43-m45-2*m46-3*m47-2*m48+8/7*S

m24 = +1/7*S

m25 = -m36-m37+m39+m40-m43+m45+2*m46+3*m47+2*m48-6/7*S

m26 = +m38+2*m39+2*m40+2*m41-m43-m44+m45+3*m46+3*m47+2*m48-13/7*S

m27 = -m36+m40-m43-m44+m46+m47+1/7*S

m28 = -m29-m30-m31-m32-m33-m34+S

m29 = +m38+m39+2*m40+m41-m43+2*m46+2*m47+m48-8/7*S

m30 = -m36-m37-m38+m39-m44+m45+m46+2*m47+m48-1/7*S

m31 = -m37-m39-m43-m45-m47+6/7*S

m32 = +m37-m38-m39-m40+m43-2*m46-m47-m48+6/7*S

m33 = +m36-m39-m40-m41+m43+m44-m45-m46-2*m47-m48+6/7*S

m34 = -m40-m41-m46-m47-m48+6/7*S

m35 = -m36-m37-m38-m39-m40-m41+S

m42 = -m43-m44-m45-m46-m47-m48+S

 

Здесь всё просто, m_i (i = 0, 1, …, 48) – элементы квадрата, S – магическая константа квадрата. Как и в моей формуле, здесь тоже 12 независимых переменных. Но вот порядок их выбора здесь оказалось возможным сделать совсем другой, нежели было сделано по моей формуле. Покажу этот порядок:

 

1 этап. Задаём независимые переменные m₄₃, m₄₄, m₄₅, m₄₆, m₄₇, m₄₈, вычисляем одну зависимую переменную – m₄₂;

2 этап. Задаём независимые переменные m₄₀, m₄₁, вычисляем одну  зависимую переменную – m₃₄;

3 этап. Задаём независимые переменные – m₃₈, m₃₉, вычисляем две зависимые переменные – m₂₆, m_29;

4 этап. Задаём одну независимую переменную – m₃₇, вычисляем три зависимые переменные - m₂₈, m₃₁, m₃₂;

5 этап. Задаём одну независимую переменную – m₃₆, вычисляем все остальные зависимые переменные - m₂₅, m₂₇, m₃₀, m₃₃, m₃₅.

 

Такой порядок задания независимых переменных дал значительный выигрыш во времени. Написала программу по этой формуле.

 

Вот первый построенный идеальный квадрат, центральное число 4177, 82 комплементарные пары (рис. 39):

 

 

Рис. 39

 

Магическая константа равна 29239.

Следом построился ещё один квадрат (рис. 40), потенциальные массивы выбирала произвольно.

 

 

Рис. 40

 

Магическая константа равна 19439.

Квадраты с меньшей магической константой мне построить не удалось.

 

Покажу идеальный квадрат, построенный по новой программе из тех простых чисел, которые составляют построенный мной ранее идеальный квадрат с магической константой 181321 (рис. 41):

 

 

Рис. 41

 

Квадрат получился неэквивалентный построенному ранее идеальному квадрату.

 

Отмечу, что все квадраты, построенные по моей программе, имеют структуру классического квадрата, изображённого на рис. 36. Это означает, что при переборе я смотрела, каким числом в комплементарной паре является элемент квадрата: первым (меньшим) или вторым (большим). Таким образом, мне удалось значительно уменьшить время выполнения программы, так как все переменные пробегают в два раза меньше значений. Однако это привело к ограничению пространства всех идеальных квадратов, так как ищутся только квадраты, имеющие заданную конкретную структуру. На рис. 42 показана структура классического квадрата с рис. 36 (в ячейках записано число 1, если элемент первый в комплементарной паре, и число 2, если элемент является вторым).

 

 

Рис. 42

 

Покажу для сравнения структуру идеального квадрата, изображённого на рис. 26 (рис. 43), этот квадрат построен с использованием примитивного квадрата.

 

 

Рис. 43

 

Интересно, что во всех строках и столбцах квадрата, кроме центральных, имеем или три двойки и четыре единицы, или три единицы и четыре двойки. В центральных строке и столбце, а также в главных диагоналях квадрата количество единиц и двоек одинаково – по три штуки. В разломанных диагоналях тоже имеем или 3+4 или 4+3 двойки и единицы.

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

 

***

 

Покажу теперь результаты А. Чернова. Ему удалось построить несколько идеальных квадратов 7-го порядка из простых чисел.  Представлю два квадрата, смотрите рис. 44 – 45. Пока наименьший квадрат имеет магическую константу 5411. Нижняя граница для магической константы равна 4487. Удастся ли построить квадрат с такой магической константой или хотя бы с константой меньше 5411? Или же квадрат с магической константой 5411 действительно является наименьшим?

 

 

Рис. 44

 

 

Рис. 45

 

Алексей тоже написал программу по своей общей формуле, но у него нет ограничений на структуру квадрата, как у меня.

Посмотрите для сравнения на структуру квадрата с рис. 44 (рис. 46):

 

 

Рис. 46

 

 

Веб-страницы

 

[1] Н. Макарова. Нетрадиционные магические квадраты. http://www.natalimak1.narod.ru/netradic.htm

[2] Н. Макарова. Совершенные магические квадраты. Часть II. http://www.klassikpoez.narod.ru/soversh1.htm

[3] Евгений Слкуни. Нетрадиционные пандиагональные магические квадраты 6-го порядка. http://www.iatp.am/slkuni/gre-la.htm 

[4] Н. Макарова. Нетрадиционные идеальные квадраты. http://www.klassikpoez.narod.ru/idnet.htm

[5] Н. Макарова. Нетрадиционные магические квадраты (метод построения нетрадиционных идеальных квадратов порядка n = 4k + 2). http://www.natalimak1.narod.ru/netradic1.htm

[6] Форум dxdy.ru, тема “Магические квадраты” http://dxdy.ru/topic12959.html

            [7] Н. Макарова. Нетрадиционные совершенные квадраты. http://www.natalimak1.narod.ru/sovnetr.htm

[8] Н. Макарова. Нетрадиционные пандиагональные квадраты порядков 8 и 12. http://natalimak1.narod.ru/kompl556.htm

 

 

24  сентября – 11 ноября 2010 г. – 30 марта 2011 г.

г. Саратов

 

Продолжение статьи читайте здесь:

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

 

 

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

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