Н. Макарова
АЛГОРИТМЫ ПОСТРОЕНИЯ НЕТРАДИЦИОННЫХ АССОЦИАТИВНЫХ КВАДРАТОВ
В последнее время много занимаюсь нетрадиционными магическими квадратами. Интересны алгоритмы построения нетрадиционных пандиагональных квадратов, основанные на теории Россера. Об этих исследованиях статья ещё впереди, материалов много, исследования ещё не закончены.
Сейчас остановлюсь на некоторых алгоритмах построения нетрадиционных ассоциативных квадратов.
Для квадратов 3-го порядка всё просто: любой магический квадрат 3-го порядка, как классический, так и нетрадиционный, является ассоциативным. В моей статье “Общие формулы магических квадратов (часть I)” вы найдёте общие формулы для магических квадратов 3-го порядка и множество примеров: магические квадраты из простых чисел и из чисел Смита.
Переходим к ассоциативным квадратам 4-го порядка. В той же статье есть, например, такая формула ассоциативного квадрата 4-го порядка (рис. 1):
a |
a + b + 3c |
a + 2b + 3c |
a + 3b |
a + 3b + 2c |
a + 2b + c |
a + b + c |
a + 2c |
a + 3b + c |
a + 2b + 2c |
a + b + 2c |
a + c |
a + 3c |
a + b |
a + 2b |
a + 3b + 3c |
Рис. 1
Выбрав в качестве переменных a, b, c произвольные натуральные числа, вы получите по этой формуле ассоциативный квадрат 4-го порядка.
Есть в статье ещё одна формула ассоциативного квадрата 4-го порядка – частный случай формулы Бергхольта (рис. 2). В этой формуле необходимо потребовать выполнение условия:
A + C = B + D.
A - a |
C + a + c |
B + a + c |
D – a – 2c |
D - c |
B |
C |
A + c |
C - c |
A |
D |
B + c |
B + a + 2c |
D - a - c |
A - a - c |
C + a |
Рис. 2
Я составила программу для построения ассоциативных магических квадратов 4-го порядка по данной формуле. По этой программе построен наименьший ассоциативный квадрат из простых чисел. Смотрите этот квадрат на рис. 3.
17 |
113 |
37 |
73 |
79 |
31 |
107 |
23 |
97 |
13 |
89 |
41 |
47 |
83 |
7 |
103 |
Рис. 3
Магическая константа квадрата равна 240.
Из чисел Смита мне не удалось получить ассоциативный квадрат по этой формуле. Думаю, что в принципе это возможно. Просто у меня язык программирования с плохим быстродействием.
Отмечу здесь интересное преобразование, которое я назвала преобразованием 3-х квадратов. Это преобразование превращает ассоциативный квадрат любого чётного порядка в пандиагональный квадрат. Преобразование подробно описано в моей книге “Волшебный мир магических квадратов” и доказано на примере квадрата 4-го порядка. Но в книге я рассматривала в основном преобразования классических магических квадратов. Оказалось, что преобразование применимо и к нетрадиционным ассоциативным квадратам любого чётного порядка. Мне удалось построить ассоциативный квадрат 6-го порядка из простых чисел и с помощью этого преобразования получить из него пандиагональный квадрат (об этом ниже).
Продемонстрирую преобразование на примере квадрата с рис. 3. Квадрат порядка n = 2k делится на 4 квадрата порядка k (рис. 4).
17 |
113 |
37 |
73 |
79 |
31 |
107 |
23 |
97 |
13 |
89 |
41 |
47 |
83 |
7 |
103 |
Рис. 4
Далее выполняются следующие преобразования: левый верхний квадрат остаётся без изменения, в правом верхнем квадрате выполняется отражение относительно вертикальной оси симметрии, в левом нижнем квадрате выполняется отражение относительно горизонтальной оси симметрии, правый нижний квадрат поворачивается на 180 градусов. На рис. 5 вы видите готовый преобразованный квадрат, который является пандиагональным.
17 |
113 |
73 |
37 |
79 |
31 |
23 |
107 |
47 |
83 |
103 |
7 |
97 |
13 |
41 |
89 |
Рис. 5
Теперь покажу алгоритм построения ассоциативных квадратов 4-го порядка, основанный на использовании комплементарных пар. Напомню, что в ассоциативном квадрате сумма любых двух чисел, расположенных симметрично относительно центра квадрата, равна одному и тому же числу, называемому константой ассоциативности (обозначим эту константу K). Вот эти симметричные числа мы и будем называть комплементарными. Понятно, что ассоциативный квадрат 4-го порядка составлен из 8 комплементарных пар. Очевидно также, что магическая константа ассоциативного квадрата 4-го порядка S = 2K.
Сначала 28 комплементарных пар из смитов были найдены на форуме dxdy.ru М. Алексеевым, когда я поставила задачу построения пандиагонального квадрата 4-го порядка из смитов (пандиагональные квадраты 4-го порядка являются совершенными квадратами и тоже составляются из 8 комплементарных пар).
Позже я составила программу нахождения комплементарных пар, с помощью которой нашла эти 28 пар. Вот они:
85 94 202 346 562 778 895 985 1165 1282 1642 1678 1795 1822 1858 1894 2038 2182 2218 2326 2362 2515 2578 2688 2911 2974 3091 3226 4054 4189 4306 4369 4592 4702 4765 4918 4954 5062 5098 5242 5386 5422 5458 5485 5602 5638 5998 6115 6295 6385 6502 6718 6934 7078 7186 7195
Сумма чисел в паре (или константа ассоциативности будущего ассоциативного квадрата 4-го порядка) равна 7280.
Далее написала программу построения ассоциативного квадрата 4-го порядка с использованием комплементарных пар. Запустив программу, мгновенно получила следующий квадрат (рис. 6):
1282 |
5458 |
2578 |
5242 |
5602 |
2218 |
5098 |
1642 |
5638 |
2182 |
5062 |
1678 |
2038 |
4702 |
1822 |
5998 |
Рис. 6
Магическая константа квадрата равна 14560. М. Алексеев построил из этих же комплементарных пар пандиагональный квадрат 4-го порядка. Он утверждает, что это наименьший квадрат. В таком случае и ассоциативный квадрат с такой магической константой тоже наименьший. Применив к ассоциативному квадрату с рис. 6 преобразование 3-х квадратов, мы получим пандиагональный квадрат.
Итак, то, что было трудно построить по формуле Бергхольта, оказалось совсем просто с помощью описанного алгоритма использования комплементарных пар.
Переходим к ассоциативным квадратам 5-го порядка. В указанной выше статье вы найдёте формулы и алгоритмы построения разных видов магических квадратов 5-го порядка, в том числе и ассоциативных. Но алгоритм построения ассоциативного квадрата 5-го порядка, основанный на использовании комплементарных чисел, в статье не рассматривался.
Для построения ассоциативного квадрата 5-го порядка необходимо найти как минимум 12 комплементарных пар, 25-ое число массива равно половине суммы чисел в паре, это число будет находиться в центральной ячейке квадрата.
Применив этот алгоритм, я очень быстро получила ассоциативные квадраты 5-го порядка из простых чисел и из чисел Смита.
Нашла следующий набор из 14 комплементарных пар простых чисел с суммой в паре 502 (константа ассоциативности квадрата):
3 11 23 41 53 59 71 83 101 113 149 191 233 239 263 269 311 353 389 401 419 431 443 449 461 479 491 499 251
Примечание: красным цветом выделено число, равное половине константы ассоциативности квадрата; важно помнить, что это число тоже должно быть простым.
Из этого набора комплементарных пар квадрат составился по программе очень быстро, вы видите его на рис. 7.
11 |
263 |
101 |
431 |
449 |
443 |
149 |
389 |
41 |
233 |
479 |
311 |
251 |
191 |
23 |
269 |
461 |
113 |
353 |
59 |
53 |
71 |
401 |
239 |
491 |
Рис. 7
Магическая константа равна 251*5 = 1255. По моим подсчётам это наименьший ассоциативный квадрат 5-го порядка из простых чисел.
Для построения ассоциативного квадрата 5-го порядка из чисел Смита нашла следующий набор из 13 пар с суммой в паре 4868:
166 274 454 562 706 895 922 1219 1642 1822 1894 1903 1966 2902 2965 2974 3046 3226 3649 3946 3973 4162 4306 4414 4594 4702 2434
Здесь число 2434 равно половине константы ассоциативности, оно тоже должно быть числом Смита.
Ассоциативный квадрат построился такой (рис. 8):
166 |
2902 |
1903 |
3226 |
3973 |
4414 |
706 |
4306 |
922 |
1822 |
3649 |
2974 |
2434 |
1894 |
1219 |
3046 |
3946 |
562 |
4162 |
454 |
895 |
1642 |
2965 |
1966 |
4702 |
Рис. 8
Магическая константа равна 2434*5 = 12170. По моим подсчётам это наименьший ассоциативный квадрат 5-го порядка из чисел Смита.
Как видите, всё оказалось очень просто и для квадратов порядка 5.
Ассоциативный квадрат 6-го порядка из простых чисел я начала строить в связи с задачей построения наименьшего пандиагонального квадрата из простых чисел. Поскольку в статье Россера не нашла алгоритма построения пандиагонального квадрата 6-го порядка, пришлось самой разработать какой-нибудь алгоритм. Вот и решила попробовать построить сначала ассоциативный квадрат, а потом превратить его в пандиагональный с помощью преобразования 3-х квадратов. Всё получилось!
Для построения ассоциативного квадрата 6-го порядка необходимо найти как минимум 18 комплементарных пар. Первый подходящий набор состоит из 19 комплементарных пар простых чисел с суммой в паре 210. Вот этот набор:
11 13 17 19 29 31 37 43 47 53 59 61 71 73 79 83 97 101 103 199 197 193 191 181 179 173 167 163 157 151 149 139 137 131 127 113 109 107
Написала программу построения ассоциативного квадрата 6-го порядка с использованием комплементарных пар. Вообще программа выполняется очень долго, но в данном случае – удача! Квадрат построился практически мгновенно. Смотрите этот ассоциативный квадрат на рис. 9.
11 |
197 |
17 |
191 |
47 |
167 |
181 |
31 |
173 |
53 |
131 |
61 |
139 |
59 |
137 |
83 |
109 |
103 |
107 |
101 |
127 |
73 |
151 |
71 |
149 |
79 |
157 |
37 |
179 |
29 |
43 |
163 |
19 |
193 |
13 |
199 |
Рис. 9
Магическая константа квадрата равна 210*3 = 630.
Примечание: в программе построения ассоциативного квадрата 6-го порядка 13 независимых переменных. На рис. 9а показан один из вариантов расположения независимых элементов в квадрате; независимые элементы обозначены ai (i = 1, 2, …, 13), зависимые элементы обозначены xj (j = 1, 2, …, 23).
a1 |
a2 |
a3 |
a4 |
a5 |
x1 |
a6 |
a7 |
a8 |
a9 |
a10 |
x2 |
a11 |
a12 |
a13 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
x15 |
x16 |
x17 |
x18 |
x19 |
x20 |
x21 |
x22 |
x23 |
Рис. 9а
Покажу и пандиагональный квадрат, который получен из этого ассоциативного квадрата преобразованием 3-х квадратов (рис. 10):
11 |
197 |
17 |
167 |
47 |
191 |
181 |
31 |
173 |
61 |
131 |
53 |
139 |
59 |
137 |
103 |
109 |
83 |
43 |
163 |
19 |
199 |
13 |
193 |
149 |
79 |
157 |
29 |
179 |
37 |
107 |
101 |
127 |
71 |
151 |
73 |
Рис. 10
Напомню, что известный ранее пандиагональный квадрат 6-го порядка составлен из последовательных простых чисел и имеет магическую константу 930.
Однако вопрос о минимальности построенного мной пандиагонального квадрата остаётся открытым. Это минимальный квадрат, построенный по данному алгоритму (с использованием комплементарных пар). Но ведь пандиагональный квадрат 6-го порядка не обязательно должен быть составлен из комплементарных пар. Так что вполне возможно, что существует пандиагональный квадрат 6-го порядка из произвольных простых чисел с магической константой меньше 630. Напомню, что наименьший обычный магический квадрат 6-го порядка из простых чисел имеет магическую константу 432.
Для ассоциативных квадратов из смитов задача оказалась сложнее. Пока найден только идеальный квадрат 6-го порядка с очень большой магической константой (автор М. Алексеев). Этот квадрат показан на рис. 11.
7195 |
4306 |
17149 |
23566 |
2362 |
23962 |
22738 |
9094 |
24538 |
9634 |
4702 |
7834 |
23089 |
166 |
9535 |
18022 |
6502 |
21226 |
4954 |
19678 |
8158 |
16645 |
26014 |
3091 |
18346 |
21478 |
16546 |
1642 |
17086 |
3442 |
2218 |
23818 |
2614 |
9031 |
21874 |
18985 |
Рис. 11
Квадрат построен из следующего массива смитов:
166 1642 2218 2362 2614 3091 3442 4306 4702 4954 6502 7195 7834 8158 9031 9094 9535 9634 16546 16645 17086 17149 18022 18346 18985 19678 21226 21478 21874 22738 23089 23566 23818 23962 24538 26014
Здесь 18 комплементарных пар с суммой в паре 26180. Магическая константа квадрата 26180*3 = 78540.
Эта задача сейчас решается. Смотрите тему “Магические квадраты” на форуме dxdy.ru:
http://dxdy.ru/topic12959.html
Приходите на форум со своими идеями.
Можно ли построить по алгоритму использования комплементарных чисел ассоциативный квадрат 7-го порядка из простых чисел или из чисел Смита? Предлагаю читателям исследовать этот вопрос. В принципе да, можно. Но тут опять приходится рассчитывать на удачу. Вдруг повезёт, как мне повезло с ассоциативным квадратом 6-го порядка. Ни для одного набора комплементарных пар смитов программа для квадратов 6-го порядка не выдаёт ассоциативного квадрата и не выполняется до конца, так как много вложенных циклов.
Другой путь – придумывать оптимизации, хитрые ходы. Есть над чем подумать!
ДОБАВЛЕНИЕ (10 августа 2010 г.)
М. Алексеев нашёл наименьший ассоциативный квадрат 6-го порядка из смитов с магической константой 14280 (рис. 12).
2722 |
2326 |
1255 |
2965 |
958 |
4054 |
2182 |
391 |
2902 |
3865 |
4306 |
634 |
4198 |
2605 |
2839 |
166 |
58 |
4414 |
346 |
4702 |
4594 |
1921 |
2155 |
562 |
4126 |
454 |
895 |
1858 |
4369 |
2578 |
706 |
3802 |
1795 |
3505 |
2434 |
2038 |
Рис. 12
Сразу покажу полученный из этого квадрата с помощью преобразования 3-х квадратов пандиагональный квадрат (рис. 13):
2722 |
2326 |
1255 |
4054 |
958 |
2965 |
2182 |
391 |
2902 |
634 |
4306 |
3865 |
4198 |
2605 |
2839 |
4414 |
58 |
166 |
706 |
3802 |
1795 |
2038 |
2434 |
3505 |
4126 |
454 |
895 |
2578 |
4369 |
1858 |
346 |
4702 |
4594 |
562 |
2155 |
1921 |
Рис. 13
Ещё один интересный результат я получила из найденного мной ранее пандиагонального квадрата 8-го порядка из простых чисел, который был построен из четырёх пандиагональных квадратов 4-го порядка с одинаковой магической константой по решётке Россера (подробно об алгоритмах Россера планирую рассказать в статье, посвящённой алгоритмам построения нетрадиционных пандиагональных квадратов). Поскольку этот пандиагональный квадрат 8-го порядка составлен из комплементарных пар чисел, я предположила, что к нему применимо преобразование, обратное преобразованию трёх квадратов. Попробовала и – получилось! На рис. 14 вы видите пандиагональный квадрат 8-го порядка из простых чисел, а на рис. 15 полученный из него с помощью преобразования обратного преобразованию 3-х квадратов ассоциативный квадрат.
Кстати, замечу: преобразование обратное преобразованию 3-х квадратов интересно тем, что оно совпадает с самим преобразованием 3-х квадратов.
61 |
137 |
103 |
229 |
503 |
311 |
653 |
643 |
47 |
73 |
193 |
251 |
449 |
379 |
631 |
617 |
509 |
313 |
647 |
641 |
67 |
139 |
97 |
227 |
461 |
389 |
619 |
607 |
59 |
83 |
181 |
241 |
157 |
349 |
7 |
17 |
599 |
523 |
557 |
431 |
211 |
281 |
29 |
43 |
613 |
587 |
467 |
409 |
593 |
521 |
563 |
433 |
151 |
347 |
13 |
19 |
601 |
577 |
479 |
419 |
199 |
271 |
41 |
53 |
Рис. 14
61 |
137 |
103 |
229 |
643 |
653 |
311 |
503 |
47 |
73 |
193 |
251 |
617 |
631 |
379 |
449 |
509 |
313 |
647 |
641 |
227 |
97 |
139 |
67 |
461 |
389 |
619 |
607 |
241 |
181 |
83 |
59 |
601 |
577 |
479 |
419 |
53 |
41 |
271 |
199 |
593 |
521 |
563 |
433 |
19 |
13 |
347 |
151 |
211 |
281 |
29 |
43 |
409 |
467 |
587 |
613 |
157 |
349 |
7 |
17 |
431 |
557 |
523 |
599 |
Рис. 15
Итак, ассоциативный квадрат 8-го порядка из простых чисел уже есть. При этом он наименьший, если соответствующий ему пандиагональный квадрат наименьший в классе подобных пандиагональных квадратов (составленных из комплементарных пар чисел).
Подобный пандиагональный квадрат 8-го порядка их смитов пока не построен.
По-прежнему не найден ассоциативный квадрат 7-го порядка из простых чисел; из смитов, конечно, тоже не найден.
ДОБАВЛЕНИЕ (21 марта 2011 г.)
Вот дошла очередь и до ассоциативных квадратов 7-го порядка. Сначала я рассмотрела классический ассоциативный квадрат, построенный методом террас (рис. 16).
4 |
29 |
12 |
37 |
20 |
45 |
28 |
35 |
11 |
36 |
19 |
44 |
27 |
3 |
10 |
42 |
18 |
43 |
26 |
2 |
34 |
41 |
17 |
49 |
25 |
1 |
33 |
9 |
16 |
48 |
24 |
7 |
32 |
8 |
40 |
47 |
23 |
6 |
31 |
14 |
39 |
15 |
22 |
5 |
30 |
13 |
38 |
21 |
46 |
Рис. 16
Напомню читателем: если в этом ассоциативном квадрате переставить столбцы (или строки) с шагом 1, получится идеальный квадрат.
Ассоциативный квадрат с рис. 16 можно получить из самого простого обратимого квадрата с помощью следующего матричного преобразования (рис. 17):
a14 |
a51 |
a25 |
a62 |
a36 |
a73 |
a47 |
a57 |
a24 |
a61 |
a35 |
a72 |
a46 |
a13 |
a23 |
a67 |
a34 |
a71 |
a45 |
a12 |
a56 |
a66 |
a33 |
a77 |
a44 |
a11 |
a55 |
a22 |
a32 |
a76 |
a43 |
a17 |
a54 |
a21 |
a65 |
a75 |
a42 |
a16 |
a53 |
a27 |
a64 |
a31 |
a41 |
a15 |
a52 |
a26 |
a63 |
a37 |
a74 |
Рис. 17
Если составить примитивный симметрический квадрат, являющийся полным аналогом обратимого квадрата, и применить к нему это матричное преобразование, то должен получиться нетрадиционный ассоциативный квадрат.
Пробую на примитивном квадрате из простых чисел, который я построила для идеального квадрата (рис. 18):
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 |
Рис. 18
Применяю матричное преобразование с рис. 17 к этому примитивному квадрату и получаю следующий ассоциативный квадрат из простых чисел (рис. 19):
7753 |
30637 |
13759 |
37123 |
20233 |
44017 |
27799 |
34429 |
13723 |
36187 |
19309 |
43093 |
26863 |
7717 |
13687 |
39979 |
19273 |
42157 |
25939 |
6793 |
33493 |
39043 |
19237 |
45949 |
25903 |
5857 |
32569 |
12763 |
18313 |
45013 |
25867 |
9649 |
32533 |
11827 |
38119 |
44089 |
24943 |
8713 |
32497 |
15619 |
38083 |
17377 |
24007 |
7789 |
31573 |
14683 |
38047 |
21169 |
44053 |
Рис. 19
Если в этом ассоциативном квадрате переставить столбцы с шагом 1, как показано выше для классического квадрата, получится идеальный квадрат из простых чисел, тот самый, который был построен мной из показанного на рис. 18 примитивного квадрата с помощью другого матричного преобразования. Подчеркну ещё раз: для того чтобы из примитивного квадрата получался ассоциативный квадрат, который можно превратить в идеальный с помощью перестановки столбцов (или строк), примитивный квадрат должен быть симметрическим.
Таким образом, ассоциативный квадрат 7-го порядка из простых чисел построен, но это наверняка не наименьший квадрат. Собственно, и идеальный квадрат тоже является ассоциативным.
Затем я написала программу построения ассоциативного квадрата по общей формуле, у меня получилось 18 независимых переменных. Конечно, в общем случае программа работает очень долго. Зафиксировав три первых переменных, я довольно быстро получила первый ассоциативный классический квадрат (рис. 20):
4 |
47 |
13 |
30 |
14 |
39 |
28 |
35 |
5 |
38 |
21 |
33 |
42 |
1 |
10 |
44 |
16 |
26 |
27 |
9 |
43 |
48 |
19 |
32 |
25 |
18 |
31 |
2 |
7 |
41 |
23 |
24 |
34 |
6 |
40 |
49 |
8 |
17 |
29 |
12 |
45 |
15 |
22 |
11 |
36 |
20 |
37 |
3 |
46 |
Рис. 20
Далее, конечно, начала испытывать потенциальные массивы из простых чисел. Понятно, что потенциальный массив должен состоять из комплементарных пар чисел, их должно быть не меньше 24. При этом константа комплементарности (являющаяся и константой ассоциативности искомого квадрата) равна удвоенному центральному числу (числу, находящемуся в центральной ячейке квадрата), а это число, разумеется, тоже должно быть простым. Первым потенциальным массивом из простых чисел является массив с центральным числом 617, он состоит из 24 комплементарных пар (минимальное количество). Запускаю программу для этого массива и… программа надолго “задумывается”. Оставляю этот массив и перехожу к другим. Начала проверку с больших центральных чисел. Первым выбрала центральное число 4177, массив содержит 82 комплементарных пары. Программу запускаю по-прежнему с фиксированными тремя переменными. И… в этом случае квадрат находится за несколько секунд. Вы видите этот ассоциативный квадрат на рис. 21.
67 |
8317 |
613 |
4261 |
937 |
8017 |
7027 |
7603 |
43 |
7621 |
1021 |
5023 |
7867 |
61 |
601 |
8191 |
1297 |
6691 |
6871 |
421 |
5167 |
8161 |
3931 |
7477 |
4177 |
877 |
4423 |
193 |
3187 |
7933 |
1483 |
1663 |
7057 |
163 |
7753 |
8293 |
487 |
3331 |
7333 |
733 |
8311 |
751 |
1327 |
337 |
7417 |
4093 |
7741 |
37 |
8287 |
Рис. 21
Продолжила испытания, произвольно выбирая центральные числа. Для всех выбранных центральных чисел квадраты построились. Покажу все эти квадраты (рис. 22 – 26).
307 |
5407 |
337 |
2731 |
811 |
4993 |
4363 |
4657 |
67 |
4801 |
907 |
3673 |
4663 |
181 |
601 |
5101 |
1723 |
4327 |
3463 |
463 |
3271 |
4957 |
2251 |
3793 |
2707 |
1621 |
3163 |
457 |
2143 |
4951 |
1951 |
1087 |
3691 |
313 |
4813 |
5233 |
751 |
1741 |
4507 |
613 |
5347 |
757 |
1051 |
421 |
4603 |
2683 |
5077 |
7 |
5107 |
Рис. 22
71 |
3677 |
227 |
2243 |
443 |
3527 |
2741 |
3191 |
113 |
3203 |
653 |
2333 |
3413 |
23 |
233 |
3557 |
1697 |
2087 |
2531 |
347 |
2477 |
3593 |
1787 |
2027 |
1847 |
1667 |
1907 |
101 |
1217 |
3347 |
1163 |
1607 |
1997 |
137 |
3461 |
3671 |
281 |
1361 |
3041 |
491 |
3581 |
503 |
953 |
167 |
3251 |
1451 |
3467 |
17 |
3623 |
Рис. 23
23 |
2549 |
137 |
1583 |
317 |
2423 |
1907 |
2207 |
107 |
2243 |
467 |
1607 |
2297 |
11 |
197 |
2441 |
677 |
2063 |
1667 |
281 |
1613 |
2381 |
1181 |
1811 |
1277 |
743 |
1373 |
173 |
941 |
2273 |
887 |
491 |
1877 |
113 |
2357 |
2543 |
257 |
947 |
2087 |
311 |
2447 |
347 |
647 |
131 |
2237 |
971 |
2417 |
5 |
2531 |
Рис. 24
41 |
1907 |
233 |
1013 |
347 |
1847 |
1451 |
1601 |
53 |
1487 |
677 |
1361 |
1637 |
23 |
167 |
1871 |
857 |
1523 |
983 |
131 |
1307 |
1949 |
761 |
1091 |
977 |
863 |
1193 |
5 |
647 |
1823 |
971 |
431 |
1097 |
83 |
1787 |
1931 |
317 |
593 |
1277 |
467 |
1901 |
353 |
503 |
107 |
1607 |
941 |
1721 |
47 |
1913 |
Рис. 25
61 |
1747 |
757 |
1021 |
307 |
1153 |
1093 |
1321 |
13 |
1297 |
787 |
1063 |
1627 |
31 |
271 |
1657 |
211 |
1423 |
1231 |
223 |
1123 |
1471 |
463 |
1213 |
877 |
541 |
1291 |
283 |
631 |
1531 |
523 |
331 |
1543 |
97 |
1483 |
1723 |
127 |
691 |
967 |
457 |
1741 |
433 |
661 |
601 |
1447 |
733 |
997 |
7 |
1693 |
Рис. 26
С каждым новым центральным числом количество комплементарных пар уменьшалось, 2707 – 57 пар, 1847 – 46 пар, 1277 – 40 пар, 977 – 34 пары, 877 – 26 пар.
Наконец, дошла до второго кандидата на наименьший ассоциативный квадрат, центральное число 641, 25 комплементарных пар. Этот квадрат построился мгновенно! Смотрите его на рис. 27.
53 |
1277 |
101 |
1091 |
173 |
1019 |
773 |
1013 |
59 |
863 |
599 |
881 |
1049 |
23 |
179 |
1193 |
563 |
821 |
761 |
131 |
839 |
1031 |
311 |
929 |
641 |
353 |
971 |
251 |
443 |
1151 |
521 |
461 |
719 |
89 |
1103 |
1259 |
233 |
401 |
683 |
419 |
1223 |
269 |
509 |
263 |
1109 |
191 |
1181 |
5 |
1229 |
Рис. 27
Магическая константа квадрата равна 4487.
Теперь решила посмотреть на первый потенциальный массив с центральным числом 617:
3 1231 5 1229 11 1223 17 1217 41 1193 47 1187 53 1181 71 1163 83 1151 131 1103 137 1097 173 1061 251 983 257 977 263 971 281 953 293 941 347 887 353 881 461 773 491 743 557 677 587 647 593 641 617
В массиве ровно 49 чисел. Представила все числа по модулю 6; 47 чисел равны 5(mod 6), и два числа такие: 3 = 3(mod 6), 1231 = 1(mod 6). Магическая константа квадрата 4319 = 5(mod 6).
Понятно, что числа 3 и 1231 нельзя вписать по отдельности в строку, столбец или диагональ квадрата, чтобы получить сумму, равную 5(mod 6).
Следовательно, наименьший ассоциативный квадрат 7-го порядка из простых чисел имеет магическую константу 4487 (рис. 27).
Из ассоциативных квадратов, построенных по программе, нельзя получить идеальные квадраты перестановкой столбцов (или строк) с шагом 1, как показано выше.
Мне удалось построить и наименьший ассоциативный квадрат 8-го порядка с магической константой 2040. Подробно о построении этого квадрата смотрите в статье “Нетрадиционные пандиагональные квадраты (часть III)”. Квадрат представлен на рис. 33.
Теперь представлю все известные на сегодня наименьшие ассоциативные квадраты из простых чисел.
n = 3, S = 177 (рис. 28)
17 |
89 |
71 |
113 |
59 |
5 |
47 |
29 |
101 |
Рис. 28
n = 4, S = 240 (рис. 29)
17 |
113 |
37 |
73 |
79 |
31 |
107 |
23 |
97 |
13 |
89 |
41 |
47 |
83 |
7 |
103 |
Рис. 29
n = 5, S = 1255 (рис. 30)
11 |
263 |
101 |
431 |
449 |
443 |
149 |
389 |
41 |
233 |
479 |
311 |
251 |
191 |
23 |
269 |
461 |
113 |
353 |
59 |
53 |
71 |
401 |
239 |
491 |
Рис. 30
n = 6, S = 630 (рис. 31)
11 |
197 |
17 |
191 |
47 |
167 |
181 |
31 |
173 |
53 |
131 |
61 |
139 |
59 |
137 |
83 |
109 |
103 |
107 |
101 |
127 |
73 |
151 |
71 |
149 |
79 |
157 |
37 |
179 |
29 |
43 |
163 |
19 |
193 |
13 |
199 |
Рис. 31
n = 7, S = 4487 (рис. 32)
Дублирую квадрат с рис. 27.
53 |
1277 |
101 |
1091 |
173 |
1019 |
773 |
1013 |
59 |
863 |
599 |
881 |
1049 |
23 |
179 |
1193 |
563 |
821 |
761 |
131 |
839 |
1031 |
311 |
929 |
641 |
353 |
971 |
251 |
443 |
1151 |
521 |
461 |
719 |
89 |
1103 |
1259 |
233 |
401 |
683 |
419 |
1223 |
269 |
509 |
263 |
1109 |
191 |
1181 |
5 |
1229 |
Рис. 32
n = 8, S = 2040 (рис. 33)
7 |
499 |
19 |
487 |
463 |
67 |
467 |
31 |
53 |
421 |
233 |
409 |
317 |
157 |
379 |
71 |
61 |
347 |
239 |
401 |
313 |
227 |
373 |
79 |
173 |
311 |
241 |
179 |
383 |
281 |
359 |
113 |
397 |
151 |
229 |
127 |
331 |
269 |
199 |
337 |
431 |
137 |
283 |
197 |
109 |
271 |
163 |
449 |
439 |
131 |
353 |
193 |
101 |
277 |
89 |
457 |
479 |
43 |
443 |
47 |
23 |
491 |
11 |
503 |
Рис. 33
Все квадраты, кроме квадрата 3-го порядка, найдены мной. Квадрат 3-го порядка известен очень давно. Конечно, я тоже могла бы его найти (это очень просто; в статье “Нетрадиционные квадраты из простых чисел” представлена моя программа построения нетрадиционных магических квадратов 3-го порядка), но он уже был найден. Неэквивалентных вариантов квадрат из простых чисел с магической константой 177 не имеет.
Хочу подготовить статью в OEIS “Последовательность наименьших магических констант ассоциативных квадратов из простых чисел”. Последовательность имеет такой вид:
177, 240, 1255, 630, 4487, 2040
Примечание: статья в OEIS отправлена. Смотрите https://oeis.org/A188537
Готовлю статью “Последовательность наименьших магических констант ассоциативных квадратов из чисел Смита”.
Далее предстоит найти наименьший ассоциативный квадрат 9-го порядка из простых чисел. Пока у меня нет никакого. Приглашаю читателей заняться этим вопросом. Найдено два пандиагональных квадрата 9-го порядка из простых чисел в рамках проводимого мной на форуме dxdy.ru конкурса “Нетрадиционные пандиагональные квадраты”. Найденные квадраты имеют огромные магические константы. Идеальный квадрат 9-го порядка из простых чисел мне пока найти не удалось, хотя я разработала неплохие алгоритмы для такого поиска. О пандиагональных квадратах 9-го порядка смотрите статью “Нетрадиционные пандиагональные квадраты (часть IV)”.
ДОБАВЛЕНИЕ (25 марта 2011 г.)
Далее попробовала по той же программе строить ассоциативные квадраты 7-го порядка из смитов. Пока у меня получился такой наименьший квадрат (рис. 34):
346 |
18274 |
1219 |
10966 |
2182 |
16735 |
14566 |
16474 |
121 |
13666 |
3946 |
16726 |
12442 |
913 |
1282 |
17833 |
7762 |
15646 |
9274 |
706 |
11785 |
18346 |
2839 |
14719 |
9184 |
3649 |
15529 |
22 |
6583 |
17662 |
9094 |
2722 |
10606 |
535 |
17086 |
17455 |
5926 |
1642 |
14422 |
4702 |
18247 |
1894 |
3802 |
1633 |
16186 |
7402 |
17149 |
94 |
18022 |
Рис. 34
Магическая константа квадрата равна 64288. Не уверена, что это действительно наименьший квадрат. Осталось проверить следующие потенциальные массивы (указаны магические константы): 64162, 63658, 60760, 59626, 56098, 54334, 52066, 51814, 48160, 45514, 43246. Наиболее вероятны ассоциативные квадраты с магическими константами: 56098 и 64162 (судя по поведению моей программы).
Покажу ещё два ассоциативных квадрата из смитов – 8-го и 12-го порядка. Эти квадраты построены в статье http://www.natalimak1.narod.ru/kompl556.htm
Конечно, они, скорее всего, не являются наименьшими. Смотрите рис. 35 – 36.
391 |
778 |
677101 |
675058 |
46714 |
184018 |
637474 |
498514 |
958 |
2578 |
674914 |
663934 |
281434 |
54958 |
412078 |
629194 |
514597 |
657274 |
167935 |
26914 |
655258 |
661018 |
20578 |
16474 |
633694 |
490558 |
50458 |
202954 |
585454 |
670414 |
81058 |
5458 |
674554 |
598954 |
9598 |
94558 |
477058 |
629554 |
189454 |
46318 |
663538 |
659434 |
18994 |
24754 |
653098 |
512077 |
22738 |
165415 |
50818 |
267934 |
625054 |
398578 |
16078 |
5098 |
677434 |
679054 |
181498 |
42538 |
495994 |
633298 |
4954 |
2911 |
679234 |
679621 |
Рис. 35
391 |
778 |
3694 |
677101 |
675058 |
659938 |
241519 |
46714 |
184018 |
454873 |
637474 |
498514 |
958 |
2578 |
4198 |
674914 |
663934 |
674194 |
276358 |
281434 |
54958 |
405274 |
412078 |
629194 |
8014 |
19678 |
26014 |
655618 |
650974 |
633838 |
290578 |
260158 |
294178 |
409594 |
429214 |
402214 |
514597 |
657274 |
521446 |
167935 |
26914 |
174946 |
593365 |
655258 |
661018 |
70267 |
20578 |
16474 |
633694 |
490558 |
459094 |
50458 |
202954 |
222538 |
620374 |
585454 |
670414 |
58018 |
81058 |
5458 |
519466 |
438934 |
457078 |
176926 |
250438 |
243094 |
586354 |
641254 |
538366 |
73498 |
29398 |
125266 |
554746 |
650614 |
606514 |
141646 |
38758 |
93658 |
436918 |
429574 |
503086 |
222934 |
241078 |
160546 |
674554 |
598954 |
621994 |
9598 |
94558 |
59638 |
457474 |
477058 |
629554 |
220918 |
189454 |
46318 |
663538 |
659434 |
609745 |
18994 |
24754 |
86647 |
505066 |
653098 |
512077 |
158566 |
22738 |
165415 |
277798 |
250798 |
270418 |
385834 |
419854 |
389434 |
46174 |
29038 |
24394 |
653998 |
660334 |
671998 |
50818 |
267934 |
274738 |
625054 |
398578 |
403654 |
5818 |
16078 |
5098 |
675814 |
677434 |
679054 |
181498 |
42538 |
225139 |
495994 |
633298 |
438493 |
20074 |
4954 |
2911 |
676318 |
679234 |
679621 |
Рис. 36
Ассоциативных квадратов порядков 9 - 11 не построено ни из простых чисел, ни из смитов.
ДОБАВЛЕНИЕ (31 марта 2011 г.)
Алексей Чернов прислал ассоциативные квадраты 7-го порядка из смитов, найденные по его программе:
7:[a]:64288: 14719,94,913,15529,18346,121,14566,17833,17662,1633,18022,1822,1894,5422,2182,3946,14206,17149,1642,17086,8077,2515,6583,14242,9184,4126,11785,15853,10291,1282,16726,1219,4162,14422,16186,12946,16474,16546,346,16735,706,535,3802,18247,22,2839,17455,18274,3649
7:[a]:65674: 18247,5098,3649,202,1678,18742,18058,18409,18418,2218,17482,2911,2038,4198,2227,4306,16591,10579,16582,5818,9571,2326,8158,8095,9382,10669,10606,16438,9193,12946,2182,8185,2173,14458,16537,14566,16726,15853,1282,16546,346,355,706,22,17086,18562,15115,13666,517
7:[a]:68194: 14422,10291,526,6502,19165,2902,14386,4918,18562,16645,1822,3046,18922,4279,8518,4369,15835,6115,5818,15682,11857,12406,14026,4765,9742,14719,5458,7078,7627,3802,13666,13369,3649,15115,10966,15205,562,16438,17662,2839,922,14566,5098,16582,319,12982,18958,9193,5062
7:[a]:73234: 16645,15943,382,562,20578,2902,16222,2182,18958,3442,19246,2362,19066,7978,18346,3091,15682,5638,2839,18409,9229,6718,12847,16735,10462,4189,8077,14206,11695,2515,18085,15286,5242,17833,2578,12946,1858,18562,1678,17482,1966,18742,4702,18022,346,20362,20542,4981,4279
7:[a]:74242: 18985,11816,319,16294,517,7465,18846,5926,19246,2218,20578,913,20506,4855,6084,18607,5269,14494,2965,18278,8545,11857,7186,7195,10606,14017,14026,9355,12667,2934,18247,6718,15943,2605,15128,16357,706,20299,634,18994,1966,15286,2366,13747,20695,4918,20893,9396,2227
7:[a]:87094: 24538,7402,24322,4189,922,1219,24502,9031,23242,2182,2326,23602,23089,3622,3973,4306,21919,22522,16726,5386,12262,15286,7186,5269,12442,19615,17698,9598,12622,19498,8158,2362,2965,20578,20911,21262,1795,1282,22558,22702,1642,15853,382,23665,23962,20695,562,17482,346
7:[a]:88354: 25222,5998,922,1678,4918,24538,25078,6178,23602,2155,2556,23962,24259,5642,4189,23449,22522,19858,2902,7339,8095,15848,15709,18805,12622,6439,9535,9396,17149,17905,22342,5386,2722,1795,21055,19602,985,1282,22688,23089,1642,19066,166,706,20326,23566,24322,19246,22
7:[a]:90874: 23449,25906,166,14998,2155,958,23242,728,3442,25618,25573,25582,535,9396,24588,1822,1642,25298,7402,20893,9229,6084,4198,20695,12982,5269,21766,19880,16735,5071,18562,666,24322,24142,1376,16568,25429,382,391,346,22522,25236,2722,25006,23809,10966,25798,58,2515
7:[a]:98182: 27535,12406,27994,634,1633,454,27526,3046,26545,5818,26374,4198,26014,6187,7978,4954,2785,25618,25834,25078,5935,15115,21667,9094,14026,18958,6385,12937,22117,2974,2218,2434,25267,23098,20074,21865,2038,23854,1678,22234,1507,25006,526,27598,26419,27418,58,15646,517
7:[a]:101962: 20785,6295,94,25078,778,29074,19858,2227,1376,28280,28174,22448,7051,12406,26527,27238,4918,26914,2965,2614,10786,8077,18396,7465,14566,21667,10736,21055,18346,26518,26167,2218,24214,1894,2605,16726,22081,6684,958,852,27756,26905,9274,58,28354,4054,29038,22837,8347
Вот такая хорошая коллекция ассоциативных квадратов 7-го порядка из смитов.
Если верить программе Алексея, то наименьшим квадратом является квадрат с магической константой 64288. Таким образом, найденный мной квадрат оказался наименьшим (см. рис. 34).
Из простых чисел Алексей тоже построил несколько квадратов. Наименьший квадрат у него получился с магической константой 4487, как и у меня.
Покажу наименьший
ассоциативный квадрат из смитов, полученный по программе Алексея, в привычном
виде (рис. 37):
14719 |
94 |
913 |
15529 |
18346 |
121 |
14566 |
17833 |
17662 |
1633 |
18022 |
1822 |
1894 |
5422 |
2182 |
3946 |
14206 |
17149 |
1642 |
17086 |
8077 |
2515 |
6583 |
14242 |
9184 |
4126 |
11785 |
15853 |
10291 |
1282 |
16726 |
1219 |
4162 |
14422 |
16186 |
12946 |
16474 |
16546 |
346 |
16735 |
706 |
535 |
3802 |
18247 |
22 |
2839 |
17455 |
18274 |
3649 |
Рис. 37
Предлагаю читателям сравнить этот квадрат с квадратом с рис. 34. Квадраты получились не эквивалентные.
ДОБАВЛЕНИЕ (17 апреля 2011 г.)
А. Чернов построил несколько идеальных квадратов 9-го порядка из простых чисел (см. его страничку http://alexblack.wallst.ru/article.php?content=116 )
Понятно, что идеальные квадраты являются ассоциативными. Приведу идеальный квадрат с наименьшей магической константой из найденных Алексеем (рис. 38). Минимальность этого квадрата не доказана.
5381 |
5189 |
5273 |
149 |
107 |
89 |
83 |
2633 |
5333 |
977 |
449 |
443 |
419 |
5003 |
5039 |
5147 |
5153 |
1607 |
1583 |
4787 |
3413 |
4877 |
653 |
1373 |
3089 |
2909 |
1553 |
2699 |
3863 |
743 |
4127 |
2027 |
3767 |
1979 |
2609 |
2423 |
2969 |
1709 |
3119 |
3389 |
2693 |
1997 |
2267 |
3677 |
2417 |
2963 |
2777 |
3407 |
1619 |
3359 |
1259 |
4643 |
1523 |
2687 |
3833 |
2477 |
2297 |
4013 |
4733 |
509 |
1973 |
599 |
3803 |
3779 |
233 |
239 |
347 |
383 |
4967 |
4943 |
4937 |
4409 |
53 |
2753 |
5303 |
5297 |
5279 |
5237 |
113 |
197 |
5 |
Рис. 38
Магическая константа этого квадрата равна 24237. Думаю, что можно построить ассоциативный квадрат 9-го порядка из простых чисел с меньшей магической константой. Однако сделать это непросто. Предлагаю читателям попробовать решить эту задачу.
2 – 10 августа 2010 г. – 17 апреля 2011 г.
г. Саратов
На главную страницу:
http://www.klassikpoez.narod.ru/index.htm