Дьявольские магические квадраты из простых чисел

[Nataly-Mak]

Как уже сказано выше, решения конкурсной задачи для порядков 7 - 9 известны, только не доказана минимальность.
Можно ли минимизировать эти решения? Для порядка $n=8$ можно, я уже нашла решение с магической констнтой меньше известной. Но в минимальности не уверена. Надо проверить оставшиеся потенциальные магические константы.
Для порядка 9 мне пока не удалось минимизировать известное решение alexBlack. Программу написала, но перебор идёт долго.

Для порядков $n>9$ решения мне неизвестны. Может, где-то они и получены, но я не встречала. Если кто-то вдруг найдёт такие решения, сообщите, пожалуйста.
Кстати, на конкурс разрешается вводить известные решения.

Теперь покажу идеальные квадраты порядков $n>9$ из произвольных натуральных чисел, чтобы участники могли видеть примеры таких квадратов.

$n=10$

101 5779 407 5677 169 5473 373 5711 475 5405
5371 577 5065 679 5303 883 5099 645 4997 951
4079 1801 4385 1699 4147 1495 4351 1733 4453 1427
4045 1903 3739 2005 3977 2209 3773 1971 3671 2277
985 4895 1291 4793 1053 4589 1257 4827 1359 4521
1393 4555 1087 4657 1325 4861 1121 4623 1019 4929
3637 2243 3943 2141 3705 1937 3909 2175 4011 1869
4487 1461 4181 1563 4419 1767 4215 1529 4113 1835
4963 917 5269 815 5031 611 5235 849 5337 543
509 5439 203 5541 441 5745 237 5507 135 5813

$K=5914, S=29570$

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

113 173 1151 1091 1229 389 911 911 101 941
173 113 1091 1151 389 1229 911 911 941 101
839 839 521 1361 41 101 1013 953 1091 251
839 839 1361 521 101 41 953 1013 251 1091
941 881 953 113 701 701 449 1289 461 521
881 941 113 953 701 701 1289 449 521 461
311 1151 389 449 1361 1301 881 41 563 563
1151 311 449 389 1301 1361 41 881 563 563
1301 461 491 491 173 1013 251 311 1289 1229
461 1301 491 491 1013 173 311 251 1229 1289

$K=1402, S=7010$
Этот квадрат составлен из копий одного и того же идеального квадрата 5-го порядка из простых чисел.
А вот составить идеальный квадрат 10-го порядка из различных простых чисел посложнее. Мне пока это не удалось.

-- Пн фев 23, 2015 09:37:43 --

Идеальный квадрат 11-го порядка из произвольных натуральных чисел я построила так.
Сначала построила ассоциативный квадрат Стенли:

27541 28513 28549 29485 30409 30445 30481 31405 32341 32377 33349
34519 35491 35527 36463 37387 37423 37459 38383 39319 39355 40327
41149 42121 42157 43093 44017 44053 44089 45013 45949 45985 46957
10819 11791 11827 12763 13687 13723 13759 14683 15619 15655 16627
16369 17341 17377 18313 19237 19273 19309 20233 21169 21205 22177
22999 23971 24007 24943 25867 25903 25939 26863 27799 27835 28807
29629 30601 30637 31573 32497 32533 32569 33493 34429 34465 35437
35179 36151 36187 37123 38047 38083 38119 39043 39979 40015 40987
4849 5821 5857 6793 7717 7753 7789 8713 9649 9685 10657
11479 12451 12487 13423 14347 14383 14419 15343 16279 16315 17287
18457 19429 19465 20401 21325 21361 21397 22321 23257 23293 24265

$K=51806, S=284933$

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

15619 21205 28807 29629 36151 5857 13423 21325 30445 37459 45013
12487 20401 30409 37423 44089 14683 21169 27835 35437 35179 5821
20233 27799 34465 40987 4849 12451 19465 29485 37387 44053 13759
19429 28549 36463 44017 13723 19309 26863 34429 40015 10657 11479
25939 33493 39979 9685 17287 18457 28513 35527 43093 13687 19273
27541 35491 42157 12763 19237 25903 32569 39043 9649 16315 24265
32533 38119 8713 16279 23293 33349 34519 42121 11827 18313 25867
40327 41149 11791 17377 24943 32497 38083 7789 15343 23257 32377
38047 7753 14419 22321 32341 39355 46957 10819 17341 24007 31573
45985 16627 16369 23971 30637 37123 7717 14383 21397 31405 39319
6793 14347 21361 30481 38383 45949 15655 22177 22999 30601 36187

$K=51806, S=284933$

(Матричное преобразование и иллюстрация показаны здесь.)

Насколько трудно составить ассоциативный квадрат Стенли из различных простых чисел? Думаю, что трудно, если учесть, что длительные попытки (предпринятые мной и коллегами) составить ассоциативный квадрат Стенли 9-го порядка пока ни к чему не привели.
Поэтому данный алгоритм не является эффективным для поиска идеального квадрата 11-го порядка из различных простых чисел. Надо придумывать другие алгоритмы.
Есть, например, общая формула. Ну, это тоже, скорее всего, не самый лучший алгоритм.

[Nataly-Mak]

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

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

