Programming: theory and practice by alexBlack

Определение и свойства магических квадратов смотрите в википедии или на сайте Наталии Макаровой ^[1]. Здесь описан алгоритм построения пандиагонального магического квадрата девятого порядка из произвольных чисел.

а) Выбирем девять различных чисел a₁ … a_9, таких, что выполняются условия:

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

Например:

 a₁ = 11    a₂ = 22    a₃ = 17
 a₄ =  6    a₅ = 20    a₆ = 16
 a₇ = 28    a₈ =  3    a₉ = 12

b) Выбираем три числа d_1, d₂ и d_3. Эти числа вместе с a₁ … a₉ задают девять последовательностей:

	a_i
+ d₁	a_i + d₁
+ d₂	a_i + d₁ + d₂
+ d₃	a_i + d₁ + d₂ + d₃
+ d₁	a_i + 2*d₁ + d₂ + d₃
+ d₂	a_i + 2d₁ + 2d₂ + d₃
+ d₃	a_i + 2d₁ + 2d₂ + 2*d₃
+ d₁	a_i + 2d₁ + 2d₂ + 2*d₃ + d₁
+ d₂	a_i + 2d₁ + 2d₂ + 2*d₃ + d₁ + d₂

Например, для d₁ = 20, d₂ = 29 и d₃ = 18 получим следующие последовательности.

	+20	+29	+18	+20	+29	+18	+20	+29
11	31	60	78	98	127	145	165	194
22	42	71	89	109	138	156	176	205
17	37	66	84	104	133	151	171	200
6	26	55	73	93	122	140	160	189
20	40	69	87	107	136	154	174	203
16	36	65	83	103	132	150	170	199
28	48	77	95	115	144	162	182	211
3	23	52	70	90	119	137	157	186
12	32	61	79	99	128	146	166	195

c) Расположим числа этих последовательностей в таблице следующим образом:

a₁	a₁ + d₁ + d₂	a₁ + d₁	a₁ + d₁ + d₂ + d₃	a₁ +2d₁ +2d₂₊ d₃	a₁ +2d₁ + d₂ + d₃	a₁ +2d₁ +2d₂ +2d₃	a₁ +3d₁ +3d₂ +2d₃	a₁ +3d₁ +2d₂ +2d₃
a₂ +3d₁ +2d₂ +2d₃	a₂ +2d₁ +2d₂ +2d₃	a₂ + d₁ + d₂	a₂ + d₁	a₂	a₂ +2d₁ +2d₂ + d₃	a₂ +2d₁ + d₂ + d₃	a₂ + d₁ + d₂ + d₃	a₂ +3d₁ +3d₂ +2d₃
a₃ + d₁ + d₂ + d₃	a₃ +3d₁ +3d₂ +2d₃	a₃ +3d₁ +2d₂ +2d₃	a₃ +2d₁ +2d₂ +2d₃	a₃ + d₁ + d₂	a₃ + d₁	a₃	a₃ +2d₁ +2d₂ + d₃	a₃ +2d₁ + d₂ + d₃
a₄ +2d₁ +2d₂ + d₃	a₄ +2d₁ + d₂ + d₃	a₄ + d₁ + d₂ + d₃	a₄ +3d₁ +3d₂ +2d₃	a₄ +3d₁ +2d₂ +2d₃	a₄ +2d₁ +2d₂ +2d₃	a₄ + d₁ + d₂	a₄ + d₁	a₄
a₅	a₅ + d₁ + d₂	a₅ +2d₁ + d₂ + d₃	a₅ + d₁ + d₂ + d₃	a₅ +2d₁ +2d₂ + d₃	a₅ +3d₁ +2d₂ +2d₃	a₅ +2d₁ +2d₂ +2d₃	a₅ +3d₁ +3d₂ +2d₃	a₅ + d₁
a₆ +3d₁ +3d₂ +2d₃	a₆ + d₁	a₆	a₆ + d₁ + d₂	a₆ +2d₁ + d₂ + d₃	a₆ + d₁ + d₂ + d₃	a₆ +2d₁ +2d₂ + d₃	a₆ +3d₁ +2d₂ +2d₃	a₆ +2d₁ +2d₂ +2d₃
a₇ +3d₁ +2d₂ +2d₃	a₇ +2d₁ +2d₂ +2d₃	a₇ +3d₁ +3d₂ +2d₃	a₇ + d₁	a₇	a₇ + d₁ + d₂	a₇ +2d₁ + d₂ + d₃	a₇ + d₁ + d₂ + d₃	a₇ +2d₁ +2d₂ + d₃
a₈ +2d₁ +2d₂ + d₃	a₈ +2d₁ + d₂ + d₃	a₈ +2d₁ +2d₂ +2d₃	a₈ +3d₁ +3d₂ +2d₃	a₈ +3d₁ +2d₂ +2d₃	a₈	a₈ + d₁ + d₂	a₈ + d₁	a₈ + d₁ + d₂ + d₃
a₉ + d₁	a₉ + d₁ + d₂ + d₃	a₉ +2d₁ +2d₂ + d₃	a₉ +2d₁ + d₂ + d₃	a₉ +2d₁ +2d₂ +2d₃	a₉ +3d₁ +3d₂ +2d₃	a₉ +3d₁ +2d₂ +2d₃	a₉	a₉ + d₁ + d₂

Для нашего примера получится такая таблица:

11	60	31	78	127	98	145	194	165
176	156	71	42	22	138	109	89	205
84	200	171	151	66	37	17	133	104
122	93	73	189	160	140	55	26	6
20	69	107	87	136	174	154	203	40
199	36	16	65	103	83	132	170	150
182	162	211	48	28	77	115	95	144
119	90	137	186	157	3	52	23	70
32	79	128	99	146	195	166	12	61

Видно, что:

1) сумма элементов в каждом столбце и на диагоналях равна a₁ + … +a₉ + 15*d₁ + 12*d₂ +9*d₃ (магической сумме будущего квадрата S)

2) в каждом столбце суммы трех элементов (1,4,7), (2,5,8) и (3,6,9) совпадают и равны a₁ + a₄ + a₇ + 5*d₁ + 4*d₁ + 3*d₂ (=1/3*S)

d) К полученной таблице применяем преобразование ^[2]

         M[(1*i+1*j) mod 9, (2*i+3*j) mod 9] = A[i,j]

По данным примера получится следующий пандиагональный магический квадрат:

11	79	137	48	103	174	55	133	205
26	104	176	60	128	186	28	83	154
77	132	203	6	84	156	31	99	157
78	146	3	115	170	40	122	200	71
93	171	42	127	195	52	95	150	20
144	199	69	73	151	22	98	166	23
145	12	70	182	36	107	189	66	138
160	37	109	194	61	119	162	16	87
211	65	136	140	17	89	165	32	90

Аналогичные условия для примитивных квадратов получены Н.Макаровой^[3].

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

Мне удалось найти пару квадратов из простых чисел. Не буду здесь повторяться, квадраты приведены на страничке с итогами конкурса. Эти квадраты получены практически случайно (методом "тыка"). Через некоторое время я пришел к стратегии, которая позволяет находить такие квадраты (Здесь и мои идеи, и идеи Н.Макаровой, почерпнутые из личной переписки).

Посмотрим еще раз, что нам нужно найти. Нам нужна достаточно большая группа последовательностей с разностями a, b, c, a, b, c, a, b. Из этой группы нужно будет выбрать три группы (по три последовательности) с одинаковыми суммами первых элементов. Два первых квадрата получены из группы с более чем двумястами последовательностями.

Выбрав значения a,b,c не составляет труда отобрать из простых чисел нужные последовательности. (Для чисел до 5*10¹⁰ это занимает 30-40 минут). Нам нужны такие значения a,b,c, чтобы последовательностей было как можно больше. Сделаем перебор значений a,b,c в небольшом диапазоне (например 10-60) с некоторым шагом (у меня шаг = 6). Для каждой тройки нет возможно проверить весь список простых чисел, поэтому ограничимся небольшим списком или, как делал я, ограничим время и вычислим скорость, с которой появляются нужные нам последовательности. Теперь из всех троек a,b,c отберем только те, которые имеют максимальную скорость и уже для них выберем последовательности из всего списка простых чисел.

Этим способом выбраны значения a=66 b=168 c=396. Среди полученных последовательностей найдены девять, образующие примитивный квадрат. Первые члены последовательностей

output

3463 1073647 5168687 5503 1769357 4470937 8597 138337 6098863

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

S = 18,743,961
3463	6099493	4472197	5168753	139033	1770683	1073881	9461	6997
1073713	9293	6829	3697	6099727	4472431	5168687	138967	1770617
5168921	139201	1770851	1073647	9227	6763	3529	6099559	4472263
4093	6100123	4470937	5169383	139663	1769423	1074511	10091	5737
1074343	9923	5569	4327	6100357	4471171	5169317	139597	1769357
5169551	139831	1769591	1074277	9857	5503	4159	6100189	4471003
4723	6098863	4471567	5170013	138403	1770053	1075141	8831	6367
1074973	8663	6199	4957	6099097	4471801	5169947	138337	1769987
5170181	138571	1770221	1074907	8597	6133	4789	6098929	4471633

И еще один квадрат, с немного меньшей константой:

S= 12,108,303
491	1694921	2980189	2301683	1380653	1000429	1728257	960527	61153
1727597	959867	60493	1811	1696241	2981509	2301023	1379993	999769
2302343	1381313	1001089	1726937	959207	59833	1151	1695581	2980849
2381	1696811	2976409	2303573	1382543	996649	1730147	962417	57373
1729487	961757	56713	3701	1698131	2977729	2302913	1381883	995989
2304233	1383203	997309	1728827	961097	56053	3041	1697471	2977069
4271	1693031	2978299	2305463	1378763	998539	1732037	958637	59263
1731377	957977	58603	5591	1694351	2979619	2304803	1378103	997879
2306123	1379423	999199	1730717	957317	57943	4931	1693691	2978959

С еще меньшей константой (24,237) получен идеальный квадрат из простых чисел.

1↑Н.В.Макарова. Волшебный мир магических квадратов.

2↑Barkley Rosser, R.J. Walker. Алгебраическая теория дьявольских магических квадратов

3↑Н.В.Макарова. Нетрадиционные пандиагональные квадраты. Часть IV. Методы построения пандиагональных квадратов 9-го порядка

Comments

10.09.2012 12:18 Spawnet

 Нашёл что искал. 
 спасибо автору.С уважением,spawnet.

08.09.2016 12:49 find-way.net

 « Метод построения совршенных магических квадратов с помощью обобщённых латинских квадрато
 в »

Вы можете оставить комментарий или задать вопрос