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

[Nataly-Mak]

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

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

Решила протестировать программу на построении ассоциативного квадрата Стенли 6-го порядка из произвольных натуральных чисел (с двумя дополнительными условиями, которые должны гарантировать превращение построенного квадрата в совершенный магический квадрат).
Задаю константу ассоциативности квадрата K=222
[задаётся не индекс квадрата S, а константа ассоциативности K; эти величины для квадрата 6-го порядка связаны так: $S=3K$]
во входной файл записываю массив из 230 первых натуральных чисел. Запускаю программу, решение выдаётся мгновенно:

1 2 101 103 202 203
4 5 104 106 205 206
7 8 107 109 208 209
13 14 113 115 214 215
16 17 116 118 217 218
19 20 119 121 220 221

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

1 220 103 19 202 121
218 5 116 206 17 104
13 208 115 7 214 109
203 20 101 221 2 119
16 205 118 4 217 106
215 8 113 209 14 107

Всё замечательно.
Протестировала программу и для индекса ассоциативного квадрата Стенли, который мне давно известен: S=29790.
Прогоняю программу полностью, решение выдаётся только одно - то самое, которое известно. Других решений программа не находит.

Каким-то чудом мне удалось тогда попасть на эту магическую константу - 29790.
Сейчас проверила уже около десятка различных индексов близких к данному значению, решений нет!
А проверять надо очень много.
Наименьший пандиагональный квадрат 6-го порядка из простых чисел имеет магическую константу 486 (построен svb).
Представили диапазон? Проверять надо магические константы с шагом 6.
Хватит ли мне жизни, чтобы всё это проверить?

[Nataly-Mak]

У меня хорошая новость - опубликована последовательность A225133 в OEIS, это последовательность минимальных индексов квадратов Стенли из чисел Смита.

(Оффтоп)

Большое спасибо General и maxal, они помогли мне опубликовать статью.
Также выражаю благодарность Pavlovsky, J. K. Andersen и Carlos Rivera.

-- Пн май 06, 2013 06:18:30 --

Отмечу факт, который остался за рамками статьи.
Квадрат Стенли 6-го порядка их чисел Смита с индексом S=30885 был найден мной.

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

Сегодня удалось немного продвинуться в поиске квадрата Стенли 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 числа, это ещё очень много для полного перебора.

Однако я не доказала минимальность этого индекса.
Очень долго билась, чтобы уменьшить индекс, но так ничего и не получилось.

Минимальность индекса подтвердил J. K. Andersen.
Он построил точно такой же квадрат и сообщил (в головоломке 681 на сайте primepuzzles.net), что это квадрат с минимальным индексом.

[Nataly-Mak]

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

Я готовлю свои программы (в исполняемом варианте).
Но прежде чем выложить их, хочу подробно описать что и как строится.

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

149 769 1069 2309 2609 3229
863 1483 1783 3023 3323 3943
2711 3331 3631 4871 5171 5791
4139 4759 5059 6299 6599 7219
5987 6607 6907 8147 8447 9067
6701 7321 7621 8861 9161 9781

Определение ассоциативного квадрата Стенли было дано выше.
Понятно, что такой квадрат составляется из пар чисел, дающих одинаковую сумму, которая суть константа ассоциативности квадрата. Для приведённого квадрата константа ассоциативности равна 9930. Пары чисел:

149 9781, 769 9161, 1069 8861 и т.д.

Эти пары назвают ещё парами комплементарных чисел (название произошло от свойства комплементарности совершенных магических квадратов).

В моей программе построения ассоциативного квадрата Стенли главным параметром является константа ассоциативности. Я задаю конкретную константу ассоциативности и пытаюсь строить квадрат с такой константой.
Конечно, можно организовать поиск по-другому: не фиксировать константу ассоциативности. Но мне кажется, что так поиск будет выполняться намного дольше.

Стартовая программа START.exe готовит массив чисел по заданной константе ассоциативности, то есть она как раз ищет все пары комплементарных чисел и ранжирует массив (числа выбираются из файла prime.txt, содержащего простые числа). При запуске программы выдаётся запрос на ввод константы ассоциативности. Введите константу. Программа сформирует массив чисел и запишет его в файл A22.txt.
Посмотрите этот файл, в нём есть информация о количестве чисел в сформированном массиве. Этот параметр нужен для второй программы - PRIMIT6as1.exe.
При запуске этой программы запрашивается количество чисел в массиве. Массив программа введёт из файла A22.txt.
Это всё. Больше ничего не требуется.

