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

[Nataly-Mak]

Всё, отправила свои решения головоломки для n=4,5,6.
Для порядка 6 так и остался меньший квадрат с константой 4062.
Сегодня целый день проверяется константа 3954! Шансы есть, для каждого проверяемого числа находятся 35 элементов. Но... это жутко долго, может и суток не хватить. Нет, я пас.
Пусть другие найдут наименьший квадрат 6-го порядка.
Например, Pavlovsky; он утверждает, что решение головоломки для порядков 4-6 элементарно
Для порядка 7 покрутила программу, тоже долго проверяется, бросаю. Найти можно квадрат, но надо много времени.

Возвращаюсь к ассоциативным квадратам Стенли.

[Nataly-Mak]

Да, расскажу здесь о достраивании квадратов Стенли.
Вот такой квадрат Стенли 6х6 программа поиска квадратов Стенли 7-го порядка находит легко:

11  101  1949  2999  3329  4259  0 
1229  1319  3167  4217  4547  5477  0 
6689  6779  8627  9677  10007  10937  0 
17489  17579  19427  20477  20807  21737  0 
19379  19469  21317  22367  22697  23627  0 
22481  22571  24419  25469  25799  26729  0 
0  0  0  0  0  0  0 

Не хватает одной строки и одного столбца.
Теперь можно пробовать достроить этот квадрат 6х6 до искомого квадрата 7х7.
В чём преимущество достраивания? В том, что при достраивании в программе будет всего две свободных переменных. Поэтому берём большой массив (состоящий тоже из простых чисел близнецов) и пробуем достроить.
Достраивание выполняется по определению квадрата Стенли. Дополним квадрат 6х6 искомыми элементами $a_i$:

11  101  1949  2999  3329  4259  a1
 1229  1319  3167  4217  4547  5477  a2 
 6689  6779  8627  9677  10007  10937  a3 
 17489  17579  19427  20477  20807  21737  a4 
 19379  19469  21317  22367  22697  23627  a5 
 22481  22571  24419  25469  25799  26729  a6 
 a7  a8  a9  a10  a11  a12  a13 

Независимыми здесь будут только два элемента: $a_1$ и $a_7$.
Все остальные элементы вычисляются. Естественно, вычисленные элементы надо проверять на принадлежность массиву чисел-близнецов.

Я ещё не пробовала выполнить достраивание приведённого квадрата 6х6. Надо программку написать для достраивания.
Может быть, есть желающие?
[нет, не программку написать, а выполнить достраивание]

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

[Nataly-Mak]

Всё-таки дожала пандиагональный квадрат 6-го порядка с магической константой 3954 из простых чисел близнецов
Не прерывала программу --- интуиция подсказывала, что решение есть.
Уже полночь. Но квадрат найден!

5 101 1427 1931 71 419
881 1319 569 29 347 809
179 107 521 59 2027 1061
269 2237 599 431 227 191
239 149 641 1487 821 617
2381 41 197 17 461 857

Но и этот квадрат, скорее всего, не наименьший.
Ну, покручу программу ещё --- между делом.

[Nataly-Mak]

Программку достраивания квадрата Стенли 6х6 до квадрата 7х7 написала.
Достроить поностью не удалось:

11 101 1949 2999 3329 4259 376931
1229 1319 3167 4217 4547 5477 378149
6689 6779 8627 9677 10007 10937 383609
17489 17579 19427 20477 20807 21737 394409
19379 19469 21317 22367 22697 23627 396299
22481 22571 24419 25469 25799 26729 399401
150959 151049 152897 153947 154277 X   X

Последние два элемента, разумеется, вычисляются, но они не принадлежат массиву простых чисел близнецов:
155207, 527879

Вот такое почти готовое решение. Но "почти", как известно, не годится.
Чтобы достроить полностью, надо либо изменить исходный квадрат 6х6, либо увеличить массив чисел. У меня массив содержит
100 000 простых чисел близнецов (только первые числа). Этого мало для полного достраивания.

[Nataly-Mak]

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

