Магические квадраты

[Nataly-Mak]

Начала писать программу построения примитивного квадрата из простых чисел.
Значения для первой строки и первого столбца примитивного квадрата программа нашла быстро:

3 7 13 19 47 43 37 31
53  .  .  .  .  .  .  .  
59  .  .  .  .  .  .  .
71  .  .  .  .  .  .  .
157 .  .  .  .  .  .  .
107 .  .  .  .  .  .  .
101 .  .  .  .  .  .  .
89  .  .  .  .  .  .  .

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

Таким образом, как мне кажется, задача нахождения примитивного квадрата 8х8 из простых чисел (или из чисел Смита) для построения пандиагонального квадрата по схеме Россера непростая.

Посмотрела в Теореме 5.5 случай для порядков $n = 3m$, пока ничего не поняла

-- Вс июн 20, 2010 14:03:27 --

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

103 105 157 117 145 123 3 63
185 111 117 129 31 57 75 111
111 133 37 53 69 115 191 107
43 81 63 87 197 135 105 105
59 81 201 141 101 99 47 87
173 147 129 93 19 93 87 75
135 89 13 97 93 71 167 151
7 69 99 99 161 123 141 117

В этом квадрате всякие числа: и простые, и составные, и одинаковые. Это, так сказать, на подступах к пандиагональному квадрату из простых чисел

Пусть в обозначениях, приведённых выше:
S_1 = a + e, S_2 = a + l
Тогда магическая константа пандиагонального квадрата, полученного из такого примитивного квадрата, вычисляется по следующей формуле:
S = 4(S_1 + S_2) - 8a
Поскольку наименьший магический квадрат 8-го порядка из простых чисел имеет магическую константу 1154, мы имеем нижнюю границу для константы пандиагонального квадрата 8-го порядка из простых чисел.
Имеем мы нижнюю границу и для пандиагонального квадрата из чисел Смита, так как наименьший МК нам тоже известен.

[Nataly-Mak]

Кстати, о наименьшем магическом квадрате 8-го порядка из произвольных смитов.
В OEIS в последовательности A170928
этот квадрат до сих пор значится как неизвестный.

maxal или svb
прошу вас исправить этот пробел. Квадрат ведь давно найден svb.

Ещё надо там убрать предположительную константу магического квадрата 7-го порядка 3719, так как 12d3 доказал, что квадрата с такой магической константой не существует. Следовательно, наименьшим является построенный мной квадрат с константой 3720, который там уже указан.

[Pavlovsky]

Берем панидагональный МК 4х4.
Например такой:

3   31   28   16
26   18   1   33
11   23   36   8
38   6   13   21

Так как у меня нет под рукой 4-х разных МК, возьмем этот МК 4 раза.
Тогда представленный ниже МК 8х8 тоже является пандиагональным.

3   3   31   31   28   28   16   16
3   3   31   31   28   28   16   16
26   26   18   18   1   1   33   33
26   26   18   18   1   1   33   33
11   11   23   23   36   36   8   8
11   11   23   23   36   36   8   8
38   38   6   6   13   13   21   21
38   38   6   6   13   13   21   21

Пользоваться теоремами из главы 5, статьи Россера, надо очень осторожно, они сформулированиы для традиционных МК, составленных из чисел от 1 до n^2. Никак не дойдут руки, чтобы посмотреть теоремы из главы 5. Какие из них справедливы и для нетрадиционных МК, а для каких можно сформулировать аналогичные теоремы справедливые для нетрадиционных МК.

[Nataly-Mak]

Ага, спасибо, сейчас посмотрю, как из разных квадратов составить пандиагональный МК8.

Для МК8 я уже представила два примера, когда из примитивного квадрата строится нетрадиционный пандиагональный квадрат по Теореме 5.5. Всё работает, хотя Россер рассматривает классические МК.

А вот для МК9 пока ничего не поняла, даже для классического МК, то, что описано в Теореме 5.5 (случай 3).

[Nataly-Mak]

Интересно получается! Если есть 4 пандиагональных квадрата 4х4 с одинаковой магической константой, то из них можно составить пандиагональный квадрат 8х8, как показал Pavlovsky.

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

[Nataly-Mak]

Согласно теореме 2.4 любой пандиагональный квадрат чётного порядка $n =2 m$ допускает L(2), то есть его можно составить из 4-х пандиагональных квадратов порядка $m$ с одинаковой магической константой.
Взяла 4 классических пандиагональных квадрата 5-го порядка и составила пандиагональный квадрат 10-го порядка:

1 1 12 18 24 9 18 15 10 22
1 1 23 8 10 24 14 12 17 20
23 14 20 25 6 2 2 16 14 8
15 14 19 17 2 5 21 6 8 23
7 17 4 6 13 13 25 24 16 5
22 10 6 21 13 13 20 19 4 2
15 23 21 4 17 20 9 7 3 11
18 18 5 4 24 7 7 25 11 11
19 10 8 12 5 21 11 3 22 19
9 22 12 15 16 16 3 3 25 9

Таким образом, для построения пандиагонального квадрата 10-го порядка из простых чисел достаточно построить 4 пандиагональных квадрата 5-го порядка с одинаковой магической константой.

[Pavlovsky]

Теорема 2.4 утверждает немного другое. Своими словами. Она утверждает что МК порядка n=2m, можно разбить на 4 решетки L(2) порядка m (на вашем рисунке выделенных различными цветами) таких, что сумма элементов в этих решетках одинакова и соответсвенно равна сумме элементов большого МК порядка n деленная на 4.