Выполните тест
При запуске программы START.exe введите константу ассоциативности 9930.
Программа сформирует массив, смотрите его в файле A22.txt
(на файл A5.txt не обращайте внимания, это промежуточный рабочий файл).
В файле вы увидите, что количество чисел в массиве равно 532.
Теперь запустите программу PRIMIT6as1.exe.
Введите на запрос программы количество чисел 532.
Программа выполнится быстро, ассоциативный квадрат Стенли будет построен и запишется в файл A2.txt.
Этот квадрат показан здесь.

Примечание: для построения квадрата 6-го порядка требуется всего 18 пар комплементарных чисел. В тестовом массиве таких пар 266. Понятно, что если пар будет меньше 18, квадрат построить невозможно.

Чуть позже выложу архив с программами.

Если есть вопросы по описанию, пожалуйста, спрашивайте, не стесняйтесь

-- Пн май 06, 2013 09:57:53 --

Архив:
http://yadi.sk/d/YQXkd2FN4a3XI

Архив содержит файл prime.txt и две исполняемые программы: START.exe и PRIMIT6as1.exe.

-- Пн май 06, 2013 10:18:37 --

Замечания

1. Обычный квадрат Стенли 6-го порядка (не ассоциативный) из простых чисел имеет минимальный индекс 774:

13 19 43 109 139 223
31 37 61 127 157 241
41 47 71 137 167 251
53 59 83 149 179 263
67 73 97 163 193 277
101 107 131 197 227 311

Следовательно, нам известна нижняя граница искомого индекса ассоциативного квадрата Стенли. Известна и верхняя граница - 29790.
Я не знаю, существует ли ассоциативный квадрат Стенли 6-го порядка (из простых чисел) с индексом, находящимся в этом интервале.

2. Ассоциативные квадраты Стенли с минимальным индексом я ищу не просто так, а с целью получить наименьший совершенный квадрат 6-го порядка из простых чисел (об этом писала выше).
Поэтому надо искать только ассоциативные квадраты Стенли с индексом кратным 6, ибо совершенный магический квадрат 6-го порядка из простых чисел может иметь только магическую константу кратную 6.
И как уже было отмечено выше, далеко не любой ассоциативный квадрат Стенли 6-го порядка превращается в совершенный магический квадрат. Но это проверяется в программе (наложены два дополнительных условия).

[Nataly-Mak]

Я уже проверила ряд констант ассоциативности, выбирала их методом тыка:

(Оффтоп)

1800 75
5700 186
5760 172
3300 120
7200 198
7800 233
8100 230
8400 271
8700 242
8880 256
9000 242
9300 261
9360 264
9366 229
9420 255
9480 257
9600 261
9630 264
9660 324
9666 194
9690 284
9696 193
9720 254
9750 286
9780 260
9840 264
9870 316
9900 301
9906 211
9912 233
9918 223
9924 200

Первый столбец - константа ассоциативности, второй столбец - количество пар комплементарных чисел. Для константы ассоциативности 9660 имеется 324 пары комплементарных чисел, но квадрат не строится!

[Nataly-Mak]

Всё не так страшно

Вчера начала проверку констант ассоциативности не выборочно, а подряд. За день проверила примерно 100 констант.
Сегодня с утра сделала пакетный файл; обе программы выполняются одна за другой через Pause; вся нужная информация выводится на экран, я её вижу; выполнение программ повторяется 10 раз.
Стало намного удобнее. Продолжаю проверку.
Хорошо, что проверка одной константы выполняется довольно быстро, когда чисел в массиве меньше 250 (125 пар комплементарных чисел), да и когда больше, тоже не очень долго.
Так что, надеюсь проверить все константы.

[Nataly-Mak]

Проверка идёт полным ходом.

Как уже писала, минимально возможный индекс ассоциативного квадрата Стенли 6-го порядка из простых чисел - 774, значит, минимально возможная константа ассоциативности равна 258.
Для некоторых констант ассоциативности в начале списка имеется меньше 18 пар комплементарных чисел, значит, и проверять их не надо.
Например:

258 14
260 10
262 8
264 16
266 8
268 9
270 19
272 7
274 10
276 16
278 14
282 16
284 8
286 12
288 17
290 10

[первый столбец - константа ассоциативности, второй столбец - количествоа пар комплементарных чисел].
Здесь надо проверить всего одну константу ассоциативности - 270 (19 пар комплементарных чисел).

Друг помог сделать очень хороший пакетный файл, чтобы полностью автоматизировать поиск. Я такие пакетные файлы писать не умею. Всё-таки свет не без добрых людей!
А программы обе мои; в них сделали небольшие изменения - ввод параметров не с клавиатуры, а из файлов, и вывод параметра "количество чисел в массиве" в файл.
Теперь с утра запускаю этот пакетный файл с параметром, например:

run.bat 5040

(5040 - та константа, с которой надо начть проверку) и - всё! Дальше программа выполняется без моего участия. Вечером прерываю программу, записав константу, на которой остановилась проверка.
В пакетном файле организован цикл по константе ассоциативности (константа увеличивается с шагом 2 от заданного начального значения); программа прекращает работу, как только константа ассоциативности достигает максимального значения - 9930. Я даже не знала, что это можно организовать в пакетном файле.

Сегодня начала проверку уже с константы 6126. Конец виден
А решения пока не найдено.

[Nataly-Mak]

Получила письмо, в котором автор (болгарин Radko Nachev) предлагает строить пандиагональные квадраты из простых чисел-близнецов. Он сообщает, что построил такой квадрат 4-го порядка с магической константой 120900. Непонятно, почему такая большая константа.

Сразу строю ассоциативный квадрат Стенли 4-го порядка из близнецов с индексом 420 (с меньшим индексом квадрат не найден; надо бы проверить ещё раз --- искала по-быстрому):

17 19 59 61
29 31 71 73
137 139 179 181
149 151 191 193

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

17 191 31 181
151 61 137 71
179 29 193 19
73 139 59 149

Может быть, Radko как-то по-другому строил свой квадрат с константой 120900.
Предполагается, что будет опубликована головоломка на сайте primepuzzles.net о построении таких квадратов. Тогда всё прояснится.

[Nataly-Mak]

Головоломка Radko Nachev опубликована.
Всё прояснилось. Пандиагональные квадраты строятся из простых чисел близнецов, причём берутся только первые числа из пар близнецов.
Первый построенный Radko квадрат 4-го порядка с магической константой 120896:

2657 57191 4517 56531
50591 10457 48731 11117
55931 3917 57791 3257
11717 49331 9857 49991

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

Ну, и тут мне сослужили хорошую службу ассоциативные квадраты Стенли 4-го порядка, которые очень просто превращаются в пандиагональные (и совершенные!) квадраты.
Запустив свою программу построения ассоциативных квадратов Стенли 4-го порядка, довольно быстро нашла квадрат 4-го порядка с минимальным индексом 12176.
Полученный из него наименьший пандиагональный квадрат 4-го порядка (из простых чисел близнецов - только первые числа из пар близнецов):

239 5279 1871 4787
4421 2237 2789 2729
4217 1301 5849 809
3299 3359 1667 3851

Магическая константа квадрата 12176.

Закончу проверку построения наименьшего совершенного квадрата 6-го порядка, попробую решить эту головоломку для квадратов порядков 5 и 6.

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

[Nataly-Mak]

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

Ассоциативный квадрат Стенли 6-го порядка без двух дополнительных условий (гарантирующих превращение квадрата в совершенный) найден быстро; индекс квадрата равен 2520.

Но начну по порядку --- все наименьшие ассоциативные квадраты Стенли из простых чисел, которые нашла на сегодня.

n=2, S=16

3 5
11 13

n=3, S=177

5 17 29
47 59 71
89 101 113

n=4, S=240

7 13 31 37
17 23 41 47
73 79 97 103
83 89 107 113

Этот квадрат даёт наименьший совершенный магический квадрат 4-го порядка.

n=5, S=3505

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

Этот квадрат превращается в наименьший идеальный магический квадрат.
Для превращения можно использовать либо преобразование Россера, либо моё преобразование (получено при разработке темы "Построение идеальных квадратов нечётного порядка из обратимых квадратов", см. статью)

