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

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

Предлагаю ещё три примитивных прямоугольника 12х13, в этих прямоугольниках надо достроить одну строку.

№ 1

Код:

823  1109  3203  5003  5623  6793  9209  11399  177013  182653  233669  294773  429083
1237  1523  3617  5417  6037  7207  9623  11813  177427  183067  234083  295187  429497
1621  1907  4001  5801  6421  7591  10007  12197  177811  183451  234467  295571  429881
5857  6143  8237  10037  10657  11827  14243  16433  182047  187687  238703  299807  434117
7753  8039  10133  11933  12553  13723  16139  18329  183943  189583  240599  301703  436013
8713  8999  11093  12893  13513  14683  17099  19289  184903  190543  241559  302663  436973
12241  12527  14621  16421  17041  18211  20627  22817  188431  194071  245087  306191  440501
13627  13913  16007  17807  18427  19597  22013  24203  189817  195457  246473  307577  441887
17203  17489  19583  21383  22003  23173  25589  27779  193393  199033  250049  311153  445463
127747  128033  130127  131927  132547  133717  136133  138323  303937  309577   360593  421697  556007
598867  599153  601247  603047  603667  604837  607253  609443  775057  780697  831713  892817  1027127
740227  740513  742607  744407  745027  746197  748613  750803  916417  922057  973073  1034177  1168487

№ 2

Код:

1109 3203 5003 5623 6793 9209 26479 50789 63443 479209 852689 1154819
1277 3371 5171 5791 6961 9377 26647 50957 63611 479377 852857 1154987
1523 3617 5417 6037 7207 9623 26893 51203 63857 479623 853103 1155233
6143 8237 10037 10657 11827 14243 31513 55823 68477 484243 857723 1159853
8039 10133 11933 12553 13723 16139 33409 57719 70373 486139 859619 1161749
8999 11093 12893 13513 14683 17099 34369 58679 71333 487099 860579 1162709
12527 14621 16421 17041 18211 20627 37897 62207 74861 490627 864107 1166237
17489 19583 21383 22003 23173 25589 42859 67169 79823 495589 869069 1171199
34667 36761 38561 39181 40351 42767 60037 84347 97001 512767 886247 1188377
160591 160877 162971 164771 165391 166561 168977 186247 210557 223211 638977 1012457 1314587
493693 493979 496073 497873 498493 499663 502079 519349 543659 556313 972079 1345559 1647689
843757 844043 846137 847937 848557 849727 852143 869413 893723 906377 1322143 1695623 1997753

№ 3

Код:

1109 3203 5003 5623 6793 9209 26479 50789 63443 852689 1154819 1541963
1277 3371 5171 5791 6961 9377 26647 50957 63611 852857 1154987 1542131
1523 3617 5417 6037 7207 9623 26893 51203 63857 853103 1155233 1542377
6143 8237 10037 10657 11827 14243 31513 55823 68477 857723 1159853 1546997
8039 10133 11933 12553 13723 16139 33409 57719 70373 859619 1161749 1548893
8999 11093 12893 13513 14683 17099 34369 58679 71333 860579 1162709 1549853
12527 14621 16421 17041 18211 20627 37897 62207 74861 864107 1166237 1553381
17489 19583 21383 22003 23173 25589 42859 67169 79823 869069 1171199 1558343
34667 36761 38561 39181 40351 42767 60037 84347 97001 886247 1188377 1575521
160591 160877 162971 164771 165391 166561 168977 186247 210557 223211 1012457 1314587 1701731
623431 623717 625811 627611 628231 629401 631817 649087 673397 686051 1475297 1777427 2164571
843757 844043 846137 847937 848557 849727 852143 869413 893723 906377 1695623 1997753 2384897

Вместе с приведённым выше прямоугольником 13х12 имеем 4 кандидата в пандиагональный квадрат 13-го порядка с меньшей магической константой.

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

Ага! Нету смелых связываться с дьявольским квадратом 13-го порядка :-)

Да, это непростой квадратик. Решила немного отдохнуть от него.

Взяла найденный мной набор комплементарных пар простых чисел, состоящий из 266 пар. Из чисел этого набора построен совершенный квадрат 6-го порядка. Константа комплементарности (сумма чисел в паре) равна 9930.
Из этого набора у меня построилось 23 пандиагональных квадрата 4-го порядка из различных чисел.
Ну, пандиагональные квадраты 8-го и 12-го порядков из простых чисел уже построены, так что строю пандиагональный квадрат 16-го порядка по решёткам Россера:

Код:

23 47 71 9887 9901 9871 9857 9697 4993 5659 5281 269 4943 4283 4651
101 181 197 9833 9791 9739 9719 5227 6907 5711 5347 4721 3061 4229 4597
281 307 317 9679 9619 9551 9547 7079 5437 7789 5573 2861 4523 2213 4423
439 463 467 9497 9473 9343 9337 5417 7507 6287 5147 4549 2441 3767 4909
6967 7309 7549 163 2969 2633 2383 113 1997 1697 2339 9781 7927 8221 7589
7687 7583 6373 4091 2281 2357 3571 709 881 2053 1223 9203 9011 7867 8693
6793 8699 6053 2693 3167 1303 3943 409 1637 1217 797 9511 8263 8641 9067
7559 7253 6337 2953 2389 2801 3719 1993 491 1429 1657 7901 9421 8377 8147
4937 4271 4649 9661 4987 5647 5279 9923 9907 9883 9859 43 29 59 73
3023 4219 4583 5209 6869 5701 5333 9851 9829 9749 9733 97 139 191 211
4493 2141 4357 7069 5407 7717 5507 9689 9649 9623 9613 251 311 379 383
2423 3643 4783 5381 7489 6163 5021 9533 9491 9467 9463 433 457 587 593
7933 8233 7591 149 2003 1709 2341 127 2963 2621 2381 9767 6961 7297 7547
9049 7877 8707 727 919 2063 1237 4073 2243 2347 3557 5839 7649 7573 6359
8293 8713 9133 419 1667 1289 863 2683 3137 1231 3877 7237 6763 8627 5987
9439 8501 8273 2029 509 1553 1783 2917 2371 2677 3593 6977 7541 7129 6211

Магическая константа квадрата равна 79440. Думаю, что это не наименьшая константа.
Для построения пандиагонального квадрата 20-го порядка не хватило двух квадратов 4-го порядка.

Вот так просто строится пандиагональный квадрат 16-го порядка из простых чисел, а вот квадрат следующего 17-го порядка так просто, наверное, не построить. Хотя алгоритм я предложила, он работает. Но надо строить очень большие матрицы методом смешанного достраивания, затем использовать программу для выделения из этой матрицы квадрата 17х17, состоящего из единиц. Тоже в общем-то всё просто.

maxal · 11/01/06 5660

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

Предлагаю ещё три примитивных прямоугольника 12х13, в этих прямоугольниках надо достроить одну строку.

Наименьшие строки таковы:

№1:

Код:

1622748571, 1622748857, 1622750951, 1622752751, 1622753371, 1622754541, 1622756957, 1622759147, 1622924761, 1622930401, 1622981417, 1623042521, 1623176831

№2:

Код:

96059563, 96059849, 96061943, 96063743, 96064363, 96065533, 96067949, 96085219, 96109529, 96122183, 96537949, 96911429, 97213559

№3:

Код:

2939096227, 2939096513, 2939098607, 2939100407, 2939101027, 2939102197, 2939104613, 2939121883, 2939146193, 2939158847, 2939948093, 2940250223, 2940637367

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

Так во втором вроде неплохо получилось. Сейчас посмотрю, какой там квадрат получится.

А вот ещё один пандиагональный квадрат 16-го порядка из простых чисел с магической константой 48048, он построен из набора комплементарных пар, из которого построился совершенный квадрат 8-го порядка. В наборе 195 пар. И чисел этого набора у меня построилось 19 пандиагональных квадратов 4-го порядка из различных чисел.

Код:

67 83 109 5953 5927 5903 5879 3203 3049 3229 3547 2837 2969 2797 2477
139 157 179 5857 5843 5839 5813 3359 3187 3467 4423 2659 2843 2549 1597
223 227 317 5743 5737 5749 5623 3917 3299 3907 4139 2153 2753 2129 1933
433 523 607 5563 5347 5443 5209 3863 4229 3413 3803 2239 2003 2633 2393
3319 3739 4007 1787 2699 2287 2017 1069 337 593 569 4903 5657 5393 5419
4507 4349 4597 2309 1523 1667 1423 487 1459 1039 353 5507 4523 4957 5639
3389 4129 4789 1733 2663 1907 1283 619 313 449 967 5323 5647 5527 4973
4793 3623 4283 2083 1439 2423 1913 503 997 733 1087 5407 4783 5233 4729
2957 2777 2459 3169 3037 3209 3529 5987 5939 5923 5897 53 79 103 127
2819 2539 1583 3347 3163 3457 4409 5869 5867 5849 5827 149 163 167 193
2707 2099 1867 3853 3253 3877 4073 5807 5783 5779 5689 263 269 257 383
1777 2593 2203 3767 4003 3373 3613 5659 5573 5483 5399 443 659 563 797
5669 5413 5437 1103 349 613 587 1753 2687 2267 1999 4219 3307 3719 3989
4547 4967 5653 499 1483 1049 367 2297 1499 1657 1409 3697 4483 4339 4583
5693 5557 5039 683 359 479 1033 1669 2617 1877 1217 4273 3343 4099 4723
5009 5273 4919 599 1223 773 1277 1987 1213 2383 1723 3923 4567 3583 4093