17  59  2969  3527  4019  6299  519119 
419  461  3371  3929  4421  6701  519521
1277  1319  4229  4787  5279  7559  520379 
2687  2729  5639  6197  6689  8969  521789
7547  7589  10499  11057  11549  13829  526649 
13679  13721  16631  17189  17681  19961  532781
31079  31121  34031  34589  35081  37361    X

Эх, совсем близко решение

[Nataly-Mak]

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

Автор сайта primepuzzles.net Carlos Rivera опубликовал сегодня мои решения головоломки. Больше пока нет других решений. Carlos представил решения как мои и С. Беляева. Всё верно --- я написала, что квадраты 6-го порядка найдены по его программе.

[Nataly-Mak]

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

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

Кто-нибудь бы ещё попробовал решить головоломку.
На конкурсы AZ все налетают, а тут никого нет
А задача-то не так и проста!
Ну, для порядков 4-6 ещё более-менее решаемо, а попробуйте-ка найти такой пандиагональный квадрат порядка 7

Для порядков 4-6 задача решается элементарно. Нужен только список простых чисел близнецов.

Pavlovsky
решение для n=6 в студию!
У меня пока найден квадрат 6-го порядка с магической константой 3774. А у вас?
Конкурс "1000!" закончился, самое время заняться решением головоломки

Кстати, о списке простых чисел близнецов...
У меня список содержит 100 000 первых чисел из пар близнецов.
Этого мало для получения квадрата Стенли 7-го порядка. Где можно взять список побольше (примерно 300 000 первых чисел)?
Программку я сделала для поиска близнецов, но чтобы их очень много найти, надо огромный массив из простых чисел иметь. У меня массив простых чисел не очень большой.

[Nataly-Mak]

Закончила исследование ассоциативных квадратов Стенли 7-го порядка.

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

a36 a47 a51 a62 a73 a14 a25
a72 a13 a24 a35 a46 a57 a61
a45 a56 a67 a71 a12 a23 a34
a11 a22 a33 a44 a55 a66 a77
a54 a65 a76 a17 a21 a32 a43
a27 a31 a42 a53 a64 a75 a16
a63 a74 a15 a26 a37 a41 a52

Ассоциативный квадрат Стенли из простых чисел - полный аналог обратимого квадрата. Значит, к нему тоже можно применить указанное преобразование и получить идеальный квадрат (далее показан пример).
Далее: квадрат Стенли - это примитивный квадрат по Россеру. Следовательно, к нему можно применить преобразование Россера и тоже получить пандиагональный (!) квадрат.

Это проебразование Россера в матричной форме:

a16 a33 a57 a74 a21 a45 a62
a71 a25 a42 a66 a13 a37 a54
a63 a17 a34 a51 a75 a22 a46
a55 a72 a26 a43 a67 a14 a31
a47 a64 a11 a35 a52 a76 a23
a32 a56 a73 a27 a44 a61 a15
a24 a41 a65 a12 a36 a53 a77

Теперь рассмотрим пример.
Следующий ассоциативный квадрат Стенли я нашла очень давно (см. в указанной выше статье), когда искала идеальный квадрат 7-го порядка из простых чисел:

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

Константа ассоциативности этого квадрата равна 51806, индекс равен 181321.

1. Применяем к этому ассоциативному квадрату Стенли моё преобразование и получаем следующий идеальный квадрат:

20233 27799 30637 37123 44017 7753 13759
43093 7717 13723 19309 26863 34429 36187
25939 33493 39979 42157 6793 13687 19273
5857 12763 19237 25903 32569 39043 45949
32533 38119 45013 9649 11827 18313 25867
15619 17377 24943 32497 38083 44089 8713
38047 44053 7789 14683 21169 24007 31573

(напомню: идеальный квадрат - это пандиагональный квадрат, который обладает ещё и свойством ассоциативности).

2. А теперь применим к ассоциативному квадрату Стенли преобразование Россера. Получим следующий пандиагональный (!) квадрат:

