Дьявольские магические квадраты из простых чисел

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

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

Взяла массив с константой комплементарности K=51806. В массиве 360 комплементарных пар. И ничего не хочет складываться :-(

Покажу образец (напомню, что образцом я называю квадрат подобный искомому решению, то есть обладающий всеми нужными свойствами):

Код:

21337 28813 29683 36187 6115 13477 21313 30427 37483 44707
20245 30343 37369 44089 14527 20959 28375 35203 35209 5827
27943 34309 41017 4813 12433 19447 29527 37399 44053 13759
28537 36457 44341 13723 19309 26863 34171 40063 10657 11383
33493 39979 9649 17215 18457 28615 35533 43093 13687 19273
35437 42187 12763 19237 25903 32569 39043 9619 16369 24733
38119 8713 16273 23191 33349 34591 42157 11827 18313 25867
41149 11743 17635 24943 32497 38083 7465 15349 23269 32377
7753 14407 22279 32359 39373 46993 10789 17497 23863 31573
16597 16603 23431 30847 37279 7717 14437 21463 31561 39019
14323 21379 30493 38329 45691 15619 22123 22993 30469 36415

$K=51806, S=284933$
В этом решении много не простых чисел, однако нет перекосов: все числа в диапазоне, отрицательных чисел нет. Вполне хороший образец.

Кто-нибудь может попытаться построить искомый квадрат по приведённому образцу.
Я строю по образцу так: задаю значения нескольких свободных элементов из образца, например, 16 элементов. Это уменьшает количество свободных переменных (которых в общей формуле 40).
Далее поиск по общей формуле.
Даже если остаётся 24 свободных элемента, перебор всё равно зашкаливает, тем более, что массив чисел в данном примере огромный.
Можно попробовоть потенциальные массивы поменьше.

Замечу, что в образце все 40 свободных элементов простые числа. Можно выбирать любые свободные элементы (и в любом количестве) для фиксирования.

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

Отложила идеальные квадраты 11-го порядка на время, что-то увязла.
Возвращаюсь к задаче минимизации решений для порядков 7-10.

Для порядка 7 я улучшила результат alexBlack - решение с магической константой 5411, построив идеальный квадрат с магической константой 4613. Это решение дано как известное на начало конкурса.
Остались всего две потенциальные магические константы: 4529 и 4487.

Начинаю с минимальной - $S=4487$ . Ей соответствует центральный элемент 641 и константа ассоциативности $K=1282$ .
Имеем массив точно из 24 комплементарных пар:

Код:

5  23  53  59  89  101  131  173  179  191  233  251  263  269  311  353  401  419  443  461  509  521  563  599  683  719  761  773  821  839  863  881  929  971  1013  1019  1031  1049  1091  1103  1109  1151  1181  1193  1223  1229  1259  1277

Это хорошо: строить квадрат надо только из одного потенциального массива, состоящего точно из 49 чисел.

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

С ходу нашлось решение с 2 дырками:

Код:

89 1259 1151 179 1229 269
563 683 929 461 263 725*
509 443 233 1109 251 1181
1223 5 641 1277 59 401
1031 173 1049 839 773 521
557* 1019 821 353 599 719 419
53 1103 131 23 1193 971

$K=1282, S=4487$
Всего одна неправильная комплементарная пара (557, 725); при этом одно число в паре простое, так что, формально в решении одна дырка - не простое число 725, но фактически всё-таки 2 дырки.

Существует ли решение :?:

"Дырявые полуфабрикаты", конечно, плохо. Однако не дырявые найти не так просто.

Можно попробовать доказать несуществование решения без перебора.
12d3 мастер таких доказательств.

12d3
ау! Не попытаетесь доказать?

В крайнем случае, остаётся полный перебор. Но для этого надо переписать мою программу на C++ (с QBASIC).
Кто готов помочь?

А пока кручу программу, у меня идёт случайное задание (случайная генерация) первых двух переменных из 12.
Один такой проход (с оставшимися 10 переменными) выполняется достаточно быстро. Всего таких проходов будет 2256.

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

Показанному выше решению с 2 дырками соответствует следующий шаблон из вычетов по модулю 4:

Код:

3  1  3  3  3  1  1 
3  3  3  1  1  3  1 
1  1  3  1  1  3  1 
1  3  1  1  1  3  1 
1  3  1  1  3  1  1 
1  3  1  1  3  3  3 
1  1  3  3  3  1  3 

Вычет 1 – 27 шт.
Вычет 3 – 22 шт.

Заданный массив комплементарных пар простых чисел имеет такое разделение в соответствии с вычетами по модулю 4:

Вычет 1 - 24 шт.

Код:

5  53  89  101  173  233  269  353  401  461  509  521  761  773  821  881  929  1013  1049  1109  1181  1193  1229  1277

Вычет 3 - 24 шт.

Код:

23  59  131  179  191  251  263  311  419  443  563  599  683  719  839  863  971  1019  1031  1091  1103  1151  1223  1259 

Плюс центральный элемент 641 -> вычет 1.

Очевидно, что представленный шаблон не подходит для данного массива чисел.

Тем временем программа нашла ещё одно решение с 2 дырками:

Код:

599 1049 59 101 1229 419
719 191 1193 929 401 875*
1151 173 839 263 971 821
773 521 641 761 509 5
311 1019 443 1109 131 1013
407* 881 353 89 1091 563 1103
53 1181 1223 233 683 251

$K=1282, S=4487$
Здесь 2 дырки и формально, и фактически: неправильная комплементарная пара (407, 875).
Этому решению соответствует такой шаблон из вычетов по модулю 4:

Код:

3  3  1  3  1  1  3 
3  3  3  1  1  1  3 
1  3  1  3  3  3  1 
1  1  1  1  1  1  1 
1  3  3  3  1  3  1 
3  1  1  1  3  3  3 
3  1  1  3  1  3  3 

Вычет 1 – 25 шт
Вычет 3 – 24 шт

Этот шаблон годится для заданного массива чисел. Можно смело пробовать найти решение по этому шаблону.

Вопрос: много ли можно составить шаблонов из вычетов по модулю 4 для идеального квадрата 7-го порядка, состоящих из равного количества вычетов 1 и 3 (не считая центрального элемента, которому соответствует вычет 1) :?:

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

Новое решение с 2 дырками:

Код:

881 269 1229 131 5 1109 
719 251 521 971 1181 821 
47* 1049 509 929 263 599 
443 1103 641 179 839 89 
1019 353 773 233 1235* 191 
101 311 761 1031 563 1259 
1277 1151 53 1013 401 419

$K=1282, S=4487$
Неправильная комплементарная пара (47, 1235) содержит одно простое число, так что формально дырка одна.

И новый шаблон из вычетов по модулю 4, соответствующий этому решению:

Код:

3  1  1  1  3  1  1 
3  3  3  1  3  1  1 
3  3  1  1  1  3  3 
1  3  3  1  3  3  1 
3  3  1  1  1  3  3 
1  1  3  1  3  3  3 
1  1  3  1  1  1  3 

Этот шаблон тоже годится для заданного массива простых чисел (по распределению вычетов).

Параллельно начала крутить программу для второй потенциальной магической константы – 4529.
Здесь тоже имеем один потенциальный массив, состоящий точно из 49 простых чисел:

Код:

5  11  17  71  101  107  113  131  191  197  233  263  281  311  317  347  353  383  431  467  521  593  617  641  647  653  677  701  773  827  863  911  941  947  977  983  1013  1031  1061  1097  1103  1163  1181  1187  1193  1223  1277  1283  1289

Решение с двумя дырками пока нашлось только одно и искалось оно долго (по сравнению с решением для магической константы 4487):

Код:

827 347 71 1283 977 593 
1097 1103 107 383 5 671*
281 983 521 1181 1193 353 
617 1061 647 233 677 641 
101 113 773 311 1013 1277 
623* 1289 911 1187 191 197 131 
317 11 1223 947 467 863

$K=1294, S=4529$

Итак, весьма и весьма интересно: существуют ли решения с магическими константами 4487 и 4529 :?:

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

-- Пт мар 27, 2015 11:49:36 --

Опять вспомнила метод точных ортогональных покрытий массива.
Для порядка 7 и все цепочки составить не проблема. Я уже делала это, когда пыталась применить этот метод для поиска минимального пандиагонального квадрата 7-го порядка из простых чисел. БД всех цепочек не такая уж и большая. Поэтому вполне реально с ней поработать.
Но вот метод мне так и не удалось применить до конца в случае с пандиагональными квадратами.
Зато метод прекрасно работает для ассоциативных квадратов! Найти два точных ортогональных покрытия для ассоциативного квадрата - задачка совсем простенькая. А плюс ещё два (попарно ортогональных) для идеального квадрата? Никто ещё не попробовал :-)