103 263 59 313 163 47 233 61 139 149 293 157
263 103 313 59 47 163 61 233 149 139 157 293
229 23 257 73 307 101 131 277 13 317 53 199
23 229 73 257 101 307 277 131 317 13 199 53
283 167 17 271 67 227 173 37 181 191 269 97
167 283 271 17 227 67 37 173 191 181 97 269
61 233 149 139 157 293 263 103 313 59 47 163
233 61 139 149 293 157 103 263 59 313 163 47
277 131 317 13 199 53 23 229 73 257 101 307
131 277 13 317 53 199 229 23 257 73 307 101
37 173 191 181 97 269 167 283 271 17 227 67
173 37 181 191 269 97 283 167 17 271 67 227

$K=330, S=1980$

Этот квадрат составлен из копий одного и того же идеального квадрата 6-го порядка из различных простых чисел (автор квадрата maxal ).

Составить идеальный квадрат 12-го порядка из различных натуральных чисел тоже просто. Достаточно взять любую арифметическую прогрессию длины 144 и заполнить числами этой прогрессии матрицу 12х12 в соответствии с любым классическим идеальным квадратом 12-го порядка.

Теперь задача у нас сложнее: составить идеальный квадрат 12-го порядка из различных простых чисел.

Можно ли получить идеальный квадрат 12-го порядка из ассоциативного квадрата Стенли? Можно, но не из любого ассоциативного квадрата Стенли. Для этого ассоциативный квадрат Стенли должен удовлетворять дополнительным условиям. Составить такой ассоциативный квадрат Стенли из различных простых чисел тоже сложно.

[Nataly-Mak]

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

Попытка №1
Константа ассоциативности 9230, массив состоит из 133 комплементарных пар простых чисел.
Это максимум, что удалось получить быстро:

4327  4789  4957  8923  0  0  0  8461  1297  0 
9199  709  6373  73  6763  1213  0  5839  0  2803 
811  2203  853  4003  7927  3079  8731  8893  4663  4987 
43  0  5323  79  97  6043  0  2833  0  9103 
0  229  8623  9067  223  0  7507  103  139  0 
0  9091  9127  1723  0  9007  163  607  9001  0 
127  0  6397  0  3187  9133  9151  3907  0  9187 
4243  4567  337  499  6151  1303  5227  8377  7027  8419 
6427  0  3391  0  8017  2467  9157  2857  8521  31 
0  7933  769  0  0  0  307  4273  4441  4903

$K= 9230, S= 46150$

Попытка №2
Константа ассоциативности 5914, массив состоит из 73 комплементарных пар простых чисел.
Это максимум, что удалось получить быстро:

101  5783  0  5657  0  0  0  5717  263  0 
5351  1913  5087  521  5297  977  0  383  0  641 
3761  1181  5051  1697  4127  1493  4391  3851  4463  0 
3701  0  3557  1223  3617  2657  0  1997  0  2543 
0  5231  2111  4967  941  0  1433  4091  1163  0 
0  4751  1823  4481  0  4973  947  3803  683  0 
3371  0  3917  0  3257  2297  4691  2357  0  2213 
0  1451  2063  1523  4421  1787  4217  863  4733  2153 
5273  0  5531  0  4937  617  5393  827  4001  563 
0  5651  197  0  0  0  257  0  131  5813 

$K=5914, S=29570$

В программе поиска реализована эта формула для подгруппы идеальных квадратов 10-го порядка.

Дальше перебор идёт долго, ждать не хочется. Да когда ещё неизвестно, существует ли решение.
Если программу написать, скажем, на C++ и хорошо оптимизировать, вполне реально получить полное решение.
Для порядка $n=8$ я получила решения и по своей плохонькой программке.

-- Вт фев 24, 2015 06:18:50 --

Кстати, малюсенькая эвристика

Сравните последнее неполное решение с этим идеальным квадратом 10-го порядка из различных натуральных чисел:

101 5779 407 5677 169 5473 373 5711 475 5405
5371 577 5065 679 5303 883 5099 645 4997 951
4079 1801 4385 1699 4147 1495 4351 1733 4453 1427
4045 1903 3739 2005 3977 2209 3773 1971 3671 2277
985 4895 1291 4793 1053 4589 1257 4827 1359 4521
1393 4555 1087 4657 1325 4861 1121 4623 1019 4929
3637 2243 3943 2141 3705 1937 3909 2175 4011 1869
4487 1461 4181 1563 4419 1767 4215 1529 4113 1835
4963 917 5269 815 5031 611 5235 849 5337 543
509 5439 203 5541 441 5745 237 5507 135 5813

$K=5914, S=29570$

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

[Nataly-Mak]

Несколько полезных ссылок для потенциальных участников конкурса

1. Walter Trump «Ultra Magic squares»
http://www.magic-squares.net/trump-ultra.htm
2. Лучшие результаты конкурса «Пандиагональные квадраты из простых чисел»
http://trdb.org/Contest/PandiagonalMagi ... inalReport
3. Статья «Нетрадиционные идеальные квадраты»
http://www.klassikpoez.narod.ru/idnet.htm
4. Цикл статей «Нетрадиционные пандиагональные квадраты»
одна из статей цикла
http://www.natalimak1.narod.ru/pannetr1.htm
5. Тема "Магические квадраты"
topic12959.html
6. Тема «Антимагические квадраты»
topic58862.html
7. Тема «Идеальные магические квадраты»
http://e-science.ru/groups/%D0%B8%D0%B4 ... 1%82%D1%8B
8. Статья в OEIS «The constant for the smallest n X n associative magic square which consists of primes»
A188537

[Nataly-Mak]

Представлю образец идеального квадрата 14-го порядка из произвольных (различных) натуральных чисел

