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

[Nataly-Mak]

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

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

[Nataly-Mak]

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

11  101  * Potential scam. Censored *  0 
* Potential scam. Censored *  4547  5477  0 
* Potential scam. Censored *  10007  10937  0 
17489  17579  19427  * Potential scam. Censored * 
19379  19469  21317  * Potential scam. Censored * 
22481  22571  24419  * Potential scam. Censored * 
0  0  0  0  0  0  0 

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

11  101  * Potential scam. Censored *  a1
 * Potential scam. Censored *  4547  5477  a2 
 * Potential scam. Censored *  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 * Potential scam. Censored *
881 1319 569 29 347 809
179 * Potential scam. Censored *
* Potential scam. Censored * 191
* Potential scam. Censored * 617
2381 41 197 17 461 857

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

[Nataly-Mak]

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

11 101 * Potential scam. Censored * 376931
* Potential scam. Censored * 4547 5477 378149
* Potential scam. Censored * * Potential scam. Censored *
17489 17579 19427 20477 * Potential scam. Censored *
19379 19469 21317 22367 * Potential scam. Censored *
22481 22571 24419 25469 * Potential scam. Censored *
150959 151049 152897 153947 154277 X   X

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

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

[Nataly-Mak]

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

* Potential scam. Censored *  6299  519119 
419  461  * Potential scam. Censored *  519521
* Potential scam. Censored *  5279  7559  520379 
* Potential scam. Censored *  6689  8969  521789
7547  7589  10499  11057  * Potential scam. Censored * 
13679  13721  16631  17189  * Potential scam. Censored *
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  * Potential scam. Censored *  8837  9629 
* Potential scam. Censored *  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):

* Potential scam. Censored * 599 1523
* Potential scam. Censored * 953 1373
863 929 * Potential scam. Censored *
977 * Potential scam. Censored * 569
1493 * Potential scam. Censored * 683
* Potential scam. Censored * 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:

* Potential scam. Censored * 3793 4729 4793
103 167 * Potential scam. Censored * 4813 4877
499 563 * Potential scam. Censored * 5209 5273
523 587 * Potential scam. Censored * 5233 5297
709 773 * Potential scam. Censored * 5419 5483
733 797 * Potential scam. Censored * 5443 5507
* Potential scam. Censored * * Potential scam. Censored *
* Potential scam. Censored * * Potential scam. Censored *

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

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

19 * Potential scam. Censored * 1277 3793 2777
* Potential scam. Censored * 103 5839 1103 4339
499 * Potential scam. Censored * 797 4273 2297
5297 773 4297 2273 523 5419 1523 3919
* Potential scam. Censored * 5987 83 4987 1583
5903 167 * Potential scam. Censored * 2129 3313
733 * Potential scam. Censored * 563 4507 2063
5483 587 4483 2087 709 5233 1709 3733

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

[Nataly-Mak]

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

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

* Potential scam. Censored *  6299  519119 
419  461  * Potential scam. Censored *  519521
* Potential scam. Censored *  5279  7559  520379 
* Potential scam. Censored *  6689  8969  521789
7547  7589  10499  11057  * Potential scam. Censored * 
13679  13721  16631  17189  * Potential scam. Censored *
31079  31121  34031  34589  35081  37361    X

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

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

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

* Potential scam. Censored *  6299 44066417 
419  461  * Potential scam. Censored * 44066819
* Potential scam. Censored *  * Potential scam. Censored * 
* Potential scam. Censored *  * Potential scam. Censored *
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
* Potential scam. Censored * * Potential scam. Censored *
* Potential scam. Censored * 6689 13721 6299 4229
2729 19961 2969 44067677 11057 31079 4421
* Potential scam. Censored * 8969 16631 44066417
* Potential scam. Censored * 3527 1277 11549 31121
S = 44139893

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