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

[Pavlovsky]

На Al Zimmermann's Programming Contest начался новый конкурс:
http://www.azspcs.net/Contest/PandiagonalMagicSquares

Автор задачи Наталия Макарова.

Необходимо составить пандиагональные (дьявольские) магические квадраты NxN из простых чисел. N равно от 6 до 20. Задача очень трудная. Уже для маленьких N перебор становится непосильным даже для кластеров.

Уже есть первые результаты!

1 11.48 Roy van Rijn Maassluis, Netherlands 21 Jun 2013 17:24 
2 5.00 Shyam Sunder Gupta New Delhi, India 21 Jun 2013 17:30 
3 1.72 Alexander Gettinger Apex, North Carolina, United States 21 Jun 2013 17:55 
4 1.00 Jim Gillogly Long Beach, California, United States 21 Jun 2013 16:39 
5 .48 Nick Gardner Portsmouth, England, United Kingdom 21 Jun 2013 15:52 

[Nataly-Mak]

Посмотрите на таблицу известных решений:

n Smallest Known Magic Constant
6      450
7      1597
8      1584
9      24237
10    3594
11    18191
12    8820
13    1394767
14   No known solution
15    18231
16    48048
17    5675102246930958811
18    54054
19    7769339597062329721
20    65100

Забавно магические константы "пляшут"
А для N=14 решение вообще мне неизвестно. Теоретически оно существует, найти его мне не удалось.

-- Пт июн 21, 2013 22:39:37 --

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

Уже есть первые результаты!

1 11.48 Roy van Rijn Maassluis, Netherlands 21 Jun 2013 17:24 
...

Да, результат 11,48 на старте - это очень хорошо.
Максимальный результат 15 баллов.

[Nataly-Mak]

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

Уже для маленьких N перебор становится непосильным даже для кластеров.

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

У двух конкурсантов уже есть 12 баллов. Быстро они управились
Ну, это ещё не значит, что найденные ими решения нельзя улучшить.
Интересно, кто первым найдёт неизвестное решение для N=14.

[Jarek]

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

У двух конкурсантов уже есть 12 баллов. Быстро они управились

For any N there is a lower bound for the magic sum, which can be found as follows:
Take the smallest sum of distinct primes which is divisible by N. The lower bound for the magic sum is 1/N-th of that sum.

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. This is theoretical minimum, but it may be hard or impossible to find.

It 2 people are tied at 12.00 then either they found a way to produce optimal solutions (and the contest is almost over) or their solutions come from applying the same algorithm or they come from the same source.

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

Интересно, кто первым найдёт неизвестное решение для N=14.

Note that also the known solutions for N=17 and N=19 are too large to obey 2^53 limitation, so for the contest purposes there are 12 known and 3 unknown solutions. Hence we should wait for a score over 12.00.

[Nataly-Mak]

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

It 2 people are tied at 12.00 then either they found a way to produce optimal solutions (and the contest is almost over) or their solutions come from applying the same algorithm or they come from the same source.

Найти оптимальные решения и доказать минимальность решения непросто.
Минимальность доказана только для N=6.
Решение для N=7 найдено мной очень давно, однако минимальность его мне доказать не удалось. Вполне возможно, что оно не минимальное.
Тем более всё сложно для N>7.
Не думаю, что эти участники нашли минимальные решения.

Можно ориентироваться на магические константы обычных (не пандиагональных) МК из простых чисел - A164843.

Цитата:

Note that also the known solutions for N=17 and N=19 are too large to obey 2^53 limitation, so for the contest purposes there are 12 known and 3 unknown solutions. Hence we should wait for a score over 12.00.

Да, это верно. Удастся ли уменьшить магические константы для N=17,19 так, чтобы не выходить за пределы 2^53? Это, конечно, вполне возможно.
Я знаю по опыту моих решений для N=11,13.

[Jarek]

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

Можно ориентироваться на магические константы обычных (не пандиагональных) МК из простых чисел - A164843.

Indeed, that is an excellent reference point!

I am pretty sure that those magic constants are identical with the optimal magic constants for pandiagonal magic squares of primes for large N - not extremely large N, I am convinced that N=10 is large enough. Since those constants are known to be optimal for non-pandiagonal squares, any pandiagonal solution matching them must be optimal as well.