23 9166 433 9084 351 8838 105 8715 228 8961 474 9043 556 8633
8592 679 8182 761 8264 1007 8510 1130 8387 884 8141 802 8059 1212
6173 3016 6583 2934 6501 2688 6255 2565 6378 2811 6624 2893 6706 2483
7362 1909 6952 1991 7034 2237 7280 2360 7157 2114 6911 2032 6829 2442
4943 4246 5353 4164 5271 3918 5025 3795 5148 4041 5394 4123 5476 3713
3672 5599 3262 5681 3344 5927 3590 6050 3467 5804 3221 5722 3139 6132
1253 7936 1663 7854 1581 7608 1335 7485 1458 7731 1704 7813 1786 7403
1827 7444 1417 7526 1499 7772 1745 7895 1622 7649 1376 7567 1294 7977
3098 6091 3508 6009 3426 5763 3180 5640 3303 5886 3549 5968 3631 5558
5517 3754 5107 3836 5189 4082 5435 4205 5312 3959 5066 3877 4984 4287
6788 2401 7198 2319 7116 2073 6870 1950 6993 2196 7239 2278 7321 1868
6747 2524 6337 2606 6419 2852 6665 2975 6542 2729 6296 2647 6214 3057
8018 1171 8428 1089 8346 843 8100 720 8223 966 8469 1048 8551 638
597 8674 187 8756 269 9002 515 9125 392 8879 146 8797 64 9207

$K=9230, S=64610$

Квадрат построен из чисел арифметической прогрессии $23+41n, n=0,1,…,224$ по следующему эталону:

1 224 11 222 9 216 3 213 6 219 12 221 14 211
210 17 200 19 202 25 208 28 205 22 199 20 197 30
151 74 161 72 159 66 153 63 156 69 162 71 164 61
180 47 170 49 172 55 178 58 175 52 169 50 167 60
121 104 131 102 129 96 123 93 126 99 132 101 134 91
90 137 80 139 82 145 88 148 85 142 79 140 77 150
31 194 41 192 39 186 33 183 36 189 42 191 44 181
45 182 35 184 37 190 43 193 40 187 34 185 32 195
76 149 86 147 84 141 78 138 81 144 87 146 89 136
135 92 125 94 127 100 133 103 130 97 124 95 122 105
166 59 176 57 174 51 168 48 171 54 177 56 179 46
165 62 155 64 157 70 163 73 160 67 154 65 152 75
196 29 206 27 204 21 198 18 201 24 207 26 209 16
15 212 5 214 7 220 13 223 10 217 4 215 2 225

$K=226, S=1582$

Построение эталона описано в статье.
(Поскольку классического идеального квадрата 14-го порядка не существует, его роль выполняет данный эталон.)

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

1439 23 1307 947 359 1409 47 1499 137 1187 599 239 1523 107
23 1439 947 1307 1409 359 1499 47 1187 137 239 599 107 1523
443 173 227 593 269 563 1163 383 983 1277 953 1319 1373 1103
173 443 593 227 563 269 383 1163 1277 983 1319 953 1103 1373
863 1493 929 1229 1097 827 1433 113 719 449 317 617 53 683
1493 863 1229 929 827 1097 113 1433 449 719 617 317 683 53
977 977 179 179 887 887 773 773 659 659 1367 1367 569 569
977 977 179 179 887 887 773 773 659 659 1367 1367 569 569
1493 863 1229 929 827 1097 113 1433 449 719 617 317 683 53
863 1493 929 1229 1097 827 1433 113 719 449 317 617 53 683
173 443 593 227 563 269 383 1163 1277 983 1319 953 1103 1373
443 173 227 593 269 563 1163 383 983 1277 953 1319 1373 1103
23 1439 947 1307 1409 359 1499 47 1187 137 239 599 107 1523
1439 23 1307 947 359 1409 47 1499 137 1187 599 239 1523 107

$K=1546, S=10822$

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

[Nataly-Mak]

Представляю образец идеального квадрата 15-го порядка из произвольных (различных) натуральных чисел:

45 4093 1189 1937 3081 2025 7393 7129 8537 9021 5325 9373 6469 5237 3741
1629 2861 2465 7657 6953 8229 8801 5765 9637 6293 4929 3521 485 4357 1013
7349 6777 8493 9241 5545 9329 6117 5193 3961 265 4049 837 1893 3301 2245
8713 5809 9857 6381 4665 3433 529 4577 1101 1365 2773 2509 7877 7041 7965
6161 5105 3697 353 4269 881 1805 3037 2333 7569 6821 8405 8977 5633 9549
177 4533 1321 1585 2729 2157 7833 7261 8185 8669 5457 9813 6601 4885 3389
1849 3257 2421 7305 6733 8449 9197 5721 9285 6073 5149 3917 441 4005 793
7745 6997 8273 8889 5501 9725 6337 4973 3609 221 4445 1057 1673 2949 2201
9153 5941 9505 6029 4797 3873 661 4225 749 1497 3213 2641 7525 6689 8097
6557 5061 3345 133 4489 1277 1761 2685 2113 7789 7217 8361 8625 5413 9769
397 4313 969 1541 3125 2377 7613 6909 8141 9065 5677 9593 6249 4841 3785
1981 2905 2069 7437 7173 8581 8845 5369 9417 6513 5281 3565 89 4137 1233
7701 6645 8053 9109 5897 9681 5985 4753 3829 617 4401 705 1453 3169 2597
8933 5589 9461 6425 5017 3653 309 4181 1145 1717 2993 2289 7481 7085 8317
6205 4709 3477 573 4621 925 1409 2817 2553 7921 6865 8009 8757 5853 9901

