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

[Nataly-Mak]

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

Однако пришлось сделать хитрый финт: раньше я генерировала все отклонения кратные 6, для константы 498 это ничего не дало (проверила очень много комплектов таких отклонений и по своей программе, и по программе svb). Тогда я стала генерировать произвольные чётные отклонения. На второй тысяче комплектов отклонений результат был получен:

13  29  73 139 191  53 
151 167  97  17   5  61 
109  41  19 127  71 131 
 31  11 163 149 101  43 
157 113  67   7  47 107 
 37 137  79  59  83 103 
  1: S=498  p2,4,6,8=-36 -8 38 -42
 67 103   7  13 157 151 
 29 139 197  43  53  37 
107   5  89  41 173  83 
181  11 127  71  61  47 
 97 109  19 163  31  79 
 17 131  59 167  23 101 
  1: S=498  p2,4,6,8=-2 26 110 -138

Всего два квадрата на тысячу комплектов отклонений.

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

486, 498, 510, 522

Можно предлагать в OEIS

[Nataly-Mak]

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

svb
вам слово. Завтра вторник и уже не 13-ое

[Nataly-Mak]

Реализовала новую идею в подборе отклонений. Теперь для каждой магической константы генерирую свой набор отклонений. При этом отклонения выбираются только такие, для которых количество комплементарных пар не меньше 5.
Удалось с помощью этого метода получить новый пандиагональный квадрат с магической константой 5964:

94 2902  22 1111 202 1633 
1795 517 895 382 1921 454 
922 166 2785 274 1282 535 
913 526 355 1858 346 1966 
1678 1219 1642 121 319 985 
562 634 265 2218 1894 391 
  1: S=5964  p2,4,6,8=1260 -72 -108 72

Один квадрат на 1000 комплектов отклонений.

Замечу, что магическая константа всё из той же арифметической прогрессии с разностью 108. Я теперь из этой прогрессии и беру константы.

Можно идти дальше Минимальная потенциальная магическая константа (из указанной прогрессии) равна 2508.

svb
предлагаю вам начать снизу, с константы 2508. А я буду идти сверху, так и встретимся где-нибудь

Pavlovsky
а вы не хотите поэкспериментировать по программе svb? Программа очень хорошая, мне нравится. Я вот уже обоработала по ней несколько тысяч комплектов отклонений. Работает быстро даже у меня.

[Pavlovsky]

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

Замечу, что магическая константа всё из той же арифметической прогрессии с разностью 108. Я теперь из этой прогрессии и беру константы.

Наталия надо брать прогрессию с разностью 54, почему я объяснял выше.

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

Можно идти дальше Минимальная потенциальная магическая константа (из указанной прогрессии) равна 2508.
svb
предлагаю вам начать снизу, с константы 2508. А я буду идти сверху, так и встретимся где-нибудь

Проверил константы от 2508 до 3480. Построить пандиагональный МК из чисел Смита вида 4mod9 для этих констант невозможно.

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

Pavlovsky
а вы не хотите поэкспериментировать по программе svb? Программа очень хорошая, мне нравится. Я вот уже обоработала по ней несколько тысяч комплектов отклонений. Работает быстро даже у меня.

Дык у вас и без меня отлично получается!! Уже три недели пытаюсь реализовать некоторые свои идеи, пока безуспешно. Хотя надеюсь дня через три представить первые результаты.

[Nataly-Mak]

Да, я видела ваши рассуждения. Но вот уже к своей прогрессии привязалась
Спасибо за информацию о константах 2508 - 3480. Можно, значит, начинать проверку с константы 3534. Правильно? Ну, а если с моим шагом 108, то с константы 3588. Мой шаг крупнее однако, меньше проверять

[Pavlovsky]

На всякий случаю повторю для констант от 2508 до 3480 я целенаправлено брал только числа Смита вида 4mod9. Совсем не факт, что нельзя построить МК с маленькой константой используя другие числа. Хотя пока все найденные МК состоят из чисел вида 4mod9. Есть и другие доводы в пользу этих чисел. Их больше половины среди чисел Смита и они обладают "хорошими" аддитивными свойствами.

[svb]

Забыв, что в программу нельзя подставлять нечетные $S$, запустил ее для натурального ряда с суммой $S=111$ и чуть не упал со стула, когда посыпались квадраты типа:

  1   2  34  33   9  32 
 31  27  11   7  22  13 
 29  14  17  21  12  18 
  4  28   5  36  35   3 
 30  15  24   6  10  26 
 16  25  19   8  23  20 
  1: S=111  p2,4,6,8=0 0 0 0

