Антимагические квадраты

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Nataly-Mak в сообщении #577916 писал(а):

Someone в сообщении #577600 писал(а):

Для квадрата порядка 10 время решения системы уравнений вполне может составить несколько сотен часов.

Ну, я, пожалуй, могу решить быстрее

Посмотрела на все решения, очень они похожи, как одна мать родила :-)

Итак, я обещала решить задачу нахождения общей формулы для квадратов Стенли 10-го порядка :-)

Давно уж это было, но вот я вернулась к квадратам Стенли и активно ими занимаюсь сейчас.
Для начала приведу общую формулу квадратов Стенли 10-го порядка, полученную по алгоритму составлению примитивного квадрата по Россеру.
Если же решать систему уравнений, это будет система из 10! (10 факториал) уравнений со 101 неизвестными. Хорошая система :-)

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

Код:

x12 = x2 + x11 - x1
x13 = x3 + x12 - x2
. . . . . . . . . . .  
x20 = x10 + x19 - x9
x22 = x12 + x21 - x11
x23 = x13 + x22 - x12
. . . . . . . . . . .
x30 = x20 + x29 - x19
x32 = x22 + x31 - x21
x33 = x23 + x32 - x22
. . . . . . . . . . . 
x40 = x30 + x39 - x29
x42 = x32 + x41 - x31
x43 = x33 + x42 - x32
. . . . . . . . . . .
x50 = x40 + x49 - x39
x52 = x42 + x51 - x41
x53 = x43 + x52 - x42
. . . . . . . . . . .
x60 = x50 + x59 - x49
x62 = x52 + x61 - x51
x63 = x53 + x62 - x52
. . . . . . . . . . .
x70 = x60 + x69 - x59
x72 = x62 + x71 - x61
x73 = x63 + x72 - x62
. . . . . . . . . . .
x80 = x70 + x79 - x69
x82 = x72 + x81 - x71
x83 = x73 + x82 - x72
. . . . . . . . . . .
x90 = x80 + x89 - x79
x91 = x101 - x10 - x19 - x28 - x37 - x46 - x55 - x64 - x73 - x82
x92 = x82 + x91 - x81
x93 = x83 + x92 - x82
. . . . . . . . . . .
x100 = x90 + x99 - x89

Чтобы немного сократить формулу, я сделала пропуски, где аналогия очевидна.
В формуле $x_i$ (i = 1,2,3,...,100) обозначают элементы квадрата, $x_{101}$ - индекс квадрата.
Поскольку я составляю квадраты Стенли из простых чисел, элементы квадрата у меня - попарно различные простые числа.
Можно составлять квадраты Стенли из произвольных натуральных чисел или, например, из чисел Смита. Как уже отмечалось выше, из чисел от 1 до n^2 квадраты Стенли составляются тривиально.

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

Код:

23 41 53 107 353 443 1427 1973 24077
29 47 59 113 359 449 1433 1979 24083
43 61 73 127 373 463 1447 1993 24097
79 97 109 163 409 499 1483 2029 24133
149 167 179 233 479 569 1553 2099 24203
193 211 223 277 523 613 1597 2143 24247
263 281 293 347 593 683 1667 2213 24317
4253 4271 4283 4337 4583 4673 5657 6203 28307
5419 5437 5449 5503 5749 5839 6823 7369 29473
6269 6287 6299 6353 6599 6689 7673 8219 30323

Индекс очень большой. Требуется найти квадрат Стенли с меньшим индексом.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Выполнилась программа построения квадрата Стенли 7-го порядка с индексом 1595 из простых чисел; в программе задействован массив из 120 простых чисел. Решение не найдено. Это был полный перебор с возвратом; алгоритм сделан по принципу построения примитивного квадрата.
Итак, можно с некоторой уверенностью утверждать, что регулярного пандиагонального квадрата 7-го порядка с магической константой 1595 не существует.
Такими черепашьими темпами продвигаюсь в решении этой задачи.