Интересно, как тесно связаны квадраты Стенли с магическими квадратами.
В статье Россера дан замечательный алгоритм построения пандиагональных квадратов порядков, являющихся простым числом, с помощью квадратов Стенли.
Но это далеко не всё! С помощью квадратов Стенли можно строить идеальные и совершенные магические квадраты.

n=6, S=2520

17 53 83 101 131 167
113 149 179 197 227 263
317 353 383 401 431 467
373 409 439 457 487 523
577 613 643 661 691 727
673 709 739 757 787 823

К сожалению, этот наименьший ассоциативный квадрат Стенли 6-го порядка в совершенный магический квадрат не превращается. Но превращается другой ассоциативный квадрат Стенли - с индексом 29790.

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

[Nataly-Mak]

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

Головоломка Radko Nachev опубликована.
Закончу проверку построения наименьшего совершенного квадрата 6-го порядка, попробую решить эту головоломку для квадратов порядков 5 и 6.
Приглашаю всех к решению этой головоломки.
Кстати, головоломка для обычных магических квадратов из простых чисел близнецов была опубликована на сайте очень давно. А вот теперь требуется строить пандиагональные квадраты.

Первый результат получен - пандиагональный квадрат 5-го порядка из простых чисел близнецов.
Тут тоже начинала с построения квадрата Стенли 5-го порядка (это уже история: с этого начинал Pavlovsky, когда искал наименьший пандиагональный квадрат 5-го порядка из простых чисел; именно он вгрызался в статью Россера, проник в примитивные квадраты и алгоритм построения с помощью этих квадратов пандиагональных магических квадратов).
Давнишняя программа построения квадратов Стенли 5-го порядка (примитивных квадратов по Россеру) пропала, когда сдох старый компьютер. Пришлось написать новую программу; но это и хорошо, ибо новая программа у меня всегда чуточку лучше старой

Итак, новая программа нашла квадрат Стенли 5-го порядка из простых чисел близнецов с индексом 6559:

41 59 461 881 2129
179 197 599 1019 2267
641 659 1061 1481 2729
1031 1049 1451 1871 3119
1301 1319 1721 2141 3389

Минимальность индекса сейчас проверяется.

Покажу заодно и преобразование Россера, превращающее квадрат Стенли 5-го порядка в пандиагональный квадрат; у меня это преобразование (как и все другие) в матричной форме, мне так удобнее пользоваться преобразованием.
Матрица исходного квадрата Стенли A(i,j) (индексация в естественном порядке), матрица полученного из него пандиагонального квадрата B=f(A) имеет следующий вид:

A11 A35 A54 A23 A42
A53 A22 A41 A15 A34
A45 A14 A33 A52 A21
A32 A51 A25 A44 A13
A24 A43 A12 A31 A55

Это полученный с помощью данного преобразования пандиагональный квадрат 5-го порядка из простых чисел близнецов:

41 2729 2141 599 1049
1721 197 1031 2129 1481
3119 881 1061 1319 179
659 1301 2267 1871 461
1019 1451 59 641 3389

Магическая константа квадрата равна индексу исходного квадрата Стенли - 6559.

В статье Россера показано, что между квадратами Стенли и пандиагональными квадратами порядка n=5 существует взаимнооднозначное соответствие.
К сожалению, для квадратов других порядков это не так.

Параллельно ищу пандиагональный квадрат 6-го порядка из простых чисел близнецов. Для этого поиска использую программу коллеги svb, которая, к счастью, сохранилась. Отличная программа!
Пока найден квадрат с магической константой 6618. Проверяю другие потенциальные константы в надежде найти квадрат с меньшей магической константой. К сожалению, программа работает довольно долго (по сравнению с программой для квадратов 5-го порядка), но это и понятно: с ростом порядка имеем увеличение перебора в разы. Константы проверяю выборочно. Вот выбрала константу 6618 (самую первую) и квадрат сразу же нашёлся. Удача!
Дальше проверила ещё констант пять (меньше 6618), квадратов больше нет.

[Nataly-Mak]

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

Итак, новая программа нашла квадрат Стенли 5-го порядка из простых чисел близнецов с индексом 6559.
Минимальность индекса сейчас проверяется.

Проверка закончилась. Моя программа утверждает, что индекс 6559 является минимальным для квадратов Стенли данного класса. Надеюсь, что она не врёт