Предлагаю всем, в первую очередь whitefox и 12d3 (они уже с этим методом работали).
Задача ведь и вправду очень интересная.
Массив задан конкретный, точно из 49 чисел. Два точных ортогональных покрытия этого массива могу выдать прямо сейчас. Это будет ассоциативный квадрат.

-- Пт мар 27, 2015 12:06:57 --

Наименьший ассоциативный квадрат 7-го порядка из различных простых чисел я построила давно (ещё ничего не зная о методе точных ортогональных покрытий массива):

Код:

1277 101 1091 173 1019 773
59 863 599 881 1049 23
1193 563 821 761 131 839
311 929 641 353 971 251
1151 521 461 719 89 1103
233 401 683 419 1223 269
263 1109 191 1181 5 1229

$K=1282, S=4487$

(см. статью )

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

Ещё программку неплохо бы сделать, которая проверяла бы комплект из 4-х точных попарно ортогональных покрытий (вдруг такой комплект найдётся) на предмет составления из него идеального квадрата.
Хотя... может быть, для идеального квадрата не так, как для пандиагонального. Для пандиагонального было установлено, что не любой комплект из 4-х точных попарно ортогональных покрытий массива даёт пандиагональный квадрат.

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

Эксперимент
вчера начала, сегодня должен завершиться.