Если применить к этому квадрату преобразование обратное преобразованию 3-х квадратов, получится ассоциативный квадрат.

-- Ср ноя 10, 2010 09:40:58 --

Прикинула магическую константу, которую должен дать примитивный квадрат № 2, если не ошиблась (цифр очень много :-)

), она получается 100295295. Уже лучше, чем в полученном пандиагональном квадрате, у него магическая константа равна 179870403.
Ещё один результат коллективного творчества - дьявольский квадрат 13-го порядка с симпатичной магической константой всего чуть больше 100 млн. Авторский коллектив тот же.

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

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

Примитивный квадрат 13х13 с найденной maxal'ем строкой получается такой:

Код:

823 1109 3203 5003 5623 6793 9209 26479 50789 63443 479209 852689 1154819
991 1277 3371 5171 5791 6961 9377 26647 50957 63611 479377 852857 1154987
1237 1523 3617 5417 6037 7207 9623 26893 51203 63857 479623 853103 1155233
5857 6143 8237 10037 10657 11827 14243 31513 55823 68477 484243 857723 1159853
7753 8039 10133 11933 12553 13723 16139 33409 57719 70373 486139 859619 1161749
8713 8999 11093 12893 13513 14683 17099 34369 58679 71333 487099 860579 1162709
12241 12527 14621 16421 17041 18211 20627 37897 62207 74861 490627 864107 1166237
17203 17489 19583 21383 22003 23173 25589 42859 67169 79823 495589 869069 1171199
34381 34667 36761 38561 39181 40351 42767 60037 84347 97001 512767 886247 1188377
160591 160877 162971 164771 165391 166561 168977 186247 210557 223211 638977 1012457 1314587
493693 493979 496073 497873 498493 499663 502079 519349 543659 556313 972079 1345559 1647689
843757 844043 846137 847937 848557 849727 852143 869413 893723 906377 1322143 1695623 1997753
96059563 96059849 96061943 96063743 96064363 96065533 96067949 96085219 96109529 96122183 96537949 96911429 97213559

Не буду превращать его в пандиагональный квадрат, у меня ещё не запрограммировано это преобразование, а вручную довольно долго.
Замечу, что магическую константу будущего пандиагонального квадрата легко определить: сумма чисел в любой диагонали примитивного квадрата равна этой константе.
Напомню преобразование Россера, превращающее примитивный квадрат в пандиагональный:
$a(i,j) = b(3i+2j,2i+j)$ , где $a(i,j)$ - эементы примитивного квадрата, $b(3i+2j,2i+j)$ - элементы пандиагонального квадрата, индексы берутся по модулю 13 (в случае квадратов 13-го порядка).

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

Наконец-то я его нашла :!:

Построена матрица 89х83 смешанным достраиванием.
Хорошая матрица, почти квадратная. Из неё удалось выделить по программе EtCetera (она теперь у меня, пользуюсь ею сама) квадрат 13х13, полностью состоящий из простых чисел (выделение, конечно, производится из матрицы, состоящей из нулей и единиц).

Ещё раз убеждаемся, что смешанное достраивание даёт меньшую константу пандиагонального квадрата.
Это пандиагональный квадрат 13-го порядка из простых чисел с магической константой 5441577, полученный из выделенного примитивного квадрата:

Код:

997141 118913 9901 9377 1062697 656263 929527 1523 4457 849727 53077 190891 558083
923947 844043 34361 7591 23719 1186411 673793 5101 3371 1041841 128483 31513 537403
558251 1037041 122477 10657 9623 25933 1379923 953851 1907 5003 1003111 139429 194371
537787 924493 997427 120713 11071 23887 1226311 677357 5857 3617 5077 852143 55837
195127 558497 277 846137 34981 10007 26479 1533307 1040203 5387 5171 1043011 142993
142189 541267 924661 1037327 124277 11827 24133 189547 1401017 30181 4001 5623 1005527
866653 219451 558881 823 999521 121333 13487 26647 1573207 1043767 6143 5417 6247
1045427 145753 542023 924907 563 847937 36151 24517 190093 1554401 116533 7481 5791
6793 1020037 305803 562361 991 1039421 124897 14243 26893 536443 1767427 30467 5801
6037 8663 869413 566347 925291 1109 1001321 122503 27997 190261 1594301 120097 8237
9281 6961 1059937 309367 563117 1237 2657 848557 38567 27277 536989 1920811 116819
32561 6421 9209 1022797 652699 928771 1277 1041221 126067 28753 190507 557537 843757
120383 10037 7207 23173 1033027 587441 1621 3203 1001941 124919 30757 537157 1960711