То что любой пандиагональный МК 8х8 состит из 4-х пандиагональных МК 4х4 это гипотеза и ее надо доказать. У Россера такого доказательства нет. В пользу этой гипотезы говорят теоремы 2.4 и 2.2.

Вот теорема 2.2 четко утверждает, что любой примитивный квадрат порядка 2m состоит из четырех примитивных квадратов порядка m.

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

[svb]

Контрпример:

49   64   15   2   32   17   34   47
12   53   3   62   37   28   46   19
13   52   10   55   36   29   39   26
56   57   6   11   25   24   43   38
1   16   63   50   48   33   18   31
60   5   51   14   21   44   30   35
61   4   58   7   20   45   23   42
8   9   54   59   41   40   27   22

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

[svb]

Предлагаю заменить невразумительную формулировку теоремы 2.3 на следующую:

Теорема 2.3. Пусть в квадрате порядка $$mn$ $ допустимы пути

$$P\left( {a_i ,b_i } \right)$ $ $$\left( {i = 1,2,...,s} \right)$ $.

Если квадрат порядка $$n$ $, для которого допустимы те же самые пути, требует допустимости конфигурации

$\[ \sum\limits_{x = 1}^t {\alpha _x A\left( {i_x ,j_x } \right)} \] $ ,

то квадрат порядка $$mn$ $ допускает конфигурацию

$\[ \sum\limits_{x = 1}^t {\alpha _x L\left( {i_x ,j_x ;n} \right)} \] $ .

[Nataly-Mak]

Нет, любой пандиагональный квадрат 8х8 не раскладывается на 4 пандиагональных квадрата 4х4, по крайней мере, в исходном виде. Может быть, можно его преобразовать так, что он будет раскладываться? Я что-то мельком видела у Россера о преобразовании пандиагональных квадратов.

Но вот все пандиагональные квадраты 8х8, построенные по теореме 5.5, похоже, раскладываются на 4 пандиагональных квадрата 4х4. Наверное, это можно строго доказать.
У меня пока только примеры. Я проверила классический пандиагональный квадрат 8х8, он раскладывается.
А вот воторой нетрадиционный пандиагональный квадрат 8х8, который я построила по этой схеме, он тоже раскладывается:

[Nataly-Mak]

Запустила свою программу построения пандиагональных квадратов 4-го порядка, написанную на основании формулы Бергхольта.
Программа строит пандиагональные квадраты из простых чисел и очень много, но пока все идут с повторяющимися числами. Например, очень много квадратов с магической константой 660. Выбрала произвольно 4 квадрата и составила такой пандиагональный квадрат 8-го порядка:

97 257 199 157 101 149 263 97
263 263 101 151 199 149 97 97
227 23 137 223 223 131 73 283
73 23 223 223 137 137 227 277
229 181 67 233 233 73 131 173
131 181 233 233 67 67 229 179
107 199 257 47 103 307 193 107
193 193 103 53 257 307 107 107

Это, так сказать, второе приближение. Квадрат состоит только из простых чисел, но есть одинаковые числа. В этом единственный изъян.
Магическая константа равна 660*2=1320.

maxal
у вас есть мощная программа построения пандиагональных квадратов 4-го порядка. Не могли бы вы попробовать найти 4 наименьших пандиагональных квадрата из простых чисел (и из смитов) с одинаковой магической константой, состоящих из различных чисел?
При этом надо учитывать, что магическая константа квадратов 4х4 из простых чисел должна быть не меньше 578, а квадратов из смитов - не меньше 2928.
Но с константами, не удовлетворяющими этому условию, 4 пандиагональных квадрата 4х4 и не найдётся, иначе получится, что можно будет составить пандиагональный квадрат 8х8 с магической константой меньше, чем магическая константа магического квадрата 8х8 (для простых чисел наименьший квадрат 8х8 имеет константу 1154, а для смитов - 5856).

[Nataly-Mak]

Есть первый пандиагональный квадрат 8-го порядка из простых чисел

71 53 97 193 683 607 829 827
83 113 401 421 373 337 823 809
691 733 821 701 79 179 89 67
673 577 523 569 383 353 101 181
157 233 11 13 769 787 743 647
467 503 17 31 757 727 439 719
761 661 751 773 149 107 19 139
457 487 739 659 167 263 317 271

Удалось-таки построить 4 пандиагональных квадрата 4х4 из различных простых чисел, но константа этих квадратов довольно большая - 1680.
А квадрат 8х8 соответственно имеет константу 1680*2=3360.

Кто меньше?

[svb]

Неплохо бы 719 заменить на 419

[Nataly-Mak]

Заменила:

71 53 97 193 683 607 829 827
83 113 401 421 373 337 823 809
691 733 821 701 79 179 89 67
673 577 523 569 383 353 101 181
157 233 11 13 769 787 743 647
467 503 17 31 757 727 439 419
761 661 751 773 149 107 19 139
457 487 739 659 167 263 317 271

Это максимальное уменьшение от вас? Плоховато

Тогда хотя бы расскажите, как по Теореме 5.5 (случай 3) строить пандиагональный квадрат 9-го порядка. Я ничего там не поняла.

[Pavlovsky]

svb в сообщении #333624 писал(а):

Контрпример:

49   64   15   2   32   17   34   47
12   53   3   62   37   28   46   19
13   52   10   55   36   29   39   26
56   57   6   11   25   24   43   38
1   16   63   50   48   33   18   31
60   5   51   14   21   44   30   35
61   4   58   7   20   45   23   42
8   9   54   59   41   40   27   22

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

Это ничего страшного. Гипотезу всегда можно подкорректировать. Скажем так:

Любой регулярный (по Россеру) пандиагональный МК 8х8 состит из 4-х пандиагональных МК 4х4.