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

[Nataly-Mak]

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

Минимальность регулярного решения (11,18191) доказана?

J. K. Andersen считает, что это решение минимальное:

Цитата:

This is probably minimal for 11 but has not been fully proven...

Эх, вот не умею читать
Сейчас сделала перевод, тут написано, что это решение, вероятно, минимальное, но не доказано.
Значит, минимальность этого решения не доказана!

[Pavlovsky]

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

Да, по этому пункту у вас есть замечательное авторское решение для N=10, полученное задолго до конкурса.

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

[Pavlovsky]

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

Значит, минимальность этого решения не доказана!

В более позднем сообщении Andersen пишет уже категорично:

Цитата:

(11,18191) has been proved minimal for d=11. This means the original puzzle is completely solved.

Так доказано или нет?

[Nataly-Mak]

А, ну да... я уж и забыла о более позднем сообщении.
В своё время я читала это сообщение и отметила его в теме "Антимагические квадраты"

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

Andersen доказал минимальность индекса (18191) квадрата Стенли 11-го порядка из простых чисел!
Итак, наименьший регулярный пандиагональный квадрат 11-го порядка из простых чисел построен. Теперь вопрос остаётся о нерегулярных пандиагональных квадратах.

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

Долгое время считалось, что наименьший пандиагональный квадрат 6-го порядка из (различных) простых чисел имеет магическую константу 486, пока не пришло письмо от Radko Nachev, в котором он сообщил, что минимальная константа равна 450.

-- Пт июн 28, 2013 11:55:09 --

Несколько минут назад:

Цитата:

1 15.00 Jarek Wroblewski Wroclaw, Poland 28 Jun 2013 07:36
2 7.07 Wes Sampson La Jolla, California, United States 27 Jun 2013 01:56

Мне кажется, что Jarek уже приближается к нижним границам для магических констант всех порядков N (эти границы показаны выше).
Не исключено, что он найдёт минимальные решения для нескольких N.

[Nataly-Mak]

(Оффтоп)

Только что вернулась из гостей. Смотрю, что в конкурсе...
А ничего особо нового, по-прежнему работает (вводит решения) один Jarek, ну и ещё тройка новых результатов была 29 июня, не рекордных, конечно.

Странно: неужели задача такая трудная, что поддаётся только одному участнику?
Прямо ума не приложу.

[dimkadimon]

Я нашёл нерегулярное решение для N=7 с суммой меньше 1597. Значит есть ответ на вопрос века. К сожалению я поднялся только на 0.01 балла...

[Pavlovsky]

dimkadimon в сообщении #742025 писал(а):

Я нашёл нерегулярное решение для N=7 с суммой меньше 1597.

Куда послать 500 рублей?

-- Пн июл 01, 2013 08:11:02 --

В связи с решением проблемы века, придется полностью изменить свои планы. Искать регулярные решения теперь не имеет смысла. Значит надо сразу начинать искать нерегулярные решения. Пока есть только одна идея, поиск по общей формуле. Для сокращения перебора используем теорему 3.3 (Россер). Наличие решеток тоже позволяет сократить перебор.

[dimkadimon]

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

В связи с решением проблемы века, придется полностью изменить свои планы. Искать регулярные решения теперь не имеет смысла. Значит надо сразу начинать искать нерегулярные решения. Пока есть только одна идея, поиск по общей формуле. Для сокращения перебора используем теорему 3.3 (Россер). Наличие решеток тоже позволяет сократить перебор.

На даный момент регулярные решения проще искать и поэтому я буду продолжать ими заниматься.

[Pavlovsky]

dimkadimon в сообщении #742034 писал(а):

На даный момент регулярные решения проще искать и поэтому я буду продолжать ими заниматься.

Я как то уже рассказывал анекдот. Про пьяницу, который искал потерянные часы под фонарем, потому что там светлее.

А тем временем:

1   15.00   Jarek Wroblewski   Wroclaw, Poland   1 Jul 2013 10:37
2   6.49   Wes Sampson   La Jolla, California, United States   27 Jun 2013 01:56

Уже нет сомнений Jarek Wroblewski штампует нерегулярные решения.

[Nataly-Mak]

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

Уже нет сомнений Jarek Wroblewski штампует нерегулярные решения.

У меня уже давно нет в этом сомнений
Так может, 500 рублей надо послать первому участнику, получившему нерегулярное решение для N=7? А таким участником наверняка является Jarek.
По развитию событий на данный момент можно предположить, что оба приза, учреждённые в конкурсе, выиграет Jarek. Плюс специальный приз от Pavlovsky