Квадраты, естественно, были уж никак не пандиагональными, но даже не магическими. Бросился искать ошибку в тексте программы, судорожно считал суммы по остаткам. Куда ни гляну, везде в остатке 1 (mod 10)... Нашел: 3-й и 6-й столбец - суммы разные. Но почему? Это же последняя проверка, там должно получаться на автомате после проверки 3-ей строки! И тут до меня дошло - сумма 9 элементов углового квадрата равна $9*S div 2$ в программе, но для этого необходимо, чтобы $S$ была четной. Все встало на свои места, ух.
Более спокойный стал проверять для $S=114$, но решения не находились. А у меня сейчас дополнительно выводится количество задействованных чисел из основного массива по всем парам. Пар то много, а вот задействованных чисел всего 36, а это минимум. И стали меня одолевать сомнения, какое же число из $1,2,...,37$ оказалось незадействованным? Сейчас то я догадываюсь, что это число 19, но я не стал испытывать судьбу и изменил сумму на $S=120$, решения пошли быстро:

  1   2  37  36  34  10 
 35  32  11   7  12  23 
 26  27   9  19  15  24 
  4   6  30  39  38   3 
 33  28  17   5   8  29 
 21  25  16  14  13  31 
  1: S=120  p2,4,6,8=0 0 0 0

и, вроде , пандиагональные.

[Nataly-Mak]

Я выше приводила два пандиагональных квадрата 6-го порядка из произвольных натуральных чисел, принадлежащие Е. Слкуни; один из них с магической константой 150 (как идеальный квадрат Журбы), а второй - с константой 120. Квадрат с константой 120 тоже составлен из комплементарных пар с суммой в паре равной 40.
Как я понимаю, пандиагональный квадрат с константой 120 минимальный для произвольных натуральных чисел.

А вот почему программа не хочет строить пандиагональный квадрат из произвольных натуральных чисел с дьявольской магической константой 666?
Я попробовала, программа написала: "Очень много будет строк"

[Nataly-Mak]

Всё, опять застряла, с константой 5856 квадрат не строится

Вот построила по своему алгоритму построения идеальных квадратов 6-го порядка, подобных квадрату Журбы, идеальный квадрат из произвольных натуральных чисел с дьявольской магической константой 666:

3 199 53 209 43 159
167 75 117 65 127 115
133 69 183 79 173 29
193 49 143 39 153 89
107 95 157 105 147 55
63 179 13 169 23 219

Построила вручную, пока программа искала квадрат с константой 5856
(а программа svb перед дьявольской константой пасует )

Этот алгоритм подробно описан в статье "Нетрадиционные пандиагональные квадраты". Достаточно составить 7 арифметических прогрессий длины 7 с одинаковой разностью $b$, такие, что первые члены этих прогрессий образуют арифметическую прогрессию с разностью $c$. Обозначим первый член первой арифметической прогрессии $a$, $S$ - магическая константа квадрата. Тогда достаточно подобрать a, b, c, удовлетворяющие следующему условию:
a + 3(b + c) = S/6.
В приведённом примере я выбрала a = 3, b = 10, c = 26.
Составив арифметические прогрессии, получаем примитивный квадрат 7х7, вычёркиваем в этом примитивном квадрате 4-ую строку и 4-ый столбец, получаем примитивный квадрат 6х6, который элементарно превращается в идеальный квадрат с помощью матричного преобразования.

[Nataly-Mak]

Итак, программа перестала давать результаты.

svb
есть новые идеи? Как будем проверять оставшиеся магические константы?

Да, кстати, Pavlovsky, вы, может быть, расскажете нам, как проверяли магические константы 2508 - 3480? Надо же проверить оставшиеся константы. По программе svb уже ничего не получается, прогнала несколько тысяч разных комплектов отклонений, наскучило это занятие. Надо что-то другое придумывать. А у вас ведь есть какой-то алгоритм проверки. Расскажите, пожалуйста. Я уже поняла, что вы брали только смиты вида 4(mod 9). А что дальше? По какому алгоритму строили пандиагональный квадрат из таких смитов?
Я уже в программу svb ввела массив смитов вида 4(mod 9), всё равно не строятся квадраты

[Pavlovsky]

Похожая идея проскакивала.
Алгоритм построения пандиагонального МК 6х6
1. Сформировать все четверки из чисел Смита с суммой 2/3 от заданной магической суммы.
2. Сформировать из четверок все наборы по 9 штук четверок, состоящие из различных чисел.
3. Из каждого набора сформировать прямоугольник 4х9. Это будет полумагический прямоугольник! Где сумма чисел в строке (9 чисел) будет 3/2 от магической суммы, а сумма чисел в колонке (4 числа) будет 2/3 от магической суммы.
4. Далее из каждой пары строк прямоугольника надо составить 3 шестерки.

Если все пункты будут выполнены, то есть гипотеза, что из заданного набора чисел можно построить пандиагональный МК 6х6.

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

Проверил магические константы от 2508 до 3480 с шагом 54. Использовал только числа Смита вида 4mod9. Во всех случаях пункт 2 не выполнился. То есть для заданных констант нельзя сформировать 9 четверок, состоящих из различных чисел.