$K=9946, S=74595$

Квадрат составлен из чисел арифметической прогрессии $45+44n, n=0,1,…,224$ на основе классического идеального квадрата 15-го порядка взятого из статьи, рис. 5.

Интересно: для данной константы ассоциативности имеем массив точно из 112 комплементарных пар простых чисел:

(Оффтоп)

5 17 23 59 89 107 113 179 197 227 257 269 317 359 449 467 479 509 569 653 719 743 773 809 887 947 
977 983 1013 1097 1109 1163 1193 1277 1283 1319 1373 1409 1433 1499 1523 1559 1583 1709 1823 1877 1907 
1997 2027 2039 2063 2069 2129 2153 2243 2273 2297 2339 2357 2399 2417 2423 2447 2459 2663 2693 2699 
2753 2819 2837 2843 2903 2927 2963 2969 2999 3083 3089 3119 3167 3209 3257 3347 3557 3593 3617 3623 
3659 3677 3803 3833 3917 4007 4019 4049 4079 4133 4139 4229 4253 4289 4373 4463 4547 4637 4643 4649 
4673 4793 4799 4937 4943 5003 5009 5147 5153 5273 5297 5303 5309 5399 5483 5573 5657 5693 5717 5807 
5813 5867 5897 5927 5939 6029 6113 6143 6269 6287 6323 6329 6353 6389 6599 6689 6737 6779 6827 6857 
6863 6947 6977 6983 7019 7043 7103 7109 7127 7193 7247 7253 7283 7487 7499 7523 7529 7547 7589 7607 
7649 7673 7703 7793 7817 7877 7883 7907 7919 7949 8039 8069 8123 8237 8363 8387 8423 8447 8513 8537 
8573 8627 8663 8669 8753 8783 8837 8849 8933 8963 8969 8999 9059 9137 9173 9203 9227 9293 9377 9437 
9467 9479 9497 9587 9629 9677 9689 9719 9749 9767 9833 9839 9857 9887 9923 9929 9941

Это первая потенциальная константа ассоциативности для идеальных квадратов 15-го порядка из различных простых чисел.
Таким образом, мы знаем нижнюю границу магической константы для таких квадратов, она равна 74595.

Можно ли составить идеальный квадрат 15-го порядка из чисел данного массива

-- Ср фев 25, 2015 08:17:12 --

Ещё немного покрутила программу поиска идеального квадрата 10-го порядка из различных простых чисел.
Такое приближение получила с 14 “дырками”:

71 5783 653 5657 0 0 0 5717 53 5903
5351 1181 5087 383 5297 1913 0 431 5807 683
4547 521 4943 1697 4127 1493 4391 2447 4463 941
4013 2237 3701 2153 3911 2243 0 2081 2543 2381
0 4967 983 4751 1277 0 1097 4691 1823 5153
761 4091 1223 4817 0 4637 1163 4931 947 0
3533 3371 3833 0 3671 2003 3761 2213 3677 1901
4973 1451 3467 1523 4421 1787 4217 971 5393 1367
5231 107 5483 0 4001 617 5531 827 4733 563
11 5861 197 0 0 0 257 5261 131 5843

$K=5914, S=29570$

Это приближение нашлось за несколько минут; просто я отпустила несколько последних элементов квадрата (то есть убрала в программе их проверку, что позволяет им принимать любые значения).
Покажу, что в “дырках”:

71 5783 653 5657 -445 4769 1409 5717 53 5903
5351 1181 5087 383 5297 1913 3437 431 5807 683
4547 521 4943 1697 4127 1493 4391 2447 4463 941
4013 2237 3701 2153 3911 2243 4307 2081 2543 2381
1079 4967 983 4751 1277 3749 1097 4691 1823 5153
761 4091 1223 4817 2165 4637 1163 4931 947 4835
3533 3371 3833 1607 3671 2003 3761 2213 3677 1901
4973 1451 3467 1523 4421 1787 4217 971 5393 1367
5231 107 5483 2477 4001 617 5531 827 4733 563
11 5861 197 4505 1145 6359 257 5261 131 5843

$K=5914, S=29570$

Небольшой перекос всё-таки получился (отрицательный элемент -445 и комплементарный элемент 6359). Остальные неправильные элементы в нужном диапазоне только не являются простыми числами. Правда, есть среди неправильных элементов и простые числа: 1409, 1607, 2477, но эти числа не в комплементарных парах. Поэтому фактически это тоже неправильные элементы.

[Nataly-Mak]

Ещё одна эвристика - использование шаблонов из вычетов по некоторому модулю m.
Шаблоны я получаю из приближений к решению, это очень просто делать.
Например, из показанного выше приближения к решению для идеального квадрата 10-го порядка получается такой шаблон из вычетов по модулю 4:

3  3  1  1  3  1  1  1  1  3 
3  1  3  3  1  1  1  3  3  3 
3  1  3  1  3  1  3  3  3  1 
1  1  1  1  3  3  3  1  3  1 
3  3  3  3  1  1  1  3  3  1 
1  3  3  1  1  1  3  3  3  3 
1  3  1  3  3  3  1  1  1  1 
1  3  3  3  1  3  1  3  1  3 
3  3  3  1  1  1  3  3  1  3 
3  1  1  1  1  3  1  1  3  3 

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

[Nataly-Mak]

Теперь проделала такой финт

Беру образец идеального квадрата 10-го порядка из различных натуральных чисел:

101 5779 407 5677 169 5473 373 5711 475 5405
5371 577 5065 679 5303 883 5099 645 4997 951
4079 1801 4385 1699 4147 1495 4351 1733 4453 1427
4045 1903 3739 2005 3977 2209 3773 1971 3671 2277
985 4895 1291 4793 1053 4589 1257 4827 1359 4521
1393 4555 1087 4657 1325 4861 1121 4623 1019 4929
3637 2243 3943 2141 3705 1937 3909 2175 4011 1869
4487 1461 4181 1563 4419 1767 4215 1529 4113 1835
4963 917 5269 815 5031 611 5235 849 5337 543
509 5439 203 5541 441 5745 237 5507 135 5813

$K=5914, S=29570$

Задаю значения 28 свободных элементов квадрата - простые числа (из массива комплементарных пар с данной константой комплементарности) близкие к значениям элементов образца:

K=5914:X(2)=5783:X(4)=5657:X(8)=5717:X(11)=5351:X(13)=5087:X(15)=5297
X(24)=1697:X(25)=4127:X(26)=1493:X(27)=4391:X(29)=4463
X(31)=4013:X(34)=2003:X(35)=4001:X(38)=1997:X(40)=2297:X(45)=1097:X(48)=4817:X(49)=1367
X(21)=4091:X(36)=2213:X(43)=1277:X(33)=3761:X(44)=4817:X(47)=1223:X(42)=4931:X(50)=4547:X(39)=3671

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

125  5783  419  5657  137  5489  461  5717  467  5315 
5351  611  5087  665  5297  917  4961  641  5039  1001 
4091  1871  4349  1697  4127  1493  4391  1721  4463  1367 
4013  1811  3761  2003  4001  2213  3803  1997  3671  2297 
947  4931  1277  4817  1097  4547  1223  4817  1367  4547 
1367  4547  1097  4691  1367  4817  1097  4637  983  4967 
3617  2243  3917  2111  3701  1913  3911  2153  4103  1901 
4547  1451  4193  1523  4421  1787  4217  1565  4043  1823 
4913  875  5273  953  4997  617  5249  827  5303  563 
599  5447  197  5453  425  5777  257  5495  131  5789

$K=5914, S=29570$

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

По этому приближению получила новый шаблон из вычетов по модулю 4:

1  3  3  1  1  1  1  1  3  3 
3  3  3  1  1  1  1  1  3  1 
3  3  1  1  3  1  3  1  3  3 
1  3  1  3  1  1  3  1  3  1 
3  3  1  1  1  3  3  1  3  3 
3  3  1  3  3  1  1  1  3  3 
1  3  1  3  1  1  3  1  3  1 
3  3  1  3  1  3  1  1  3  3 
1  3  1  1  1  1  1  3  3  3 
3  3  1  1  1  1  1  3  3  1

Может, пригодится. Шаблонов таких очень много, наверное, можно сочинить.

Массив комплементарных пар простых чисел с константой комплементарности 5914 покажу:

11  17  47  53  71  101  107  113  131  173  197  257  263  383  431  443  521  563  617  641  653  677  
683  743  761  827  863  911  941  947  971  977  983  1097  1163  1181  1193  1223  1277  1367  1433  1451  
1493  1523  1697  1787  1823  1901  1907  1913  1997  2003  2063  2081  2111  2153  2213  2237  2243  2297  
2333  2357  2381  2423  2447  2543  2591  2657  2663  2693  2711  2777  2903  3011  3137  3203  3221  3251  
3257  3323  3371  3467  3491  3533  3557  3581  3617  3671  3677  3701  3761  3803  3833  3851  3911  3917  
4001  4007  4013  4091  4127  4217  4391  4421  4463  4481  4547  4637  4691  4721  4733  4751  4817  4931  
4937  4943  4967  4973  5003  5051  5087  5153  5171  5231  5237  5261  5273  5297  5351  5393  5471  5483  
5531  5651  5657  5717  5741  5783  5801  5807  5813  5843  5861  5867  5897  5903 

Вполне подходящий массив для построения идеального квадрата 10-го порядка, состоит из 73 комплементарных пар.

[Nataly-Mak]