8713 19237 34429 44053 11827 25939 37123
42157 13759 24943 39043 7717 21169 32533
38047 9649 19273 30637 44089 12763 26863
32569 43093 14683 25867 39979 7753 17377
27799 38083 5857 19309 31573 45013 13687
18313 33493 44017 15619 25903 36187 7789
13723 24007 38119 6793 20233 32497 45949

Квадрат получился пандиагональный, но не идеальный --- не хватает ассоциативности. Но это легко исправляется преобразованием параллельного переноса квадрата на торе. И вот какой идеальный квадрат получается в результате этого преобразования:

9649 19273 30637 44089 12763 26863 38047
43093 14683 25867 39979 7753 17377 32569
38083 5857 19309 31573 45013 13687 27799
33493 44017 15619 25903 36187 7789 18313
24007 38119 6793 20233 32497 45949 13723
19237 34429 44053 11827 25939 37123 8713
13759 24943 39043 7717 21169 32533 42157

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

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

Pavlovsky в самом начале темы отзывался о квадратах Стенли весьма скептически.
Однако при более пристальном рассмотрении этих квадратов открываются удивительные вещи.
Похоже, задачу века для пандиагональных квадратов 7-го порядка (за решение которой Pavlovsky обещал вознаграждение ) я уже решила, но... пока только для идеальных квадратов. Идеальные квадраты - это частный случай пандиагональных квадратов. Но! в формулировке задачи сказано: "найти пандиагональный МК такой, что...".
Я представлю идеальный квадрат (автор квадрата alexBlack) такой, что..., но идеальный квадрат является пандиагональным.
Так считается ли задача решённой?

Вот она - "задача века"

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

А блин, не обеднею. Объявляю приз, решившему задачу, вышлю на веб-кошелек 500 (Пятьсот) рублей.
Точно формулирую задачу:

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

[Nataly-Mak]

Продолджаю...
Итак, давно мной был найден ассоциативный квадрат Стенли 7-го порядка из различных простых чисел с индексом 181321 (квадрат показан выше).
Естественно, возникает вопрос: какой наименьший индекс имеет ассоциативный квадрат Стенли 7-го порядка из простых чисел?
Написала программу поиска таких квадратов и начала проверку.
Проверить надо было все потенциальные константы ассоциативности K.
Индекс S ассоциативного квадрата Стенли 7-го порядка связан с константой ассоциативности следующим равенством:
K=2S/7. Для указанного квадрата с индексом S=181321 константа ассоциативности K=51806.
Потенциальные константы ассоциативности находятся в интервале [1234,51806).
Потенциальная константа ассоциативности K должна удовлетворять следующим условиям:
1. Имеется не менее 24 пар комплементарных чисел с суммой в паре равной K;
2. Значение K/2 является простым числом (это число будет центральным элементом искомого квадрата - $a_{44}$).

Для приведённого квадрата K/2=25903 (см. центрадьный элемент квадрата).
С такими условиями потенциальных констант ассоциативности оказалось тоже достаточно много - более 1000. Проверила все, надеюсь, что ничего не пропустила (проверку выполняла с помощью двух пакетных файлов, порциями). Найдены ассоцитивные квадраты с такими индексами:

179921, 157801, 154357, 135023

Не густо! Всего 4 ассоциативных квадрата Стенли в дополнение к тому квадрату, что был найден раньше.
Это квадрат с минимальным индексом 135023:

389  1181  3701  5009  6317  8837  9629 
3449  4241  6761  8069  9377  11897  12689 
13109  13901  16421  17729  19037  21557  22349 
14669  15461  17981  19289  20597  23117  23909 
16229  17021  19541  20849  22157  24677  25469 
25889  26681  29201  30509  31817  34337  35129 
28949  29741  32261  33569  34877  37397  38189 

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

Таким образом, меньший идеальный квадрат 7-го порядка из различных простых чисел - регулярный по Россеру, ибо он получается из примитивного квадрата - имеет магическую константу 135023.
Однако это далеко не наименьший идеальный квадрат 7-го порядка из простых чисел!
alexBlack нашёл идеальный квадрат 7-го порядка из различных простых чисел с магической константой 5411.
Об этом в следующем посте.

[Nataly-Mak]

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

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