Как я уже говорила, в программе 12 свободных переменных, каждая из которых должна пробежать 48 значений (48 чисел в массиве, 49-ое число - центральный элемент: не варьируется).
Делаю так: фиксирую переменную внешнего цикла, остаётся 47 чисел для перебора и 11 свободных переменных).
Вчера крутила с утра до вечера, сейчас продолжаю, сегодня точно закончится.
Итак, на проход одного внешнего цикла требуется два дня. Всего таких проходов будет 48. Так что, полный перебор реален. Конечно, моя программа ужасная тихоходка. Но лучшей пока нет у меня, помочь с программой желающих нет :-(

А надо просто переписать её на C++, ничего не изменяя, один в один.

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

(Оффтоп)

Код:

443  881  179  719  1229  5  1031 
 509  683  863  761  1109  101  461 
 1151  23  971  269  125  929  1019 
 1049  89  1091  641  191  1193  233 
 263  353  1157  1013  311  1259  131 
 821  1181  173  521  419  599  773 
 251  1277  53  563  1103  401  839 

101  599  461  1259  1223  5  839 
 971  563  1031  53  179  863  827 
 1151  353  761  773  1091  269  89 
 173  263  881  641  401  1019  1109 
 1193  1013  191  509  521  929  131 
 455  419  1103  1229  251  719  311 
 443  1277  59  23  821  683  1181 

719  599  353  1259  1109  5  443 
 1223  131  233  971  521  419  989 
 821  263  1013  1229  101  179  881 
 191  251  773  641  509  1031  1091 
 401  1103  1181  53  269  1019  461 
 293  863  761  311  1049  1151  59 
 839  1277  173  23  929  683  563 

761  353  59  1229  1031  5  1049 
 971  1193  881  131  269  1019  23 
 509  101  683  1109  545  821  719 
 191  839  863  641  419  443  1091 
 563  461  737  173  599  1181  773 
 1259  263  1013  1151  401  89  311 
 233  1277  251  53  1223  929  521 

269  599  1103  311  1019  5  1181 
 1223  131  881  23  821  419  989 
 521  173  563  1229  839  929  233 
 1031  1091  773  641  509  191  251 
 1049  353  443  53  719  1109  761 
 293  863  461  1259  401  1151  59 
 101  1277  263  971  179  683  1013 

1181  761  191  269  971  5  1109 
 263  401  1151  251  839  929  653 
 1049  773  563  821  683  419  179 
 89  59  1229  641  53  1223  1193 
 1103  863  599  461  719  509  233 
 629  353  443  1031  131  881  1019 
 173  1277  311  1013  1091  521  101 

 521  599  1013  1229  929  5  191 
 971  563  89  23  1151  863  827 
 179  59  1181  773  443  821  1031 
 1019  1109  881  641  401  173  263 
 251  461  839  509  101  1223  1103 
 455  419  131  1259  1193  719  311 
 1091  1277  353  53  269  683  761 

1019  863  131  1031  599  5  839 
 269  461  353  773  401  1259  971 
 1103  719  521  1193  587  191  173 
 233  53  1223  641  59  1229  1049 
 1109  1091  695  89  761  563  179 
 311  23  881  509  929  821  1013 
 443  1277  683  251  1151  419  263 

719  761  863  1031  509  5  599 
 263  401  179  1013  1049  929  653 
 839  311  101  821  173  1091  1151 
 1223  1193  1229  641  53  89  59 
 131  191  1109  461  1181  971  443 
 629  353  233  269  1103  881  1019 
 683  1277  773  251  419  521  563

$K=1282, S=4487$

-- Сб мар 28, 2015 07:41:24 --

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

Я что-то никак не соображу. Мне кажется, что не достаточно. Что скажете, коллеги?

-- Сб мар 28, 2015 07:51:01 --

Хотя... вот что сообразила: если с элементом 1277 решение не найдётся, то проверять симметричный ему элемент 5 уже не надо. Правильно?
Тогда количество проходов уменьшается вдвое. Ура! Не 48, а всего 24 :-)

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