Первый пункт алгоритма выполняется мгновенно.
А вот второй пункт начинался хорошо. Для маленьких магических констант выполнялся шустро. Но далее пошло все очень медленно. Для магической константы 3480 поиск велся 10 часов!

[Nataly-Mak]

Интересный алгоритм. Пункты 1-2 очень похожи на алгоритм svb. Далее по-другому. Но, как я поняла, до пункта 3 вы ни разу не дошли и потому алгоритм до конца не отработан.

[Nataly-Mak]

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

Для магической константы 3480 поиск велся 10 часов!

Стало всем понятно, что проверка потенциальных магических констант для пандиагональных квадратов из смитов задача очень сложная и требует много времени.
Нам осталось проверить потенциальные константы вида 54k + 24, k = 65, 66, ..., 109.
Констант довольно много. Можно представить, сколько понадобится времени, если на проверку одной константы потребовалось 10 часов. А с увеличением констант время будет увеличиваться стремительно.

А между тем есть хорошая программа, хочу о ней напомнить. Сначала я её выложила сама в ответ на просьбы Garik2 дать программу покрутить. Затем её выложил svb. Он изменил в программе верхнюю границу магической константы, к тому моменту это было значение 8340. Кроме того, он скомпилировал программу новым компилятором, и она стала работать раз в 20 быстрее.

Я попробовала выложенную svb программу, она действительно выполняется намного быстрее.
Но теперь опять надо изменить условия. Во-первых, надо ввести новые границы для магической константы, во-вторых, надо уменьшить исходный массив смитов, так как магическая константа уменьшилась. С новыми условиями программа будет работать ещё быстрее! Область поиска стала намного меньше.

Ещё раз напомню, что эта программа строит пандиагональные квадраты 6-го порядка из смитов вида 9k + 4. Она составлена на основе общей формулы для пандиагонального квадрата 6-го порядка с неизвестной магической константой (это 17 свободных переменных), но по шаблону, состоящему из вычетов 4 (все одинаковые вычеты в шаблоне).
Сама много пыталась покрутить программу. Делала так: задавала переменным нескольких первых циклов конкретные значения. В этом случае программа находила решения быстро.

Замечу, что в силу специфики программы (в программе все смиты разбиваются на три группы, чтобы уменьшить число значений, пробегаемых переменными вложенных циклов; если переменные будут пробегать все значения массива смитов, время выполнения программы станет вообще неприемлемым) она не даёт полного заключения о невозможности построения пандиагональных квадратов из смитов указанного вида с магическими константами в заданном диапазоне. Но она может найти некоторые из таких квадратов, если они существуют. А это уже немало!

Алгоритм svb тоже позволяет находить только некоторые пандиагональные квадраты и не даёт однозначного ответа о существовании квадрата с той или иной магической константой.

[Nataly-Mak]

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

Далее, лучше программу, основанную на общей формуле, делать для проверки заданной магической константы, это уменьшит количество свободных элементов на единицу. У меня сейчас программа сделана для проверки сразу всех магических констант из заданного диапазона, это не очень хорошо. Думаю переделать программу с учётом этих замечаний. Тогда можно попробовать проверять потенциальные магические константы по одной. Так будет вернее.

[Nataly-Mak]

Нацелилась на квадрат с магической константой 5856. Сгенерировала несколько массивов по 36 смитов, дающих такую константу. Вот три из них:

4  22  58  85  94  121  166  265  319  346  454  526  535  562  634  706  778  913  922  958  1111  1165  1219  1282  1507  1633  1642  1678  1795  1822  1858  1894  1903  1966  2038  2155

4  22  94  121  166  265  274  319  346  355  382  391  454  634  706  778  913  922  958  985  1111  1165  1219  1255  1282  1507  1633  1678  1795  1822  1858  1894  1903  1921  1966  2038 

4  58  85  94  121  202  265  274  319  355  382  391  517  562  634  706  778  895  913  922  1111  1165  1219  1255  1282  1633  1642  1795  1822  1858  1894  1903  1921  1966  2038  2155

Похоже массивов будет много.

Но вот программа svb выдаёт такую информацию: максимальное число массива смитов для данной магической константы 3865, всего задействовано смитов 150. Это в случае, если берутся все смиты от 4 до 3865. А если брать только смиты вида 9k + 4, то задействовано получается 76 чисел (последним является то же самое число 3865). Имеем уменьшение количества чисел почти в два раза. Естественно и программа svb работает в этом случае быстрее. Я попробовала несколько раз прогнать её для таких смитов, ускорение заметное.
В этом случае я использую файл numb.txt в соответствии с инструкцией.

svb
есть вопрос по этому поводу. Если поместить в файл numb.txt точно 76 смитов указанного вида (от 4 до 3865), то программа почему-то не хочет работать с таким набором чисел. Тогда я несколько увеличиваю массив (но добавляю смиты такого же вида), в этом случае программа работает. Почему так?