Pavlovsky
примитивный квадрат (квадрат Стенли) их этих 49 простых чисел не составляется.

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

Правильный вывод? Ваша задача решена?

А вот теперь надо решить эту же задачу для пандиагонального, но не идеального, квадрата.
Мной найден квадрат Стенли 7-го порядка из различных простых чисел с индексом 1597, который превращается в регулярный пандиагональный квадрат с магической константой 1597.
J. K. Andersen доказал, что квадрат Стенли 7-го порядка с индексом 1597 наименьший.
Следовательно, мы имеем наименьший регулярный пандиагональный квадрат 7-го порядка.
Но является ли этот квадрат наименьшим среди всех пандиагональных квадратов 7-го порядка (из различных простых чисел) - регулярных и нерегулярных

Чтобы ответить на этот вопрос, надо отвлечься от алгоритма Россера и строить пандиагональные квадраты 7-го порядка по общей формуле (что, конечно, намного сложнее).
Именно по общей формуле и нашёл идеальный квадрат alexBlack.

[Nataly-Mak]

Размышления не оставляют...
А что если с совершенными квадратами 6-го порядка точно такая же ситуация, как с идеальными квадратами 7-го порядка
Ассоциативный квадрат Стенли 6-го порядка из различных простых чисел, превращающийся в совершенный квадрат, с индексом меньше 29790 мне найти не удалось.
Теперь надо искать совершенный квадрат 6-го порядка не через квадраты Стенли.
Посмотрела свою статью, в которой описан алгоритм построения нетрадиционных совершенных квадратов 6-го порядка.
На рис. 1 приведена схема совершенного квадрата 6-го порядка. Очевидно, что алгоритм разработан не на основе квадратов Стенли, а на основе определения совершенного квадрата. Это очень хорошо.

Цитата:

Учитывая все эти зависимости, я составила программу построения совершенного квадрата 6-го порядка, в которой всего 4 независимых переменных. Программа выполняется быстро, однако мне долго не удавалось найти совершенный квадрат. Пришлось проверить очень много наборов комплементарных пар простых чисел, причём проверяла я их не по порядку, а выборочно.

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

Начинаю новый эксперимент.
Кто желает вместе со мной?
Как уже сказано, в указанной статье вы найдёте схему построения нетрадиционных совершенных квадратов 6-го порядка.
Потенциальные массивы составляются из пар комплементарных (простых) чисел.
Константа комплементарности единственного известного совершенного квадрата равна 9930. Значит, надо проверять только меньшие константы комплементарности.
Нижняя граница для константы комплементарности равна 150. Понятно, что константа комплементарности в искомых квадратах может быть только чётной.
Кроме того, не надо проверять те константы, для которых количество пар комплементарных чисел меньше 18.

[Nataly-Mak]

Эксперимент идёт полным ходом
Программу построения нетрадиционных совершенных квадратов 6-го порядка восстановила; к счастью, она сохранилась в рукописи, осталось только набрать текст и скомпилировать.
Программа работает быстро, всего 4 независимых переменных.
Начала проверку с константы комплементарности 9930 (для этой константы совершенный квадрат существует) и вниз с шагом 2. Опустила проверку массивов на количество пар комплементарных чисел, для больших констант эта проверка лишняя: меньше 18 пар не бывает. Ну, а ближе к маленьким константам можно вставить эту проверку, хотя там и без того одна константа проверяется очень быстро, можно и все подряд проверить.
Итак, проверить надо все чётные константы комплементарности от 9930 до 150. Всего чуть-чуть

[Nataly-Mak]

Эксперимент завершён.
Совершенный квадрат 6-го порядка из различных простых чисел с магической константой меньше 29790 не найден.
Третий алгоритм я пока не придумала для проверки данного результата.

Теперь хочу заняться ассоциативными квадратами Стенли 8-го порядка из простых чисел.
Из таких квадратов получаются совершенные квадраты, но, наверное, не из любого, так же, как и для порядка 6.
Ну, для начала надо найти наименьший ассоциативный квадрат Стенли 8-го порядка из различных простых чисел. Потом посмотрим, превратится ли он в совершенный квадрат.
Наименьший обычный (не ассоциативный) квадрат Стенли 8-го порядка из различных простых чисел нашёл J. K. Andersen; этот квадрат имеет индекс 3036.