Параллельно решаю задачу построения четырёх квадратов Стенли 5-го порядка с одинаковым индексом, составленных из различных простых чисел. Написала несколько программ построения квадрата Стенли 5-го порядка. Последняя версия работает уже довольно быстро. В этой версии задаётся конкретный индекс, остаётся всего 8 свободных переменных, программа "летает". Однако надо построить не один квадрат, а четыре, при этом все одни не должны содержать одинаковых чисел. И вот эта задача, увы, не решается.
Три квадрата строятся легко, четвёртый квадрат не хочет составляться :-(

Нужно делать программу, состоящую из 4 модулей (один модуль - это составление одного квадрата). К сожалению, я совсем забыла модульное программирование :cry:

Где искать помощи?

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Нашла квадраты Стенли из чисел Смита с минимальными индексами для порядков 2 - 4.
Квадрат порядка 5 был известен давно, его нашёл Pavlovsky, когда строил наименьшие пандиагональные квадраты 5-го порядка по Россеру.

Код:

n=2, индекс 143
22  58  
85  121 

n=3, индекс 669
22  58  202 
85  121  265 
346  382  526 

n=4, индекс 2088
85  94  121  517  
346  355  382  778 
526  535  562  958  
654  663  690  1086 

n=5, индекс 8318 (автор Pavlovsky)
58  121  382  562  1111 
202  265  526  706  1255 
454  517  778  958  1507 
1858  1921  2182  2362  2911 
3802  3865  4126  4306  4855

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

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

Код:

121 382 562 23818 37678 54418
265 526 706 23962 37822 54562
517 778 958 24214 38074 54814
1921 2182 2362 25618 39478 56218
16285 16546 16726 39982 53842 70582
180022 180085 180346 180526 203782 217642 234382
381298 381361 381622 381802 405058 418918 435658

Индекс этого квадрата Стенли равен 696745.
Требуется найти квадрат Стенли с меньшим индексом, в идеале - с минимальным.

Если удалить в этом квадрате последнюю строку и последний столбец, получится квадрат Стенли порядка 6 из чисел Смита с индексом 261087. Тоже огромный индекс. Как найти квадрат с меньшим индексом :?:

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Немножко оптимизировала программу поиска квадратов Стенли 6-го порядка.
И вот первое улучшение - квадрат из чисел Смита с индексом 184272:

Код:

58  85  166  526  1858  44518  
94  121  202  562  1894  44554  
9166  9193  9274  9634  10966  53626  
37795  37822  37903  38263  39595  82255  
39478  39505  39586  39946  41278  83938  
50818  50845  50926  51286  52618  95278 
S=184272

Пришлось задействовать массив смитов, состоящий из более 3000 чисел. При этом не задаю конкретный индекс, а только верхнюю границу для него.
Теперь эта граница будет 184272; в предыдущем прогоне программы задала верхнюю границу 261087 (по известному квадрату).

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

И ещё целый ряд улучшений, самый маленький индекс пока получился 85047:

Код:

22  58  202  454  3442  38578  
85  121  265  517  3505  38641  
526  562  706  958  3946  39082  
2182  2218  2362  2614  5602  40738  
12226  12262  12406  12658  15646  50782  
27382  27418  27562  27814  30802  65938 
S=85047

Уже неплохо

Напомню, что наименьший пандиагональный квадрат 6-го порядка из чисел Смита имеет магическую константу 5100.
Однако для порядка 6 нет связи между пандиагональными и примитивными квадратами (квадратами Стенли). Во всяком случае, я не знаю такой связи.

Эх, когда же сюда Pavlovsky заглянет?

Он утверждал в начале темы, что нет тут никаких сложных задач. А вот я никак не могу найти наименьший квадрат Стенли 6-го порядка из чисел Смита :-(

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Ещё удача

Код:

319  346  526  4126  5818  15646  
355  382  562  4162  5854  15682  
958  985  1165  4765  6457  16285  
2578  2605  2785  6385  8077  17905  
3595  3622  3802  7402  9094  18922  
10579  10606  10786  14386  16078  25906 
S=43251

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

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

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

На этом пока удача кончилась :-(

Дальше программа работает очень и очень долго, хотя в массиве теперь всего 628 чисел Смита. Прекращаю на время поиск наименьшего квадрата Стенли 6-го порядка из чисел Смита.

В своей давней статье нашла квадраты Стенли порядков 8 - 11 из простых чисел.

Код:

n=8
37 107 151 277 359 571 2221
67 137 181 307 389 601 2251
97 167 211 337 419 631 2281
109 179 223 349 431 643 2293
127 197 241 367 449 661 2311
157 227 271 397 479 691 2341
199 269 313 439 521 733 2383
769 839 883 1009 1091 1303 2953
S=5000

n=9
37 107 151 277 359 571 2221 3271
67 137 181 307 389 601 2251 3301
97 167 211 337 419 631 2281 3331
109 179 223 349 431 643 2293 3343
127 197 241 367 449 661 2311 3361
157 227 271 397 479 691 2341 3391
199 269 313 439 521 733 2383 3433
769 839 883 1009 1091 1303 2953 4003
1549 1619 1663 1789 1871 2083 3733 4783
S=9783

n=10
23 41 53 107 353 443 1427 1973 24077
29 47 59 113 359 449 1433 1979 24083
43 61 73 127 373 463 1447 1993 24097
79 97 109 163 409 499 1483 2029 24133
149 167 179 233 479 569 1553 2099 24203
193 211 223 277 523 613 1597 2143 24247
263 281 293 347 593 683 1667 2213 24317
4253 4271 4283 4337 4583 4673 5657 6203 28307
5419 5437 5449 5503 5749 5839 6823 7369 29473
6269 6287 6299 6353 6599 6689 7673 8219 30323
S=44998

n=11
23 41 53 107 353 443 1427 1973 24077 59387
29 47 59 113 359 449 1433 1979 24083 59393
43 61 73 127 373 463 1447 1993 24097 59407
79 97 109 163 409 499 1483 2029 24133 59443
149 167 179 233 479 569 1553 2099 24203 59513
193 211 223 277 523 613 1597 2143 24247 59557
263 281 293 347 593 683 1667 2213 24317 59627
4253 4271 4283 4337 4583 4673 5657 6203 28307 63617
5419 5437 5449 5503 5749 5839 6823 7369 29473 64783
6269 6287 6299 6353 6599 6689 7673 8219 30323 65633
93979 93997 94009 94063 94309 94399 95383 95929 118033 153343
S=198341

Из последнего квадрата построен с помощью преобразования Россера пандиагональный квадрат 11-го порядка. Это наименьший на сегодня квадрат.

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

-- Ср янв 16, 2013 18:48:05 --

Задача построения пандиагонального квадрата 10-го порядка из четырёх квадратов Стенли 5-го порядка

Теперь хочу подробно описать указанную задачу. Действительно: задача понятна мне и моим коллегам, которые занимались данной проблемой, но мало понятна (или совсем не понятна) другим форумчанам.
Начну с известного пандиагонального квадрата 10-го порядка из простых чисел, построенного данным методом (по решёткам Россера), автор квадрата Pavlovsky.
Вы видите этот квадрат на иллюстрации:

Магическая константа этого пандиагонального квадрата равна 3594.
Квадрат построен из четырёх пандиагональных квадратов 5-го порядка с одинаковой магической константой 1797, составленных из различных простых чисел. Квадраты 5-го порядка размещаются в матрице 10х10 по решёткам Россера. Чтобы лучше понять, где эти решётки, я выписала все квадраты 5-го порядка из каждой решётки:

Если вы посмотрите на пандиагональный квадрат 10-го порядка, а потом на 4 пандиагональных квадрата 5-го порядка, хорошо поймёте, как заполняется матрица 10х10 по решёткам Россера.

Теперь с помощью преобразования, обратного преобразованию Россера, превращаем 4 пандиагональных квадрата 5-го порядка в 4 примитивных квадрата (или - что то же - 4 квадрата Стенли):

Код:

7  13  19  139  857 
31  37  43  163  881 
61  67  73  193  911 
97  103  109  229  947 
601  607  613  733  1451

11  17  149  227  281 
131  137  269  347  401 
251  257  389  467  521 
271  277  409  487  541 
503  509  641  719  773 

127  151  167  211  307 
157  181  197  241  337 
199  223  239  283  379 
439  463  479  523  619 
547  571  587  631  727

23  29  53  313  431 
41  47  71  331  449 
83  89  113  373  491 
353  359  383  643  761 
563  569  593  853  971

Все эти квадраты Стенли 5-го порядка имеют одинаковый индекс 1797.

Вот, собственно, и всё.
Понятно. что задача свелась к построению четырёх квадратов Стенли 5-го порядка из различных простых чисел с одинаковым индексом. Pavlovsky нашёл такие квадраты Стенли с индексом 1797 и построил таким образом пандиагональный квадрат 10-го порядка с магической константой 3594.

Теперь я пытаюсь найти 4 квадрата Стенли 5-го порядка из различных простых чисел с меньшим индексом. Ближайший меньший индекс 1795.
Квадратов Стенли с таким индексом строится очень много. Но! нам надо иметь комплект из 4-х квадратов, составленных из различных чисел. В этом сложность задачи.
Комплекты из 3-х квадратов находятся довольно легко, а вот четвёртый квадрат никак.

Пример комплекта их 3-х квадратов с индексом 1795:

Код:

Квадрат №1
5  7  17  373  1063 
 11  13  23  379  1069 
 29  31  41  397  1087 
 71  73  83  439  1129 
 239  241  251  607  1297 

Квадрат №2
3  47  59  89  179 
 53  97  109  139  229 
 137  181  193  223  313 
 557  601  613  643  733 
 683  727  739  769  859 

Квадрат №3
43  67  197  227  487 
 79  103  233  263  523 
 127  151  281  311  571 
 307  331  461  491  751 
 433  457  587  617  877 

Если что-то упустила в описании, пожалуйста, спрашивайте.

У меня есть программа построения квадратов Стенли 5-го порядка с заданным индексом. Она работает достаточно быстро.
Я действую так. Строю первый квадрат, выбрасываю из массива простых чисел те числа, из которых составлен этот квадрат; строю второй квадрат и т.д.
Тут многое зависит оттого, каким будет первый квадрат. А потом и оттого, каким будет второй квадрат.
По-хорошему надо делать одну программу, чтобы она выполняла все этапы - построение всех 4-х квадратов; если построить четвёртый квадрат не удаётся, возвращаемся на начало и всё начинаем снова - с построения первого квадрата, но уже другого. А, может быть, не на начало возвращаемся, а на построение второго квадрата или даже третьего. Тут такие вложенные циклы получаются. Теоретически я представляю весь процесс, а реализовать не могу. Поэтому действую примитивно, выполняя каждый этап отдельно.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Ещё два примера.
Комплект из 3-х квадратов Стенли 5-го порядка из различных простых чисел с индексом 1793:

Код:

№1
5  7  17  103  563 
11  13  23  109  569 
29  31  41  127  587 
269  271  281  367  827 
809  811  821  907  1367 

№2
19  37  47  89  359 
43  61  71  113  383 
79  97  107  149  419 
163  181  191  233  503 
1033  1051  1061  1103  1373 

№3
67  83  179  223  509 
151  167  263  307  593 
241  257  353  397  683 
277  293  389  433  719 
331  347  443  487  773

Комплект из 3-х квадратов Стенли 5-го порядка из различных простых чисел с индексом 1765:

Код:

№1
3  5  53  131  173 
11  13  61  139  181 
101  103  151  229  271 
641  643  691  769  811 
659  661  709  787  829 

№2
7  17  31  167  607 
19  29  43  179  619 
73  83  97  233  673 
433  443  457  593  1033 
439  449  463  599  1039 

№3
23  71  137  227  491 
109  157  223  313  577 
163  211  277  367  631 
283  331  397  487  751 
353  401  467  557  821

Пробовала для нескольких индексов искать комплекты. Для некоторых не удалось найти даже третий квадрат, например, для индекса 1589. Два квадрата - вот они:

Код:

№1
3  7  31  43  73  
13  17  41  53  83  
223  227  251  263  293  
439  443  467  479  509  
769  773  797  809  839 

№2
5  11  41  83  521  
53  59  89  131  569  
61  67  97  139  577  
101  107  137  179  617  
733  739  769  811  1249

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

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

Код:

319  346  1642  1678  1966  3226  
535  562  1858  1894  2182  3442  
1255  1282  2578  2614  2902  4162  
3595  3622  4918  4954  5242  6502  
4279  4306  5602  5638  5926  7186  
13639  13666  14962  14998  15286  16546 
S=30885

Предыдущий индекс у меня был 43251.
И опять программа надолго задумалась, когда задала верхнюю границу 30885.
Надо искать новые оптимизации. В массиве сейчас осталось 464 числа, это ещё очень много для полного перебора.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Продолжаю битву за квадрат Стенли 6-го порядка из чисел Смита с минимальным индексом :-)

Трудная борьба... какие только подходы я ни использовала!
Вот, например, найдены такие полуфабрикаты:

Код:

 346  706  1966  2362  3046  0 
 22  382  1642  2038  2722  0 
 202  562  1822  2218  2902  0 
 895  1255  2515  2911  3595  0 
 274  634  1894  0  2974  0 
 0  0  0  0  0  3091 
S=11526

Добавляю ещё один элемент квадрата, теперь такое решение нашлось:

Код:

 346  526  1219  1282  4126  0 
 985  1165  1858  1921  4765  0 
 1642  1822  2515  2578  5422  0 
 2038  2218  2911  2974  5818  0 
 22  202  895  958  3802  0 
 0  0  0  0  0  3865 
S=14667

Теперь осталось добавить один элемент (свободный, то есть он задаётся произвольно) и вычислить остальные элементы (зависимые). Что получится? Наверняка, индекс 14667 уже не получится :-(

К тому же, время выполнения программы намного увеличится, так как добавится ещё один вложенный цикл (по последнему свободному элементу).

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Смотрите, как вгрызаюсь в задачу... Это не проще, чем факториалы

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

Код:

 346  526  1219  1282  4126  5539 
 985  1165  1858  1921  4765  6178 
 1642  1822  2515  2578  5422  0 
 2038  2218  2911  2974  5818  0 
 22  202  895  958  3802  0 
 0  0  0  0  0  3865 
S=14667

Осталось всего 8 элементов не найдено, все они уже зависимые. То есть сейчас их можно вычислить - без проверки на принадлежность множеству чисел Смита - и квадрат готов. Но надо, чтобы все они были числами Смита!

И ещё шаг - добавила один элемент:

Код:

 346  526  1219  1282  4126  5539 
 985  1165  1858  1921  4765  6178 
 1642  1822  2515  2578  5422  6835 
 2038  2218  2911  2974  5818  0 
 22  202  895  958  3802  0 
 0  0  0  0  0  3865 
S=14667

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

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Построила такой квадратик Стенли 6-го порядка с индексом 15999:

Всё замечательно, кроме того, что 7 элементов этого квадрата не числа Смита (эти элементы выделены синим цветом).
Уменьшить индекс 30885 мне так и не удалось.
Нужны принципиально новые подходы. Известный алгоритм, которым я пользуюсь, в этом случае буксует, хотя прекрасно справился с квадратом Стенли 6-го порядка из простых чисел, тут удалось выполнить полный перебор и доказать, что минимальный индекс равен 774.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

В OEIS опубликована статья об антимагических квадратах Стенли из простых чисел с минимальным индексом
A210710.

Итак, до порядка 6 минимальность индекса доказана.
Найдены квадраты Стенли из простых чисел порядков 7 - 11 (все они приведены в теме), но для этих порядков минимальность индекса не доказана.

Кто готов доказать? :wink:

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

На сайте primepuzzles.net оубликована головоломка о квадратах Стенли из простых чисел:
http://www.primepuzzles.net/puzzles/puzz_681.htm

К сожалению, новый конкурс программистов прервал мою работу над квадратами Стенли.
Я планировала написать статью об этих квадратах для своего сайта. Интереснейшие квадраты!
Карлос (автор указанного сайта) ими восхищён :-)

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

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

И первый отклик на головоломку о квадратах Стенли.
Его прислал Ярек Вроблевский.
Поразительно!
http://tech.groups.yahoo.com/group/prim ... sage/19733

Найденные им арифметические прогрессии из простых чисел дают возможность построить квадраты Стенли до порядка 20 включительно.

Правда, эти квадраты не с минимальными индексами, но всё равно они чрезвычайно интересны.
Наверное, можно будет построить пандиагональные квадраты порядков 17 и 19 из простых чисел (из квадратов Стенли соответствующих порядков), которые мне до сих пор построить не удалось.

Надо внимательно рассмотреть эти прогрессии, подумать.

Научный форум dxdy

Антимагические квадраты

Кто сейчас на конференции