So I am willing to assume for practical purposes that the values of minimal magic constants for the contest problem are KNOWN for N>=10 and are identical with those for non-pandiagonal squares.

The hard part is that the squares corresponding to those optimal values may be impossible to find.

[Nataly-Mak]

Из россиян самый смелый - Pavlovsky

Pavlovsky
Поздравляю с почином!
Ну, мы с вами на этой задаче собаку съели
Лучший на сегодня результат для N=10 - это ваш результат.
Я много пыталась его улучшить --- не получилось.

-- Сб июн 22, 2013 15:12:53 --

Решение для N=5 не входит в конкурсную задачу, можно показать

Это решение, найденное мной:

7 337 131 197 181
227 241 37 277 71
307 11 167 271 97
211 127 367 41 107
101 137 151 67 397
S=853

Это минимальное решение, найденное Pavlovsky:

5 73 127 137 53 
37 167 17 71 103 
83 101 13 67 131 
43 31 197 113 11 
227 23 41 7 97 
S=395

Вот так можно улучшить результат!

[Nataly-Mak]

В дискуссионной группе возник вопрос о ломаных (разломанных) диагоналях в определении пандиагонального квадрата.

Смотрите определение пандиагонального квадрата в английской Википедии в статье «Pandiagonal magic square»:

Цитата:

A pandiagonal magic square or panmagic square (also diabolic square, diabolical square or diabolical magic square) is a magic square with the additional property that the broken diagonals, i.e. the diagonals that wrap round at the edges of the square, also add up to the magic constant.

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

В магическом квадрате порядка $n$ имеется $2(n-1)$ разломанных диагоналей.

[Pavlovsky]

Как и предполагал, 12 баллов - это ввод известных на начало конкурса решений. То есть конкурс еще не начался. Авторских решений пока нет.

[Nataly-Mak]

Совершенно верно!
Я тоже при появлении первых 12 баллов так подумала, но немного сомневалась. Теперь сомнений не осталось.
Ну что же: первая интрига конкурса - все могут сейчас же получить 12 баллов
Достаточно найти в Интернете известные на сегодня решения.
Правилами конкурса ввод известных решений не запрещается.

[Pavlovsky]

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

Достаточно найти в Интернете известные на сегодня решения.

Я использовал решения из ваших статей. Но решений для N=11,13 с константами 18191,1394767 в них не нашел. Видать люди используют другие источники.

[Nataly-Mak]

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

Я использовал решения из ваших статей. Но решений для N=11,13 с константами 18191,1394767 в них не нашел. Видать люди используют другие источники.

И это верно: есть другие источники.
Более того, решения с константами 18191 и 1394767 находятся в другом источнике, нежели решения с константами, найденными мной (а мои решения тоже не только в моих статьях).

[Pavlovsky]

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

Более того, решения с константами 18191 и 1394767 находятся в другом источнике, нежели решения с константами, найденными мной (а мои решения тоже не только в моих статьях).

Я очень тонко намекал, чтобы вы дали ссылку на другие источники. Вы очень тонко намекнули, чтобы я искал ссылку сам.

[Nataly-Mak]

Я поняла ваш очень тонкий намёк
Боюсь давать ссылки, как бы не получить по маковке

В описании задачи я отправила AZ несколько ссылок, он не дал ни одной (на странице с описанием задачи). Строгий товарищ. Наверное, это хорошо, строгость всегда полезна

Скажу без ссылок, читайте:
темы "Магические квадраты", "Антимагические квадраты" на этом форуме;
фундаментальную статью Россера "Алгебраическая теория дьявольских квадратов";
статьи на моём сайте (ищите те статьи, которые по названию подходят к конкурсной задаче).

[Pavlovsky]

Хм. Ввел все решения из статей Наталии. Получил 12 баллов. Значит источник с решениями с константами 18191,1394767 для N=11,13 еще никто не нашел.

-- Вс июн 23, 2013 00:44:06 --

Одного месяца на решение 15-ти задач, для меня слишком мало. Пожалуй займусь поиском рекорда для N=11,13.