Мне осталось представить образец идеального квадрата 16-го порядка из произвольных (различных) натуральных чисел.
Ну, тут тоже всё очень просто. Классические идеальные квадраты 16-го порядка существуют.
Берём любой из них и на его основе составляем квадрат из чисел любой арифметической прогрессии длины 256.
Я взяла для построения уникальный классический идеальный квадрат 16-го порядка, полученный мной из пандиагонального квадрата 16-го порядка Франклина (см. статью.
Арифметическую прогрессию взяла такую: $25+36n, n=0,1,...,255$.

Такой образец у меня получился:

25 8629 8089 8017 7549 2257 1789 2869 2329 6325 5785 5713 5245 4561 4093 565 
9133 673 1069 1285 1609 7045 7369 6433 6829 2977 3373 3589 3913 4741 5065 8737 
61 4597 4057 5749 5209 6289 5821 2833 2365 2293 1753 8053 7513 8593 8125 529 
9097 4705 5101 3553 3949 3013 3337 6469 6793 7009 7405 1249 1645 709 1033 8773 
241 8413 8305 7801 7765 2041 2005 2653 2545 6109 6001 5497 5461 4345 4309 349 
9061 745 997 1357 1537 7117 7297 6505 6757 3049 3301 3661 3841 4813 4993 8809 
277 4381 4273 5533 5425 6073 6037 2617 2581 2077 1969 7837 7729 8377 8341 313 
9025 4777 5029 3625 3877 3085 3265 6541 6721 7081 7333 1321 1573 781 961 8845 
385 8269 8449 7657 7909 1897 2149 2509 2689 5965 6145 5353 5605 4201 4453 205 
8917 889 853 1501 1393 7261 7153 6649 6613 3193 3157 3805 3697 4957 4849 8953 
421 4237 4417 5389 5569 5929 6181 2473 2725 1933 2113 7693 7873 8233 8485 169 
8881 4921 4885 3769 3733 3229 3121 6685 6577 7225 7189 1465 1429 925 817 8989 
457 8197 8521 7585 7981 1825 2221 2437 2761 5893 6217 5281 5677 4129 4525 133 
8701 1105 637 1717 1177 7477 6937 6865 6397 3409 2941 4021 3481 5173 4633 9169 
493 4165 4489 5317 5641 5857 6253 2401 2797 1861 2185 7621 7945 8161 8557 97 
8665 5137 4669 3985 3517 3445 2905 6901 6361 7441 6973 1681 1213 1141 601 9205

$K=9230, S=73840$

Осталось по этому образцу построить идеальный квадрат 16-го порядка из различных простых чисел
Константа ассоциативности вполне подходящая: имеем 133 комплементарные пары простых чисел с такой константой комплементарности.
Это последний образец. В конкурсе предлагается решить задачу до порядка 16 включительно.
Теперь пора заняться производством настоящих решений

[Nataly-Mak]

Приведу нижние границы для магических констант идеальных квадратов из различных простых чисел, которые уже прикинула (возможны ошибки, просьба к коллегам проверить):

$n=7, S=4487$
(было давно известно решение alexBlack с магической константой 5411; к началу конкурса я нашла решение с магической константой 4613; минимальность этого решения не доказана);

$n=8, S=2040$
(было давно известно моё решение с магической константой 2640; к началу конкурса я нашла решение с магической константой 2520; минимальность этого решения не доказана);

$n=9, S=11493$ центральный элемент 1277;
(известно решение alexBlack с магической константой 24237; минимальность решения не доказана); см. статью;

$n=11, S=24673$ центральный элемент 2243;

$n=13,S=49361$ центральный элемент 3797;

$n=15, S=74595$ центральный элемент 4973.

Для чётных порядков больше 8 пока не вычислила нижние границы, надо искать массивы комплементарных пар.

[Nataly-Mak]

Общая формула идеального квадрата 10-го порядка (альтернативная)

Схема идеального квадрата 10-го порядка

x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
x11 x12 x13 x14 x15 x16 x17 x18 x19 x20
x21 x22 x23 x24 x25 x26 x27 x28 x29 x30
x31 x32 x33 x34 x35 x36 x37 x38 x39 x40
x41 x42 x43 x44 x45 x46 x47 x48 x49 x50
k-x50 k-x49 k-x48 k-x47 k-x46 k-x45 k-x44 k-x43 k-x42 k-x41
k-x40 k-x39 k-x38 k-x37 k-x36 k-x35 k-x34 k-x33 k-x32 k-x31
k-x30 k-x29 k-x28 k-x27 k-x26 k-x25 k-x24 k-x23 k-x22 k-x21
k-x20 k-x19 k-x18 k-x17 k-x16 k-x15 k-x14 k-x13 k-x12 k-x11
k-x10 k-x9 k-x8 k-x7 k-x6 k-x5 k-x4 k-x3 k-x2 k-x1

Здесь k – константа ассоциативности квадрата, связана с магической константой квадрата S следующим соотношением: $S=5k$.

Система линейных уравнений, описывающих идеальный квадрат 10-го порядка по представленной схеме:

x1+x2+x3+x4+x5+x6+x7+x8+x9+x10=5k
x11+x12+x13+x14+x15+x16+x17+x18+x19+x20=5k
x21+x22+x23+x24+x25+x26+x27+x28+x29+x30=5k
x31+x32+x33+x34+x35+x36+x37+x38+x39+x40=5k
x41+x42+x43+x44+x45+x46+x47+x48+x49+x50=5k
x1+x11+x21+x31+x41-x50-x40-x30-x20-x10=0
x2+x12+x22+x32+x42-x49-x39-x29-x19-x9=0
x3+x13+x23+x33+x43-x48-x38-x28-x18-x8=0
x4+x14+x24+x34+x44-x47-x37-x27-x17-x7=0
x5+x15+x25+x35+x45-x46-x36-x26-x16-x6=0
x1+x20+x29+x38+x47-x45-x36-x27-x18-x9=0
x2+x11+x30+x39+x48-x44-x35-x26-x17-x8=0
x3+x12+x21+x40+x49-x43-x34-x25-x16-x7=0
x4+x13+x22+x31+x50-x42-x33-x24-x15-x6=0
x10+x11+x22+x33+x44-x46-x35-x24-x13-x2=0
x9+x20+x21+x32+x43-x47-x36-x25-x14-x3=0
x8+x19+x30+x31+x42-x48-x37-x26-x15-x4=0
x7+x18+x29+x40+x41-x49-x38-x27-x16-x5=0

Решаем эту систему и получаем следующую общую формулу идеального квадрата 10-го порядка

X(1) = X(43)- X(44)+ X(45)+2*X(46)+2*X(47)+ X(20)- X(21)+3*X(48)- X(22)+ X(2)+ X(15)+ X(13)+ X(27) + X(30)- X(31)+2*X(49)-10*K+ X(16)+ X(36)+2*X(37)+ X(38)+2*X(39)+ X(40) -2*X(8)+2*X(50) 
X(10) = - X(42)-2*X(44)+ X(46)+ X(47)+2*X(48)- X(22)+ X(2)+ X(15)+ X(13)+ X(27)+ X(11)+ X(49)-5*K + X(16)+ X(36)+2*X(37)+ X(38)+2*X(39)-2*X(8) 
X(12) = - X(42)+ X(44)- X(47)+ X(4)+ X(9)- X(20)- X(48)- X(2)- X(15)+ X(26)- X(11)- X(30)+ X(31) + X(34)+ X(35)+ X(36)+ X(8) 
X(14) = 2*X(42)- X(43)+ X(44)-2*X(46)-2*X(47)-2*X(4)-2*X(20)+ X(21)-4*X(48)+ X(22)- X(2) -2*X(15)-2*X(13)- X(26)- X(11)- X(29)+ X(31)-2*X(49)+15*K-2*X(16)- X(34) - X(36)-3*X(37)-2*X(38)-3*X(39)- X(40)+3*X(8)-2*X(50) 
X(17) = - X(44)+ X(48)+ X(2)- X(26)+ X(11)+ X(30)- X(35)+ X(39)- X(8) 
X(18) = X(43)- X(44)+2*X(46)+3*X(47)- X(9)+2*X(20)- X(21)+3*X(48)- X(22)+ X(2)+ X(15)+ X(13) + X(29)+ X(30)- X(31)+2*X(49)-10*K+ X(16)+2*X(37)+2*X(38)+2*X(39)+ X(40) -2*X(8)+2*X(50) 
X(19) = - X(42)+ X(4)+ X(48)+ X(15)+ X(26)- X(30)- X(31)+ X(37)- X(8) 
X(23) = (2*X(42)-2*X(43)+2*X(47)-2*X(4)-2*X(9)-2*X(21)-2*X(22)-2*X(13)-2*X(26) -2*X(27)-2*X(11)+5*K-2*X(16)+2*X(35)+2*X(38)+2*X(40)+2*X(8)) /2 
X(24) = - X(20)+ X(22)- X(15)+ X(27)+ X(11)- X(29)+ X(31)+ X(16)- X(35)+ X(36)- X(40) 
X(25) = -3*X(42)+ X(43)-2*X(44)+2*X(46)+2*X(47)+2*X(4)+ X(9)+3*X(20)+5*X(48)-2*X(22)+ X(2) +3*X(15)+2*X(13)+ X(26)+ X(11)+2*X(29)-2*X(31)+3*X(49)-15*K+ X(16) +4*X(37)+2*X(38)+4*X(39)+2*X(40)-4*X(8)+2*X(50) 
X(28) = -(-4*X(42)-4*X(44)+4*X(46)+6*X(47)+2*X(4)+4*X(20)+10*X(48)-2*X(22)+2*X(2) +4*X(15)+2*X(13)+2*X(26)+2*X(27)+2*X(11)+4*X(29)+2*X(30)-2*X(31) +6*X(49)-35*K+2*X(16)+2*X(36)+8*X(37)+6*X(38)+8*X(39)+4*X(40) -6*X(8)+4*X(50)) /2 
X(3) = X(43)+ X(20)+ X(48)+ X(15)+ X(11)- X(31)+ X(16)- X(35)- X(36)- X(40)- X(8) 
X(32) = - X(42)- X(44)+ X(47)+ X(20)+2*X(48)- X(22)+2*X(15)+ X(11)+ X(29)-2*X(31)+ X(49)- X(34) - X(35)- X(36)+ X(37)+ X(39)-2*X(8) 
X(33) = X(42)+ X(44)- X(47)- X(20)-2*X(48)+ X(22)-2*X(15)- X(11)- X(29)+ X(31)- X(49)+5*K -2*X(37)- X(38)-2*X(39)- X(40)+2*X(8) 
X(41) = - X(42)- X(43)- X(44)- X(45)- X(46)- X(47)- X(48)- X(49)+5*K- X(50) 
X(5) = X(42)- X(43)+ X(44)- X(45)- X(46)- X(47)- X(4)- X(9)- X(20)-3*X(48)+ X(22)- X(2)-2*X(15)- X(13) - X(27)- X(11)+ X(31)-2*X(49)+10*K- X(16)-2*X(37)- X(38)-2*X(39)+2*X(8) - X(50) 
X(6) = -2*X(42)- X(44)+ X(47)+ X(4)+2*X(20)+2*X(48)- X(22)+2*X(15)+ X(13)- X(27)+2*X(29)- X(31) + X(49)-5*K- X(16)+ X(35)- X(36)+2*X(37)+ X(38)+2*X(39)+2*X(40)-2*X(8) + X(50) 
X(7) = 2*X(42)- X(43)+3*X(44)-2*X(46)-3*X(47)- X(4)-3*X(20)+ X(21)-5*X(48)+2*X(22)-2*X(2) -3*X(15)-2*X(13)- X(11)-2*X(29)- X(30)+2*X(31)-2*X(49)+15*K- X(16) -4*X(37)-2*X(38)-4*X(39)-2*X(40)+4*X(8)-2*X(50)

При заданной константе ассоциативности K имеем 32 свободные переменные из 50.
Точно так же и в общей формуле, полученной по программе svb (показана выше). Однако формулы получились разные. Вот и думаю-гадаю: какая формула эффективнее

Проверяю формулу. Задаю произвольные значения константы ассоциативности и свободных элементов квадрата:

K=5914:X(50)=4547:X(49)=1367:X(48)=4817:X(47)=1223:X(46)=4637:X(45)=1097
X(44)=4751:X(43)=1277:X(42)=4937:X(8)=5717:X(40)=2297
X(39)=3671:X(38)=1997:X(37)=3761:X(36)=2213:X(35)=4001:X(34)=2003:X(16)=863:X(31)=4013
X(30)=1433:X(29)=4463:X(11)=5351:X(27)=4391:X(26)=1493:X(13)=5051:X(15)=5297:X(2)=5783:X(22)=1787
X(21)=4091:X(20)=947:X(9)=443:X(4)=5657

Вычислив по формуле зависимые элементы квадрата, получаю следующий идеальный квадрат 10-го порядка:

293 5783 311 5657 155 5453 317 5717 443 5441
5351 503 5051 761 5297 863 5093 779 4925 947
4091 1787 4553 1613 4109 1493 4391 1637 4463 1433
4013 1859 3755 2003 4001 2213 3761 1997 3671 2297
917 4937 1277 4751 1097 4637 1223 4817 1367 4547
1367 4547 1097 4691 1277 4817 1163 4637 977 4997
3617 2243 3917 2153 3701 1913 3911 2159 4055 1901
4481 1451 4277 1523 4421 1805 4301 1361 4127 1823
4967 989 5135 821 5051 617 5153 863 5411 563
473 5471 197 5597 461 5759 257 5603 131 5621

$K=5914, S=29570$

Неплохое решение. Значения свободных элементов я задала так, что все они простые числа из массива комплементарных пар с данной константой комплементарности. Следовательно, в квадрате как минимум 64 элемента являются простыми числами в нужном диапазоне. Зависимые элементы тоже все в нужном диапазоне (нет отрицательных элементов). Но, к сожалению, есть повторение чисел. Ну, и среди зависимых элементов много не простых чисел.

[Nataly-Mak]

А вот и головоломка подоспела об идеальных магических квадратах из простых чисел:
http://www.primepuzzles.net/puzzles/puzz_777.htm

У Carlos Rivera всё чётко по плану.
Решаем, господа
Всё сразу - в одном пакете: и головоломка, и конкурс.

[Nataly-Mak]

Написала новую программу по показанной выше общей формуле идеального квадрата 10-го порядка.
Применила новую эвристику. Небольшой прогресс имеется
Это решение с 6 дырками получено за несколько минут:

5897 11 4007 2777 2591 2657 4319* 47 4013 3251
53 5153 131 4967 1433 5237 2081 5195* 383 4937
5657 521 4523* 2237 5483 71 5051 263 3221 2543
5351 1787 2357 1913 4091 2153 3917 2063 3491 2447
941 4817 1493 4751 983 4463 1277 4943 1181 4721
1193 4733 971 4637 1451 4931 1163 4421 1097 4973
3467 2423 3851 1997 3761 1823 4001 3557 4127 563
3371 2693 5651 863 5843 431 3677 1391* 5393 257
977 5531 719* 3833 677 4481 947 5783 761 5861
2663 1901 5867 1595* 3257 3323 3137 1907 5903 17

$K=5914, S=29570$

Неправильные элементы помечены звёздочкой.
В решении нет повторений, все числа в нужном диапазоне. Чуть-чуть не получилось, обидно. Среди неправильных элементов есть даже два простых числа – 719 и 4523, но соответствующие им комплементарные числа не простые (5195 и 1391).

Вполне вероятно, что решение с такой константой ассоциативности существует.

[Nataly-Mak]

Здесь Jarek описал свой алгоритм построения пандиагональных квадратов, который он применил в конкурсе по пандиагональным квадратам из простых чисел.
Я даже и не пыталась вникнуть в это описание по причине незнания языка.
Идея такая: нельзя ли применить этот же алгоритм для построения идеальных квадратов

Предлагаю коллегам попробовать. Ведь для идеальных квадратов всё должно быть проще из-за ассоциативности.
Jarek составлял пандиагональные квадраты из простых чисел виртуозно!

[Nataly-Mak]

Немножко покрутила последнюю программу для идеального квадрата 10-го порядка, чтобы посмотреть – будет ли прогресс. Малюсенькое продвижение есть: получила решение с 4 дырками (предыдущее было с 6 дырками).

5651 761 3671 5273 173 2111 1607* 5231 3011 2081
5351 977 5843 47 5003 2693 5657 1985* 2003 11
653 2591 4217 4007 1223 53 3533 5393 2663 5237
1901 3203 4391 1913 4091 2153 3917 2063 3491 2447
941 4817 1493 4751 983 4463 1277 4943 1181 4721
1193 4733 971 4637 1451 4931 1163 4421 1097 4973
3467 2423 3851 1997 3761 1823 4001 1523 2711 4013
677 3251 521 2381 5861 4691 1907 1697 3323 5261
5903 3911 3929* 257 3221 911 5867 71 4937 563
3833 2903 683 4307* 3803 5741 641 2243 5153 263

$K=5914, S=29570$
Всего две неправильные комплементарные пары: (1607, 4307) и (1985, 3929). При этом в каждой паре одно число является простым. Формально в решении только 2 дырки, но фактически 4.

Крутить ли дальше программу? Будет полное решение
Наверное, сие одному Богу известно, наука вряд ли сможет дать ответ на мой вопрос. Может быть, кто-нибудь попытается?

А кто-нибудь умеет с дырками бороться? Тут, в теме разные теории есть на этот счёт. О блуждающей дырке, например. Все бойцы и борцы куда-то пропали