Цитата:

Параллельно ищу пандиагональный квадрат 6-го порядка из простых чисел близнецов.
Пока найден квадрат с магической константой 6618.

Найден квадрат с магической константой 4206. По-прежнему проверяю константы выборочно, ибо проверить все подряд нереально за приемлемое время.
Итак, 6618 --> 4206 -->

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

Кстати, своё решение для n=4 отправила автору сайта; он ответил, что решения будет вносить через неделю после опубликования головоломки, такой у него порядок.

[Nataly-Mak]

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

Итак, 6618 --> 4206 -->

Теперь
6618 --> 4206 --> 4134

Кто меньше?
Думаю, что это ещё не минимум. Продолжу крутить программу, может быть, ещё повезёт.

[Pavlovsky]

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

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

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


http://oeis.org/A001359/b001359.txt
А вот и список. Можно попробовать запустить свои программы для N=4,5. Для N=6 надо запускать программы Беляева или Чернова.

[Nataly-Mak]

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

Для порядков 4-6 задача решается элементарно. Нужен только список простых чисел близнецов.
http://oeis.org/A001359/b001359.txt
А вот и список. Можно поробовать запустить свои программы для N=4,5. Для N=6 надо запускать программы Беляева или Чернова.

Для порядков 4-5 я задачу уже решила.
Для порядка 6 не так уж элементарно.
Работают обе программы у меня - и Беляева, и Чернова. Сейчас подключила вторую.
Найти наименьший квадрат не так просто, как вам кажется. Дело в том, что одна константа проверяется долго, если квадрат существует, быстро --- если решения нет.

Уже нашла квадрат с константой 4062. Проверяю дальше.
Подумываю, как решить задачу для n=7, хотя в головоломке для этого порядка даже и не просят решение. Но интересно всё равно!
Хотя, что, собственно, тут особо думать. Берём массив близнецов и ищем квадраты Стенли 7-го порядка из чисел этого массива. Как найдём, так и пандиагональный квадрат в кармане
В теории элементарно. На практике всё не так просто, как в теории.
Кстати, посмотрите, какая магическая константа квадрата 4-го порядка приведена в головоломке. Огромная!

И ещё: да, хорошо решается задача по программам Беляева и Чернова, ага, ну совсем элементарно
Не забывайте только, как много сил потратили авторы на написание этих программ!
Здесь, собственно, задействован авторский алгоритм Беляева, который мало кому известен, только тем, кто был в курсе всех событий по разработке этого алгоритма.

[Nataly-Mak]

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

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

Программа svb (Беляева) прверяет магическую константу 4026, программа alexBlack (Чернова) - 3990.
Думала, что две программы быстрее справятся со всей работой, но это совсем не так. Похоже, программы только сильно мешают одна другой. Запустила программы задолго до полудня, они до сих пор работают, конца не видно ни в одной программе.

В программе alexBlack рисуется очень симпатичная парабола
В каждой строчке только точки, догадайся, мол, сама. Ну, я догадываюсь, конечно, ибо в недалёком прошлом не раз пользовалась этой программой. На данный момент в массиве осталось 72 числа, одно из них помещено в угловую ячейку квадрата, для остальных 71 чисел идёт перебор. Перебор, конечно же, не "полный тупой", но всё равно очень и очень долгий!

Я давно поднимала вопрос об оптимизации этой программы (для обоих авторов это актуально), смотрите, например, тему "Распараллеливание для многоядерных процессоров".
По прошедшему недавно конкурсу программистов "Factorials" стало понятно, что программисты сейчас пишут многопоточные программы. Такую программу я получила от Ed Mertensotto (mertz), так же и whitefox написал такую программу. Vovka17 то же самое сообщал: учился в этом конкурсе многопоточному программированию.
Значит, процесс пошёл, осваиваем потихоньку

Очень хотелось бы, чтобы svb и alexBlack попробовали довести программу построения нетрадиционного пандиагонального квадрата 6-го порядка до ума с использованием многопоточного программирования.
Программы очень хороши (по алгоритму), но... по времени работы они никуда не годятся!
Когда мы вместе с svb искали подтверждение наименьшему пандиагональному квадрату 6-го порядка из чисел Смита, нам потребовалось много дней. Одна магическая константа может проверяться несколько суток. Разве это дело?

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