2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 63, 64, 65, 66, 67  След.
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение25.03.2015, 14:38 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение26.03.2015, 08:37 
Заблокирован
Аватара пользователя


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 дырками:

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

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение26.03.2015, 12:08 
Заблокирован
Аватара пользователя


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 дырками:

Код:
1031 599 1049 59 101 1229 419
179 719 191 1193 929 401 875*
269 1151 173 839 263 971 821
1277 773 521 641 761 509 5
461 311 1019 443 1109 131 1013
407* 881 353 89 1091 563 1103
863 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) :?:

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение27.03.2015, 10:33 
Заблокирован
Аватара пользователя


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$
Неправильная комплементарная пара (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):

Код:
431 827 347 71 1283 977 593
1163 1097 1103 107 383 5 671*
17 281 983 521 1181 1193 353
653 617 1061 647 233 677 641
941 101 113 773 311 1013 1277
623* 1289 911 1187 191 197 131
701 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-го порядка из различных простых чисел я построила давно (ещё ничего не зная о методе точных ортогональных покрытий массива):

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

$K=1282, S=4487$

(см. статью )

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение28.03.2015, 06:27 
Заблокирован
Аватара пользователя


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 :-)

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение28.03.2015, 09:27 
Заблокирован
Аватара пользователя


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. И опять всё сначала, по тому же кругу.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение30.03.2015, 07:06 
Заблокирован
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение31.03.2015, 09:25 
Заблокирован
Аватара пользователя


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.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение01.04.2015, 09:18 
Заблокирован
Аватара пользователя


22/03/08

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

Изображение

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

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

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

Ура! Прошло :D

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение04.04.2015, 17:41 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

$K=1282, S=4487$

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение05.04.2015, 15:07 
Заблокирован
Аватара пользователя


22/03/08

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

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение05.04.2015, 23:05 
Заслуженный участник


20/08/14
11065
Россия, Москва
Nataly-Mak в сообщении #1000505 писал(а):
Ну, а теперь осталась всего одна потенциальная магическая константа - 4529.
Готовьтесь к полному перебору, у меня решения с данной константой не найдено.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение08.04.2015, 07:27 
Заблокирован
Аватара пользователя


22/03/08

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

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

$K=1294, S=4529$

Программа пыхтит :-) Скоро и конец проверке.

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение12.04.2015, 06:34 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

$K=1294, S=4529 $

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

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение12.04.2015, 10:17 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

$K=1402, S=3505$

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

Код:
103 59 163 233 139 293
229 257 307 131 13 53
283 17 67 173 181 269
61 149 157 263 313 47
277 317 199 23 73 101
37 191 97 167 271 227

$K=330, S=990$

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

Код:
227 617 677 431 1217 1307 137
1259 827 1061 509 521 167 269
347 929 1187 17 557 719 857
89 479 29 659 1289 839 1229
461 599 761 1301 131 389 971
1049 1151 797 809 257 491 59
1181 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.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 63, 64, 65, 66, 67  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group