Я давно уже написала в этой теме, в чём была причина наших весьма скромных результатов. Мы слишком увлеклись алгоритмами Россера! То есть как раз подобно тому пьянице из анекдота искали решения там, где светлее (читай: проще).

[dimkadimon]

Возможно Jarek тоже ищет регулярные решения, но другие, которые легче найти...

[Nataly-Mak]

Мой контраргумент по этому пункту я уже озвучивала.
Повторюсь: примитивные квадраты (квадраты Стенли) для порядков больше 7 строить довольно сложно.
Для N=11 минимальный примитивный квадрат построил J. K. Andersen; следовательно, для данного порядка регулярное решение уже найдено.

Остаются порядки N=13,17,19 (в случаях для составных порядков N всё сложнее, так как примитивные квадраты должны удовлетворять дополнительным условиям).
Для порядка N=13 регулярные решения вполне можно поискать, так как примитивный квадрат для этого порядка, наверное, ещё не так сложно построить. Однако для порядков N=17, 19 я с алгоритмом Россера вообще ничего не добилась в своё время.
Может быть, и здесь ещё возможно поискать регулярные решения, так как на сегодня известны регулярные решения с очень большими магическими константами.

Что касается решений Jarek... тут я согласна с Pavlovsky: он давно уже вышел за границы регулярных решений.

-- Пн июл 01, 2013 18:21:02 --

Об алгоритмах...
Расскажу об очень давнем алгоритме построения классических магических квадратов 6-го порядка (это из статьи):

Цитата:

...я вспомнила про свой давнишний алгоритм построения традиционных магических квадратов 6-го порядка. Этот алгоритм я реализовала ещё на старой ЭВМ. Программа прекрасно строила традиционные магические квадраты 6-го порядка. Алгоритм был такой: с помощью функции случайных чисел формируется набор из 6 строк, состоящих из различных чисел, так что сумма чисел в каждой строке равна 111. Понятно, что числа эти выбираются случайным образом из массива первых 36 натуральных чисел. Получив такой набор, программа выполнила первый этап и переходит ко второму этапу: пытается превратить данный набор из 6 строк в полумагический квадрат, то есть добиться того, чтобы суммы чисел в столбцах тоже были равны 111 (это достигается путём перестановки чисел в строках). Этот этап выполним не для любого набора из 6 строк. Если же полумагический квадрат получить удаётся, программа переходит к третьему этапу: пытается превратить полумагический квадрат в магический, то есть добиться того, чтобы суммы чисел в главных диагоналях квадрата тоже были равны 111. Этот этап тоже не всегда выполним. Но если он выполнен, то магический квадрат построен. Покажу один из традиционных магических квадратов 6-го порядка, построенный по этой программе ещё на старой ЭВМ (рис. 5):

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

Когда начала заниматься построением наименьших магических квадратов из простых чисел, с успехом использовала этот алгоритм.
Наименьший МК 6-го порядка из (различных) простых чисел - это первый мой авторский квадрат, он внесён в OEIS - A164843.

Можно посмотреть применение данного алгоритма к построению нетрадиционных МК из простых чисел в той же статье.

Мне кажется, что этот алгоритм можно приспособить и для построения пандиагональных квадратов из простых чисел. Я не пробовала, но к коллегам часто с этим вопросом обращалась.
Например, у 12d3 есть замечательная программа построения нетрадиционных МК 6-го порядка из конкретного массива, состоящего из 36 чисел
(замечу, что конретный массив из 36 чисел сразу позволяет определить магическую константу квадрата). При этом программа строит все МК из заданного массива.
Теперь представим, что автор вставил в программу проверку пандиагональности каждого построенного МК. Это же очень просто сделать! И тогда программа точно скажет: составляется или не составляется из чисел заданного массива пандиагональный квадрат.

Кажется, в моих рассуждениях нет ошибки. Алгоритм должен работать.

Подчеркну: все приведённые алгоритмы объединяет одна особенность - заранее заданный массив чисел и, следовательно, заранее заданная магическая константа квадрата.

[dmd]

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

[Nataly-Mak]

dmd в сообщении #742222 писал(а):

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

Нет, это не ошибка, по крайней мере, при построении обычных МК из (различных) простых чисел. Я нашла по этому алгоритму МК до порядка 15, а вы подумали, что только для порядка 6