Всё, эксперимент завершился, найдено ещё одно решение с 2 дырками:

Код:

863  881  269  1229  131  5  1109 
23  719  251  521  971  1181  821 
1091  47  1049  509  929  263  599 
1193  443  1103  641  179  839  89 
683  1019  353  773  233  1235  191 
461  101  311  761  1031  563  1259 
173  1277  1151  53  1013  401  419 

$K=1282, S=4487$
Итак, осталось 23 прохода с фиксированной переменной внешнего цикла.

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

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

Первая оптимизация программы поиска идеального квадрата 7-го порядка есть!
Это было достигнуто сменой общей формулы.

Как совершенно верно писал svb в теме "Магические квадраты", общие формулы идеальных квадратов получаются разные. И какую же выбрать? Это очень интересный и важный вопрос - об эффективности общей формулы.
В теме "Магические квадраты" maxal очень давно представил самую эффективную формулу пандиагонального квадрата 5-го порядка (а также магических квадратов 4-го и 5-го порядков). К сожалению, он не пошёл дальше. А вот сейчас очень кстати была бы самая эффективная общая формула идеального квадрата 7-го порядка.

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

(Оффтоп)

Код:

m0 = -m48+2/7*S
m1 = -m47+2/7*S
m2 = -m46+2/7*S
m3 = -m45+2/7*S
m4 = -m44+2/7*S
m5 = -m43+2/7*S
m6 = +m43+m44+m45+m46+m47+m48-5/7*S
m7 = -m41+2/7*S
m8 = -m40+2/7*S
m9 = -m39+2/7*S
m10 = -m38+2/7*S
m11 = -m37+2/7*S
m12 = -m36+2/7*S
m13 = +m36+m37+m38+m39+m40+m41-5/7*S
m14 = +m40+m41+m46+m47+m48-4/7*S
m15 = -m36+m39+m40+m41-m43-m44+m45+m46+2*m47+m48-4/7*S
m16 = -m37+m38+m39+m40-m43+2*m46+m47+m48-4/7*S
m17 = +m37+m39+m43+m45+m47-4/7*S
m18 = +m36+m37+m38-m39+m44-m45-m46-2*m47-m48+3/7*S
m19 = -m38-m39-2*m40-m41+m43-2*m46-2*m47-m48+10/7*S
m20 = -m37-m38-m39-m40-m41-m45-m46-m47-m48+10/7*S
m21 = -m22-m23-m24-m25-m26-m27+S
m22 = -m38-2*m39-2*m40-2*m41+m43+m44-m45-3*m46-3*m47-2*m48+15/7*S
m23 = +m36+m37-m39-m40+m43-m45-2*m46-3*m47-2*m48+8/7*S
m24 = +1/7*S
m25 = -m36-m37+m39+m40-m43+m45+2*m46+3*m47+2*m48-6/7*S
m26 = +m38+2*m39+2*m40+2*m41-m43-m44+m45+3*m46+3*m47+2*m48-13/7*S
m27 = -m36+m40-m43-m44+m46+m47+1/7*S
m28 = -m29-m30-m31-m32-m33-m34+S
m29 = +m38+m39+2*m40+m41-m43+2*m46+2*m47+m48-8/7*S
m30 = -m36-m37-m38+m39-m44+m45+m46+2*m47+m48-1/7*S
m31 = -m37-m39-m43-m45-m47+6/7*S
m32 = +m37-m38-m39-m40+m43-2*m46-m47-m48+6/7*S
m33 = +m36-m39-m40-m41+m43+m44-m45-m46-2*m47-m48+6/7*S
m34 = -m40-m41-m46-m47-m48+6/7*S
m35 = -m36-m37-m38-m39-m40-m41+S
m42 =-m43-m44-m45-m46-m47-m48+S