Больше пока не буду строить матрицы для пандиагонального квадрата 13-го порядка из простых чисел. Результат, к которому я стремилась, получен. Дальнейшая минимизация магической константы - дело очень сложное. Надо ещё что-то придумывать принципиально новое, чтобы получить пандиагональный квадрат 13-го порядка с меньшей магической константой.

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

Поэкспериментировала с квадратами 7-го порядка из смитов.
По алгоритму смешанного достраивания каждая матрица выделяет квадрат 7х7 из единиц. Я раньше квадраты 7х7 вручную выделяла, а сейчас их тоже по программе EtCetera выделяю; по программе, разумеется, намного быстрее.
Квадраты-то примитивные выделяются из всех матриц, но константы большие получаются. Вот удалось ещё чуть уменьшить магическую константу пандиагонального квадрата:

Код:

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

А с примитивными квадратами 11х11 из смитов очень плохо, даже близко ничего нет. Надо намного увеличивать массив смитов, чтобы получить эти квадраты. Я задействовала для достраивания смиты до 1500000, а всего у меня есть смиты до 2000000.
Надо брать, например, один из полученных примитивных квадратов 7х7 и начинать смешанное достраивание. При этом желательно получить матрицу как можно большего размера, кроме того, в ней надо задать сколько-то готовых строк и готовых столбцов (они уже полностью должны состоять из смитов). При построении матриц для примитивного квадрата 13х13 из простых чисел я задавала 7 готовых строк и 7 готовых столбцов, этого оказалось достаточно.

В принципе можно попробовать и "чистое" достраивание, то есть к тем же известным примитивным квадратам 7х7 пытаться достроить 4 строки и 4 столбца (по закону примитивного квадрата), но сразу только из смитов. Предполагаю, что достраивание выполнится, но с очень большими числами; точно так, как было при достраивании всго одного столбца (одной строки) к примитивному прямоугольнику из простых чисел.
Вот, например, последний полученный мной примитивный квадрат 7х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

Из него получен показанный выше пандиагональный квадрат.
Предлагаю всем попробовать "чистое" достраивание этого примитивного квадрата до примитивного квадрата 11х11.

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

Обновлённые таблички по пандиагональным квадратам из простых чисел и из смитов:

Pavlovsky
Вы серьёзно решили потратить полгода на поиск наименьшего пандиагонального квадрата 6-го порядка из смитов? :-)

Бросьте! Посмотрите, у пандиагонального квадрата 6-го порядка из смитов магическая константа даже меньше, чем у квадратов порядков 4 и 5. Вполне возможно, что эта константа и является наименьшей.
Вы решили выполнить полный перебор? Ну, это вы можете и в полгода не уложиться.

А с другими квадратами кто будет работать? :-(

Посмотрите, что у нас с константами пандиагональных квадратов из простых чисел порядков 11 и 13. Это никуда не годится! А пандиагональный квадрат 7-го порядка из смитов... У него магическая константа огромная по сравнению с квадратами порядков 4 - 6. И уменьшить не удаётся.

Pavlovsky · 21/02/10 1594 Екатеринбург

Наталия, я уже на это столько сил положил. Так что отказаться от поисков уже немогу. Буду пол года мучить свой комп пока не найду пандиагональный МК 6х6 из Смитов с меньшей константой чем есть(о доказательстве минимальности пока речи не идет). Сейчас копаюсь в районе константы 4884.

По-поводу пандиагональных МК порядка 7 и более. Я уже писал, жду пока решится вопрос о соотношении регулярных и нерегулярных МК. Кстати приз в 500 рублей ждет своего хозяина.

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

Pavlovsky в сообщении #373446 писал(а):

Наталия, я уже на это столько сил положил. Так что отказаться от поисков уже не могу.

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

Цитата:

Буду пол года мучить свой комп пока не найду пандиагональный МК 6х6 из Смитов с меньшей константой чем есть(о доказательстве минимальности пока речи не идет).

А если не существует такого квадрата? :-)

Цитата:

Сейчас копаюсь в районе константы 4884.

Вы идёте с меньших констант? Тогда вам совсем немного осталось, если с шагом 108.