Мой коллега из Италии Stefano Tognon подключился в тему "Магические квадраты" намного позже того момента, как я нашла свой первый авторский квадрат 6-го порядка из простых чисел.
Оказалось, что у Stefano аналогичный алгоритм.
И вот итог: он строил по своим программам МК до порядка 64, кажется, сейчас точно не помню. Я с использованием его программ дошла тоже до какого-то большого порядка (можно всё это посмотреть в моих статьях).

Скажу вам больше: этот алгоритм работает тем лучше, чем больше порядок квадрата!
Удивитесь?
А нет ничего удивительного; просто с увеличением порядка в данном случае экспоненциальный взрыв не враг, а друг
Когда мы начали строить наименьшие МК из чисел Смита, удивились, что для маленьких порядков (N<11) программы Stefano не работают. А вот для больших порядков пожалуйста!
Вполне результативным оказался этот алгоритм

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

Я сейчас поищу статью S. Tognon, в которой он изложил свой алгоритм "случайного тыка", как вы его пренебрежительно называете. Статья написана на английском языке, он написал её для участия в международной конференции "Комбинаторные конструкции и их применение" (проходила в Украине). Статья была опубликована в сборнике, выпущенном оргкомитетом конференции. Кстати, я на ту конференцию представила свою статью "Магические кубы третьего порядка". Эта статья тоже опубликована.

-- Пн июл 01, 2013 22:14:23 --

Посмотрите статью A164843 в OEIS.

177, 120, 233, 432, 733, 1154, 1731, 2470, 3417, 4584, 6013, 7712, 9731, 12088, 14807, 17940, 21501, 25530, 30021, 35086, 40675, 46840, 53631, 61092, 69251, 78100, 87697, 98084, 109309, 121380, 134377, 148258, 163043 

Здесь указаны магические константы до порядка 35 включительно (кажется, в моей статье их больше).
Все МК для порядков N>5 построены мной. До порядка N=14 я пользовалась своей программой, а дальше - программой Stefano. Алгоритмы у нас, как я уже сказала, похожие.

Замечу, что всё это наименьшие магические квадраты из простых чисел.

Конечно, я не обещаю, что для пандиагональных квадратов этот алгоритм будет работать так же хорошо. Но для обычных МК он работает просто замечательно!

-- Пн июл 01, 2013 22:21:02 --

Попробуйте все внимательнее прочитать эту фразу из сообщения Jarek:

Цитата:

Moreover, for larger N this bound must be achieved since the number of permutations of the N*N primes is so large that it is virtually certain that many of them lead to pandiagonal magic sqaures.

-- Пн июл 01, 2013 22:38:02 --

Статью Stefano Tognon нашла и выложила на Яндекс-Диск (формат doc)
http://yadi.sk/d/ez_i_jVN6OGxQ

Это как раз тот вариант статьи, который был представлен на конференцию.

Я не вникала в эту статью (по незнанию языка) и вообще в описание алгоритма. Знаю только одно: Stefano тоже на первом этапе использует случайную генерацию.
Вполне возможно, что у него алгоритм реализован намного эффективнее, нежели у меня.
Смотрите сами, оцените сами.

[Nataly-Mak]

Вот этот магический квадрат 15-го порядка (не пандиагональный) из последовательных простых чисел я тоже нашла по данному алгоритму (A073520):

131 167 229 461 541 617 733 911 967 1091 1259 1279 1319 1471 1493 
547 907 1583 1613 149 1423 193 1601 941 137 233 389 1039 1283 631 
1019 181 751 163 1453 1301 1297 1277 271 1619 1327 691 277 281 761 
1307 719 359 919 1063 653 1237 269 1433 863 1439 313 191 1021 883 
503 1367 433 1013 829 1153 317 347 1109 491 1249 677 1451 1489 241 
421 311 1487 439 1049 1409 1123 463 409 983 449 1031 1163 373 1559 
1399 1193 419 1531 971 647 977 1051 709 479 1229 379 353 1093 239 
599 953 1213 587 499 727 1321 787 307 1151 157 1571 1033 773 991 
211 1291 1499 577 1087 349 947 467 739 613 1171 1609 173 839 1097 
563 139 1373 1459 1289 443 619 1201 1427 809 881 1303 331 263 569 
607 1607 1511 673 1181 1481 1217 523 661 857 223 743 197 431 757 
853 643 701 179 1483 571 769 859 1447 659 929 997 1223 1129 227 
1549 887 257 557 367 1061 601 337 1361 937 1231 811 1543 293 877 
1579 1187 397 1069 509 683 797 1567 401 383 641 283 823 827 1523 
1381 1117 457 1429 199 151 521 1009 487 1597 251 593 1553 1103 821

Это было не сложно и не очень долго.