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

[Pavlovsky]

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

Solution #2 (that is, the solution beginning with the row “3 37 151 113 67 79”) was submitted by Valery Pavlovsky.

Мамой клянусь, что ничего я не находил! Где то взял, где надо посмотреть.

[Nataly-Mak]

Это решение было выложено только в одном месте, я уже показала этот пост Сергея.

Верю вам без клятв

[Nataly-Mak]

Пятое оригинальное решение для N=6 (svb напомнил):

svb в сообщении #733564 писал(а):

Еще один квадрат с суммой 450:

 181 113   5  31  53  67
  47  71 167 131  11  23
  43  41   7  89  97 173
  59  73 127  29  61 101
 103 139 107  19  79   3
  17  13  37 151 149  83

[Xaositect]

(Оффтоп)

Jarek в сообщении #756558 писал(а):

there should be a star here to denote arbitrary continuation of the file name, but I do not want to get a warning form a moderator for putting a star outside the TeX mode and TeX used in this forum doesn't like a star either

Don't worry, TeX is mandatory only for formulae, it is acceptable to use stars for other purposes.

[Pavlovsky]

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

[Jarek]

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

Did you use any tricks for N=7?

Now I did Thank you for your question which gave me motivation for another try

I have used one-fault solutions to collect some appropriate mod 3 solutions and used them as a starting point to perform a faster search, where terms are being changed by a multiple of 3 only. Got 761 - can be seen on the bottom of the final report page.

I do not believe 761 is optimal. Firstly, all 699 one-fault solutions for 761 I had in file were distinct - moreover they had distinct sets of terms. That means that for 761 the search space is almost infinite compared to what I was able to cover. Secondly, finding 761 was too easy as for the optimal solution.

[Nataly-Mak]

Jarek в сообщении #756807 писал(а):

Got 761 - can be seen on the bottom of the final report page.

Есть $S=761$!

(3,31,97,179,167,211,73), 
(47,89,19,173,79,227,127), 
(109,281,241,23,11,29,67), 
(163,17,113,7,193,71,197), 
(43,41,101,151,223,149,53), 
(157,103,59,191,83,61,107), 
(239,199,131,37,5,13,137)

Браво!

Я предчувствовала, что будет лучшее решение.
Пространство поиска сужается!

[dimkadimon]

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

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

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

Jarek в сообщении #756807 писал(а):

Got 761 - can be seen on the bottom of the final report page.

Excellent work! I think we can expect more improvements in this area. If you tell me which code to run then I can run it on some machines.

[Nataly-Mak]

Кто тут плакал, что не хватило времени, берите пример с Jarek
Если кому интересна задача, он решает её не только в рамках конкурса.

А я вчера перерыла весь диск, программу искала для построения пандиагонального квадрата 7-го порядка по общей формуле, не нашла
Помню хорошо, что я её писала, черновик даже остался. Наверное, программа пропала, когда сдох старый компьютер.
Но я сейчас собираюсь новую программу написать, формула-то, слава Богу, не пропала.

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

svb вчера в письме эту задачу подкинула.
В конкурсе не участвовал, пусть хоть после конкурса потрудится

[dimkadimon]

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

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

В этой задаче невозможно проверить какие то S. Если мы найдем S=733 тогда задача будет решена. Иначе мы точно не будем знать есть ли решение для какого то меньшего S. Тут нельзя выполнить полный перебор. Тут только можно случайно наткнуться на одно из решений или его никогда не найти.

[Nataly-Mak]

Массив простых чисел, из которых составлено последнее решение Jarek для N=7:

3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101  103  107  109  113  127  131  137  149  151  157  163  167  173  179  191  193  197  199  211  223  227  239  241  281

До числа 137 нет ни одного пропущенного числа. Очень плотный массив.

-- Пт авг 23, 2013 09:41:50 --

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

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

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

В этой задаче невозможно проверить какие то S. Если мы найдем S=733 тогда задача будет решена. Иначе мы точно не будем знать есть ли решение для какого то меньшего S. Тут нельзя выполнить полный перебор. Тут только можно случайно наткнуться на одно из решений или его никогда не найти.

Не поняла. Что значит - нельзя проверить?
Вы не в курсе, как мы проверяли минимальность пандиагонального квадрата 6-го порядка из чисел Смита? Так почитайте тему "Магические квадраты". На эту проверку ушли многие месяцы и усилия 4-х человек.

И далее, что значит: "если найдём S=733"? Это как мы его найдём? Случайно?
Я что-то не совсем понимаю, что значит - "случайно наткнуться". Это что за алгоритм такой?
Мы с коллегами именно выполняли проверку всех потенциальных констант, а не случайно натыкались на какую-то константу.

Например, при поиске наименьшего пандиагонального квадрата 7-го порядка из различных простых чисел (и не только 7-го порядка, а всех порядков!) я действовала так: сформировала массив из 49 простых чисел с минимально возможной магической константой $S=733$ и далее по алгоритму искала квадрат с такой магической константой. Никаких "случайных натыканий" не было.