Цитата:

По-поводу пандиагональных МК порядка 7 и более. Я уже писал, жду пока решится вопрос о соотношении регулярных и нерегулярных МК. Кстати приз в 500 рублей ждет своего хозяина.

Я так полагаю, долго ждать придётся :-)

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

Pavlovsky
не отчаивайтесь! Скоро ваша задача будет решена на конкурсе, который начинается прямо сейчас :-)

Приглашаю всех на конкурс "Нетрадиционные пандиагональные квадраты" :!:

topic38320.html

Pavlovsky · 21/02/10 1594 Екатеринбург

Цитата:

А если не существует такого квадрата?

Его не может не быть! Иначе ... Нет он есть!

Цитата:

Вы идёте с меньших констант? Тогда вам совсем немного осталось, если с шагом 108.

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

Цитата:

Приглашаю всех на конкурс "Нетрадиционные пандиагональные квадраты"
topic38320.html

Хороший конкурс. Надо задачи из него предложить Зомерману.

Правда задачу 3 вы изложили в своей трактовке. Так что за решение задачи 3 из вашего конкурса я 500 рублей не дам.

-- Пт ноя 12, 2010 11:25:32 --

Предлагаю для конкурса еще задачу:
Даны числа (первая колонка число, втарая количество таких чисел):
0 30
1 1
2 1
3 4
4 35
6 32
8 6

Используя эти числа построить пандиагональный МК 6х6 такой что:
1) Сумма чисел в любой строке, колонке, диагонали, разорванной диагонали была одинаковой по модулю 9.

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

Pavlovsky в сообщении #373903 писал(а):

Цитата:

А если не существует такого квадрата?

Его не может не быть! Иначе ... Нет он есть!

Это слова настоящего исследователя!

Цитата:

Правда задачу 3 вы изложили в своей трактовке. Так что за решение задачи 3 из вашего конкурса я 500 рублей не дам.

Ну и ладно :-)

По поводу вашей задачи. Как я понимаю, вы хотите шаблон из вычетов для пандиагонального МК 6-го порядка по модулю 9. Я занималась давно такими шаблонами, не помню уже, из каких вычетов у меня были шаблоны. Если сохранился файл, посмотрю. Да и здесь я об этих шаблонах писала, несколько вроде даже приводила. И программу я делала по одному из таких шаблонов, вроде в нём присутствовали только 4 вычета, самые ходовые.

Pavlovsky · 21/02/10 1594 Екатеринбург

Цитата:

По поводу вашей задачи. Как я понимаю, вы хотите шаблон из вычетов для пандиагонального МК 6-го порядка по модулю 9. Я занималась давно такими шаблонами, не помню уже, из каких вычетов у меня были шаблоны. Если сохранился файл, посмотрю. Да и здесь я об этих шаблонах писала, несколько вроде даже приводила. И программу я делала по одному из таких шаблонов, вроде в нём присутствовали только 4 вычета, самые ходовые.

Все так и есть. Только набор вычетов представленный выше очень кривой. Мои попытки построить шаблон из этих чисел не увенчались успехом. Так что задача не простая. Если удастся доказать, что из этого набора построить МК не возможно. Тогда автоматически следует, что пандиагональный МК 6х6 с минимальной магической константой из чисел Смита обязатольно строится только из чисел Смита вида 4mod9. Это огромная эконмия в поисках!

-- Пт ноя 12, 2010 18:20:06 --

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

Цитата:

Найти пандиагональный МК 7х7 из различных простых чисел с магической констатной C и доказать, что не существует регулярного (по Россеру) пандиагонального МК 7х7 из различных простых чисел с константой равной или меньшей C. Или доказать, что это невозможно.

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

Начну с конца. По-моему, ваша постановка задачи 3 эквивалентна моей постановке. Только в моей постановке присутствует квадрат с конкретной магической константой. Тут надо подумать. У меня что-то ускользает разница :-)

Посмотрела файл с шаблонами. Увы, его уже нет.

Так вам что надо, чтобы все вычеты обязательно присутствовали в шаблоне?
У меня были шаблоны с 3-4 вычетами, а вот чтобы все сразу присутствовали - такого вроде не было. Ведь и программу писала для построения шаблонов. Где вы раньше были, когда я писала об этих шаблонах? Надо посмотреть, может, программа сохранилась. У меня ведь чёрт ногу сломит, программ очень много, я в них уже сама на разбираюсь. При этом есть совсем древние, ещё с интерпретатором работали, потом три разных компилятора svb прислал, и в каждой папке (с каждым компилятором) уже по два-три десятка программ.

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

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

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