Программа по этой формуле работает очень долго (имеется в виду полный перебор).

Тогда решила попробовать найти другую общую формулу. Для этого сама составила систему линейных уравнений, описывающих идеальный квадрат 7-го порядка, и решила её в онлайн-решателе.
И да! Формула получилась совсем другая. Нет, по количеству свободных и зависимых переменных она такая же: 12 свободных переменных из 24 при заданной константе ассоциативности. Но вот порядок задания свободных переменных и вычисления зависимых переменных в моей формуле совсем другой.
Эффект от новой формулы получился хороший. Сейчас на один проход внешнего цикла требуется всего 4-5 часов (по первой программе на это требовалось два дня).

Покажу полученную мной общую формулу идеального квадрата 7-го порядка:

Код:

X(1) = (2*X(18)-2*X(20)- K+2*X(12)+2*X(6)-2*X(14)+2*X(24))/2 
X(10) = - X(16)+ X(3)+ X(18)+ X(5)- X(20)- X(21)- K+ X(12)+2*X(6)-2*X(14)+ X(15)+ X(24) 
X(11) = -(-2*X(16)+4*X(3)-2*X(20)-2*X(21)+3*K-2*X(23)-4*X(14)-2*X(15)+2*X(24))/2 
X(13) = X(16)- X(18)- X(5)+3*K- X(12)-2*X(6)- X(15) 
X(17) = -(2*X(3)+2*X(18)-5*K+2*X(6)-2*X(14)+2*X(15)+2*X(24))/2 
X(19) = - X(16)+ X(3)- X(20)- X(21)+ K+ X(6)- X(14)+ X(24) 
X(2) = -(-2*X(16)+4*X(3)+2*X(18)-2*X(20)- K-2*X(23)+2*X(6)-4*X(14)+2*X(24))/2 
X(22) = - X(16)+ X(3)- X(5)+ X(20)+ K- X(23) 
X(4) = -(-2*X(3)+2*X(18)+2*X(5)-2*X(21)-7*K+2*X(23)+4*X(12)+4*X(6)+2*X(15))/2 
X(7) = - X(16)+ X(18)- X(21)+ X(12)+ X(6)- X(14)+ X(15) 
X(8) = - X(3)+ X(5)+ X(23)+ X(14)- X(24) 
X(9) = - X(16)+2*X(3)- X(5)+3*K-2*X(23)- X(12)-2*X(14)- X(15)+ X(24)

Всего надо вычислить 12 зависимых элементов и перебрать 12 свободных из 48 чисел массива.

Запустила сразу две копии программы. Мне надо сделать всего 24 прохода внешнего цикла. За несколько дней надеюсь управиться.

Есть ещё, наверное, не один вариант общей формулы идеального квадрата 7-го порядка. Например, такую формулу можно получить по программе, выложенной svb.
Такая формула есть и у maxal.

maxal
может быть, покажете свою формулу :?:

-- Пн мар 30, 2015 08:25:06 --

Написала программу поиска и по шаблону из вычетов по модулю 4:

Код:

3  3  1  3  1  1  3 
3  3  3  1  1  1  3 
1  3  1  3  3  3  1 
1  1  1  1  1  1  1 
1  3  3  3  1  3  1 
3  1  1  1  3  3  3 
3  1  1  3  1  3  3 

Эта программа вообще выполняется менее часа! Решение не найдено.
Но тут беда в том, что шаблон такой не единственный, их будет, наверное много (сколько :?:

).
Поэтому нельзя утверждать, что решения не существует вообще, если оно не нашлось по одному из шаблонов.

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

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

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

Код:

1049  5  1031  1229  59  353  761 
23  1019  269  131  881  1193  971 
719  821  545  1109  683  101  509 
1091  443  419  641  863  839  191 
773  1181  599  173  737  461  563 
311  89  401  1151  1013  263  1259 
521  929  1223  53  251  1277  233 

1103  59  1031  1019  353  521  401 
131  683  773  101  461  1229  1109 
839  1091  47  1013  1259  5  233 
311  563  863  641  419  719  971 
1049  1277  23  269  1235  191  443 
173  53  821  1181  509  599  1151 
881  761  929  263  251  1223  179 

761  131  1031  509  419  443  1193 
929  311  1103  5  401  1019  719 
683  821  317  1259  1181  173  53 
233  1013  191  641  1091  269  1049 
1229  1109  101  23  965  461  599 
563  263  881  1277  179  971  353 
89  839  863  773  251  1151  521 

509  131  1031  1049  1193  401  173 
1091  821  839  53  863  761  59 
263  599  695  563  179  929  1259 
269  1181  311  641  971  101  1013 
23  353  1103  719  587  683  1019 
1223  521  419  1229  443  461  191 
1109  881  89  233  251  1151  773 

233  521  1031  1193  1277  179  53 
401  839  353  311  419  1013  1151 
821  1223  125  1181  191  773  173 
563  23  1019  641  263  1259  719 
1109  509  1091  101  1157  59  461 
131  269  863  971  929  443  881 
1229  1103  5  89  251  761  1049 

$K=1282, S=4487$

В этой серии решений зафиксирован элемент $X(3)=1031$ .

Сейчас, пока программы работают, собираюсь посмотреть, как у нас дела с минимизацией решения для $n=8$ .
Пока найдено мной решение с магической константой 2520. Является ли оно минимальным?
Надо посмотреть внимательно на программу поиска таких квадратов. Нельзя ли что-то оптимизировать.

-- Вт мар 31, 2015 11:00:57 --

Любопытны два эквивалентных решения с 2 дырками; первое получено при фиксированном элементе $X(3)=1031$ , второе - при фиксированном элементе $X(3)=1019$ :

Код:

509  131  1031  1049  1193  401  173 
1091  821  839  53  863  761  59 
263  599  695  563  179  929  1259 
269  1181  311  641  971  101  1013 
23  353  1103  719  587  683  1019 
1223  521  419  1229  443  461  191 
1109  881  89  233  251  1151  773 

773  191  1019  1013  1259  59  173 
1151  461  683  101  929  761  401 
251  443  587  971  179  863  1193 
233  1229  719  641  563  53  1049 
89  419  1103  311  695  839  1031 
881  521  353  1181  599  821  131 
1109  1223  23  269  263  1091  509

$K=1282, S=4487$
Неправильная комплементарная пара в этих решениях (587, 695), одно число в паре простое; то есть формально в решениях одна дырка - не простое число 695.

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

Иллюстрация, опробовала новый хостинг для загрузки изображений :-)

Сейчас посмотрим, как это смотрится (если оно вообще сюда пройдёт).

Это работа двух копий программы поиска идеального квадрата 7-го порядка (минимального!) из различных простых чисел.
Каждая программа работает для своего фиксированного элемента X(3). Это один проход внешнего цикла.
Итак, уже 10 проходов выполнила, осталось всего 14.
Обратите внимание, как синхронно работают программы (по значению переменной первого вложенного цикла I5).
В первой программе решений с 2 дырками не найдено пока; во второй они есть, вы видите их на иллюстрации.

-- Ср апр 01, 2015 10:19:25 --

Ура! Прошло

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

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

Найдено такое интересное решение с 2 дырками:

Код:

173 761 101 53 1091 1031 
1151 1013 89 1049 563 599 
881 761 419 1103 353 509 
443 311 641 971 839 263 
929 179 863 521 401 821 
719 233 1193 269 131 1259 
191 1229 1181 521 1109 5

$K=1282, S=4487$

Дырки в этом решении особенные - это правильная комплементарная пара (521, 761), но... она повторена!
Этот квадрат идеальный, все числа в нём простые, но не различные.

Итак, завтра завершу проверку оставшихся проходов. И если решение не найдётся (а это, скорее всего, так и будет), начну проверку второй потенциальной магической константы - 4529.

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