Когда я занималась поиском совершенного квадрата 8-го порядка, мне удалось найти один ассоциативный квадрат Стенли (в те времена этот квадрат назывался примитивным --- по Россеру), который превратился в совершенный квадрат (см. статью).
Покажу и квадрат Стенли, и полученный из него совершенный квадрат (для превращения использовано моё матричное преобразование).

Ассоциативный квадрат Стенли 8-го порядка из различных простых чисел с индексом 24024:

19 83 1019 1583 3229 3793 4729 4793
103 167 1103 1667 3313 3877 4813 4877
499 563 1499 2063 3709 4273 5209 5273
523 587 1523 2087 3733 4297 5233 5297
709 773 1709 2273 3919 4483 5419 5483
733 797 1733 2297 3943 4507 5443 5507
1129 1193 2129 2693 4339 4903 5839 5903
1213 1277 2213 2777 4423 4987 5923 5987

Константа ассоциативности равна 6006.

Полученный из данного квадрата совершенный квадрат 8-го порядка с магической константой 24024:

19 5923 1019 4423 4793 1277 3793 2777
4877 1193 3877 2693 103 5839 1103 4339
499 5443 1499 3943 5273 797 4273 2297
5297 773 4297 2273 523 5419 1523 3919
1213 4729 2213 3229 5987 83 4987 1583
5903 167 4903 1667 1129 4813 2129 3313
733 5209 1733 3709 5507 563 4507 2063
5483 587 4483 2087 709 5233 1709 3733

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

[Nataly-Mak]

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

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

17  59  2969  3527  4019  6299  519119 
419  461  3371  3929  4421  6701  519521
1277  1319  4229  4787  5279  7559  520379 
2687  2729  5639  6197  6689  8969  521789
7547  7589  10499  11057  11549  13829  526649 
13679  13721  16631  17189  17681  19961  532781
31079  31121  34031  34589  35081  37361    X

Эх, совсем близко решение

Сегодня, наконец, сгенерировала достаточно большой массив простых чисел близнецов - 239101 пара близнецов (у меня был интернетовский массив из 100 000 пар).
[Хороший импульс для решения задачи получила в одной из тем форума
До этого долго думала, с какого конца начать решать эту проблему.]

Из чисел этого массива достраивание приведённого квадрата Стенли 6х6 до квадрата Стенли 7х7 получилось сразу:

17  59  2969  3527  4019  6299 44066417 
419  461  3371  3929  4421  6701 44066819
1277  1319  4229  4787  5279  7559 44067677 
2687  2729  5639  6197  6689  8969 44069087
7547  7589  10499  11057  11549  13829 44073947 
13679  13721  16631  17189  17681  19961 44080079
31079  31121  34031  34589  35081  37361  44097479 

Тщательно не проверила ещё квадрат --- завтра, точнее, уже сегодня
Надеюсь, что не ошиблась в программе.
Проверю и превращу его в пандиагональный квадрат с помощью преобразования Россера.
Конечно, индекс квадрата получился огромный (44139893), но пока нет никакого и этот пойдёт.

Уменьшить индекс для квадратов Стенли 7-го порядка такого вида - отличная задача
Кто смелый?

[Nataly-Mak]

Квадрат Стенли 7-го порядка из простых чисел близнецов проверила и превратила в пандиагональный:

17 5279 7589 37361 3371 44069087 17189
34031 44066819 6197 13679 4019 1319 13829
17681 59 7559 10499 44097479 3929 2687
44073947 34589 419 6689 13721 6299 4229
2729 19961 2969 44067677 11057 31079 4421
4787 7547 35081 461 8969 16631 44066417
6701 5639 44080079 3527 1277 11549 31121
S = 44139893

Если не наврала с генерацией больших близнецов, должно быть всё правильно.
Отправила квадрат Rivera и Radko (добавление к головоломке #689), пусть проверяют