Более того, я могу привести вам ещё один очень хороший пример.
Когда я искала наименьший МК 7-го порядка из чисел Смита, нашла решение с одной магической константой, но она была не минимальная, а следующая за минимальной. Решение с самой минимальной константой у меня никак не находилось по моему алгоритму. Тогда форумчанин 12d3 доказал теоретически (без всяких полных переборов!), что решения с такой магической константой не существует. Так-то! Существует не только такой метод доказательства --- полный перебор. Существуют ещё и математические методы.
Читайте тему "Магические квадраты"

Если в нашей текущей задаче удастся найти решение $S=735$, думаю, можно будет доказать его минимальность или существование и следующего решения $S=733$.

[dimkadimon]

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

Не поняла. Что значит - нельзя проверить?
Вы не в курсе, как мы проверяли минимальность пандиагонального квадрата 6-го порядка из чисел Смита? Так почитайте тему "Магические квадраты". На эту проверку ушли многие месяцы и усилия 4-х человек.

Я не знаю как проверить для N=7. Для N=6 гораздо меньше вариантов и можно проверить полным перебором. Кроме перебора я не знаю как проверить в этой задаче.

[Nataly-Mak]

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

Я не знаю как проверить для N=7. Для N=6 гораздо меньше вариантов и можно проверить полным перебором. Кроме перебора я не знаю как проверить в этой задаче.

Угу, для N=6 меньше вариантов. Я вам уже сказала, что на проверку всех потенциальных констант для пандиагонального квадрата 6-го порядка из чисел Смита потребовалось несколько месяцев (работали 4 человека). Вы возьмите и попробуйте сделать полный перебор для N=6. Скажете тогда, сколько часов потребовалось.

Американцы в прошлом веке решили построить все классические магические квадраты 5-го порядка. ЭВМ работала 100 часов. Потом несколько недель ушло на обработку результатов, ибо квадратов получилось порядка 25 млн. А для порядка 5 вариантов ещё меньше!

Никто не говорит о полном переборе. Надо искать эффективные алгоритмы поиска, надо подключать математику.

[Nataly-Mak]

Al Zimmermann тоже рад новому рекорду Jarek

Цитата:

I'm happy to see that Jarek isn't done yet. He's submitted an improved 7x7 solution with a magic constant of 761. Check it out at the bottom of the Final Report page (http://azspcs.net/Contest/PandiagonalMa ... inalReport).

I'm sure Natalia would like it if participants, starting with what are now the best known pandiagonal magic squares of primes, were to make additional improvements and then submit them. This wouldn't change the contest standings, but the improvements would continue to be recorded at the bottom of the Final Standings page.

Конечно, я очень хочу, чтобы были найдены новые улучшения

[Nataly-Mak]

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

Пока сырые эксперименты провела.

Вот это у меня массив простых чисел, из которых я собираюсь строить квадраты:

3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97  101 103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191 193  197  199  211 223  227 229  233  239  241 251 257 263 269 271 277  281

В массиве 59 чисел.
И вот один из экспериментов, пока сырой, как я уже сказала, и не доведён до конца. Если кому интересно, объясню подробно, что такое этапы поиска, которые здесь представлены.
Проверяется потенциальная магическая константа 759.

1 этап
0  0  0  19  0  0  3 
 0  5  0  0  0  0  0 
 7  0  11  0  0  0  0 
 0  29  0  0  0  0  0 
 23  277  31  17  127  271  13 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0
2 этап
0  0  0  19  37  0  3 
 0  5  0  109  0  0  0 
 7  0  11  263  0  0  0 
 0  29  0  41  0  0  0 
 23  277  31  17  127  271  13 
 0  0  0  53  0  0  281 
 0  0  0  257  0  269  0
3 этап
0  0  0  19  37  0  3 
 0  5  61  109  191  0  0 
 7  0  11  263  251  0  257 
 0  29  0  41  0  193  0 
 23  277  31  17  127  271  13 
 0  0  0  83  0  211  281 
 47  43  0  227  0  269  0
4 этап
0  0  43  19  37  0  3 
 0  5  101  109  197  199  0 
 7  0  11  257  241  0  193 
 0  29  0  41  0  229  0 
 23  277  31  17  127  271  13 
 0  191  0  167  0  97  281 
 53  47  0  149  0  269  0 

В последнем квадрате найдено 32 элемента, из них 22 свободных и 10 зависимых.
Здесь уже есть одна полная строка, один полный столбец и одна полная главная диагональ. Разломанные диагонали не вижу здесь, всё скачет, надо поместить квадрат в матрицу и посмотреть.
Все эти этапы выполнились мгновенно.
На следующем этапе программа уже задумалась, но я не ждала даже несколько минут, нет сейчас уже времени получше поэкспериментировать. Завтра продолжу.