Всё, проверка для минимальной магической константы идеального квадрата 7-го порядка из различных простых чисел (4487) закончена. Решение не найдено.
Ну, разумеется, я не исключаю ошибки. Программа вроде бы работала правильно, найдено довольно много решений с 2 дырками, проверяла эти решения, в них всё правильно.
Но... конечно, очень не помешала бы независимая проверка. Только некому её сделать :-(

Ну, а теперь осталась всего одна потенциальная магическая константа - 4529.
Приступаю к проверке этой константы. Опять, наверное, придётся выполнить полный перебор, если решения не существует. Если же оно есть, то может побыстрее найтись :-)

Dmitriy40 · 20/08/14 11867 Россия, Москва

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

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

Готовьтесь к полному перебору, у меня решения с данной константой не найдено.

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

Выполнила 10 проходов внешнего цикла, осталось 14.
Тоже найдено решение, полностью составленное из простых чисел, но одна комплементарная пара - (113, 1181) - повторена:

Код:

911 113 827 281 941 593 
1031 317 947 653 1283 107 
1223 1181 233 131 311 677 
17 101 647 1193 1277 1097 
983 1163 1061 113 71 521 
11 641 347 977 263 1103 
353 1013 467 1181 383 431 

$K=1294, S=4529$

Программа пыхтит :-)

Скоро и конец проверке.

На очереди минимизация решения для $n=8$ .
Замечу, что для $n=8$ и для пандиагональных квадратов из различных простых чисел задача минимизации не решена. Я много потратила времени на решение этой задачи, но пока безуспешно.
Jarek писал мне, что, возможно, вернётся к этой задаче. Увы, забыл вернуться :-)

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

Запустила последние два прохода. Решение не ожидается.
Итак, задача минимизации решения для $n=7$ решена.
Минимальный идеальный квадрат 7-го порядка из различных простых чисел имеет магическую константу 4613.

Ещё одно решение с повторенной комплементарной парой:

Код:

347 593 1283 977 5 1193 
641 1031 71 113 1013 677 
521 593 1103 911 197 17 
353 431 647 863 941 1061 
1097 383 191 701 773 107 
281 1181 1223 263 653 311 
1289 317 11 701 947 1163

$K=1294, S=4529$

Здесь повторенная комплементарная пара (593, 701). Хороший квадратик, ну всего двух чисел не хватило разных, пришлось вставить одинаковые :-)

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

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

Минимальные идеальные квадраты из различных простых чисел

$n=5$ (моё решение)

Код:

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

$K=1402, S=3505$

$n=6$ (автор maxal)

Код:

59 163 233 139 293 
257 307 131 13 53 
17 67 173 181 269 
149 157 263 313 47 
317 199 23 73 101 
191 97 167 271 227

$K=330, S=990$

$n=7$ (моё решение)

Код:

617 677 431 1217 1307 137
827 1061 509 521 167 269
929 1187 17 557 719 857
479 29 659 1289 839 1229
599 761 1301 131 389 971
1151 797 809 257 491 59
11 101 887 641 701 1091

$K=1318, S=4613$

И далее оценки магических констант для идеальных квадратов порядков 8 – 16 из различных простых чисел:

$n=8, 2040 \leqslant S \leqslant 2520$
$n=9, 12249 \leqslant S \leqslant 23319$
$n=10, 4200 \leqslant S \leqslant 46150$
$n=11, S \geqslant 26521$
$n=12, S \geqslant 8820$
$n=13, S \geqslant 49439$
$n=14, S \geqslant 16170$
$n=15, S \geqslant 74595$
$n=16, S \geqslant 21840$

Мной найдены решения:

$n=8, S=2520$
$n=9, S=23319$
$n=10, S=46150$

Решения представлены на текущий конкурс, поэтому покажу их после окончания конкурса.
Для $n>10$ пока неизвестно ни одного решения. Может быть, кто-то нашёл такие решения, но положил их под подушку :wink:

-- Вс апр 12, 2015 11:27:10 --

maxal
можно ли отправить в OEIS последовательность (минимальных магических констант идеальных квадратов из простых чисел) из 3-х членов?
Помнится, для пандиагональных квадратов из простых чисел последовательность минимальных магических констант A179440 сначала состояла тоже из 3-х членов; четвёртый член найден совсем недавно Jarek.

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

Дьявольские магические квадраты из простых чисел

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