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

[Nataly-Mak]

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

Нет не сложно, но я не знаю алгоритм.

Алгоритм в статье Россера.

Цитата:

В ваших статьях нет алгоритма, есть только примеры для некоторых N, но не для всех.

Я чего-то недоработала?
Ну, для всех N я и не нашла решения, например, для N=14,17,19. Поэтому для этих N в моих статьях и примеров нет.

Цитата:

Где найти алгоритм преобразования Россера для всех N?

Приходится повториться: в статье Россера.
К тому же, преобразование Россера, превращающее примитивный квадрат в пандиагональный квадрат, работает не для всех N.
Читайте статью Россера!
Читайте цикл моих статей "Нетрадиционные пандиагональные квадраты". Обратите внимание, что каждому порядку квадрата (N) у меня посвящена отдельная статья.
Магические квадраты --- они такие, их нельзя строить по одному общему алгоритму.
Например, для N=6 svb разработал совершенно уникальный алгоритм, которого нет даже в статье Россера.
Я разработала свои алгоритмы для N=8,11,13. В алгоритме для N=8 за основу взят алгоритм svb; в алгоритмах для N=11,13 базовая часть - алгоритм Россера.

[dimkadimon]

Угадал алгоритм преобразования Россера.

[Nataly-Mak]

Поздравляю!

[Nataly-Mak]

Полку россиян прибыло

Цитата:

14 2.00 Dmitry Ezhov Sterlitamak, Russia 24 Jun 2013 07:02

Пока трое... это очень мало. Надеюсь, кто-нибудь ещё подключится.

(Оффтоп)

Некоторые уже прислали ответ с отказом участвовать, а кое-кто пока не ответил на моё приглашение. Лето - время отпусков. Кто-то загорает на море, кто-то путешествует в горах...

[Nataly-Mak]

Отмечу ещё раз, что нижние границы для решений известны - это магические константы обычных (не пандиагональных) МК из простых чисел, смотрите последовательность A164843 в OEIS.
Приведу эти константы для квадратов конкурсной задачи:

n=6 S=432
n=7 S=733
n=8 S=1154
n=9 S=1731
n=10 S=2470
n=11 S=3417
n=12 S=4584
n=13 S=6013
n=14 S=7712
n=15 S=9731
n=16 S=12088
n=17 S=14807
n=18 S=17940
n=19 S=21501
n=20 S=25530

Сравните с известными на сегодня магическими константами пандиагональных квадратов.
Есть куда улучшать!
Неулучшаемо только решение для n=6, магическая константа для пандиагонального квадрата 6-го порядка из (различных) простых чисел S=450 минимальная.

Ещё такой интересный момент: для всех n от 6 до 20 последовательность магических констант не пандиагональных МК из простых чисел возрастающая.
Будет ли это выполняться для магических констант пандиагональных квадратов? В известных на сегодня решениях это не выполняется.

[Nataly-Mak]

Цитата:

6 9.91 Dmitry Kamenetsky Adelaide, Australia 24 Jun 2013 03:13
7 9.89 Dmitry Ezhov Sterlitamak, Russia 24 Jun 2013 14:06
8 9.37 Richard Zapor Los Angeles, California, United States 22 Jun 2013 00:14

Интересная градация.

-- Пн июн 24, 2013 19:42:55 --

Dmitry Ezhov уже ликвидировал "недостачу" в баллах
Такой клуб образовался:

Цитата:

2 9.91 Valery Pavlovsky Ekaterinburg, Russia 22 Jun 2013 20:28
3 9.91 Wes Sampson La Jolla, California, United States 23 Jun 2013 04:52
4 9.91 Roy van Rijn Maassluis, Netherlands 23 Jun 2013 08:53
5 9.91 Aicke Hinrichs Jena, Germany 23 Jun 2013 12:18
6 9.91 Dmitry Kamenetsky Adelaide, Australia 24 Jun 2013 03:13
7 9.91 Dmitry Ezhov Sterlitamak, Russia 24 Jun 2013 15:32

Как я понимаю, джентльмены этого клуба нашли все известные на сегодня решения, приведённые в конкурсной таблице.
Теперь можно начинать искать собственные решения

(Оффтоп)

Не знаю, как кому, а мне очень интересно наблюдать за конкурсом.
Немножко завидую лидеру
Мне такие решения (N=14,17,19) найти не удалось.

[Nataly-Mak]

Цитата:

2 9.12 Dmitry Kamenetsky Adelaide, Australia 25 Jun 2013 04:19

dimkadimon
поздравляю с первым авторским решением и выходом на второе место. Это хорошее начало.
Для какого N нашли своё решение?

Jarek
а вас поздравляю с новым значительным улучшением. Вижу, что счёт 9.91 превратился в 9.09. Значит, вы нашли очень хорошее улучшение; может быть, и не одно.

Интрига №3: будут ли серьёзные конкуренты лидеру?
Сейчас отрыв лидера от близких к нему конкурсантов составляет почти 6 баллов.
Другими словами: появятся ли новые 15 баллов?

[dimkadimon]

Большое спасибо! Наконец какой то прогрес. Я нашёл N=13.

[Nataly-Mak]

Отлично! Так держать.

N=13 хорошо поддаётся улучшениям.
Мой результат был улучшен J. K. Andersen ещё до конкурса. И вот найдено новое улучшение.

[Nataly-Mak]

Представлю один из алгоритмов Россера, чтобы помочь быстрее освоиться с алгоритмами.
Данный алгоритм применяется для построения пандиагональных квадратов порядка N, являющегося составным числом. Алгоритм работает как для классических, так и для нетрадиционных пандиагональных квадратов.

Если N чётное число, пандиагональный квадрат порядка N с магической константой S можно построить из четырёх пандиагональных квадратов порядка N/2 (с одинаковой магической константой, равной S/2) по так называемым решёткам Россера.

Покажу пример для N=8 (это минимальный порядок, для которого работает данный алгоритм). В примере показан классический пандиагональный квадрат 8-го порядка, построенный из четырёх пандиагональных квадратов 4-го порядка. Решётки выделены цветом. В каждой решётке находится пандиагональный квадрат 4-го порядка с магической константой 130.



Например, квадрат из первой решётки:

24 57 48 1
43 6 19 62
17 64 41 8
46 3 22 59

Если N нечётное составное число, например, кратное 3 (N>9), тогда строим квадрат порядка N из девяти пандиагональных квадратов порядка N/3. Решёток в этом случае будет девять. Пример для N=15 можно найти в моих статьях.

Замечание: в любой решётке может быть размещён любой изоморфный вариант пандиагонального квадрата 4-го порядка. Например, в первой решётке можно разместить такой вариант:

1 62 8 59
48 19 41 22
57 6 64 3
24 43 17 46

Также можно переставить квадраты 4-го порядка в решётках любым способом.

[Pavlovsky]

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

N=13 хорошо поддаётся улучшениям.

21    .01   Alex Chernov   Penza, Russia

А ведь был 1 балл.

Я так понимаю, известный результат для N=13 улучшен 100 раз!

[Jarek]

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

Я так понимаю, известный результат для N=13 улучшен 100 раз!

Not quite, it is improved by a factor below 70.

[Nataly-Mak]

По-моему, в этом конкурсе совершенно невозможно вычислить текущие рекорды, даже примерно. А в конкурсе "Factorials", например, это делали легко.
Придётся ориентироваться на нижние границы для решений, которые приведены выше.
Кстати, нижняя граница для N=13 равна 6013. Результат на начало конкурса был 1394767.
Хорошие "ножницы" Улучшайте на здоровье!
Окончательное решение Sopt>=6013.

[Pavlovsky]

Интересно, будут ли по результатам конкурса, подвижки в решении проблемы века. О соотношении классов регулярных (по Россеру) и нерегулярных пандиагональных квадратов. Есть большое подозрение, что все авторские решения тройки лидеров являются регулярными квадратами.

-- Вт июн 25, 2013 21:50:33 --

post348692.html#p348692
А блин, не обеднею. Объявляю приз, решившему задачу, вышлю на веб-кошелек 500 (Пятьсот) рублей.
Точно формулирую задачу:

Найти пандиагональный МК 7х7 из различных простых чисел с магической константой C и доказать, что не существует регулярного (по Россеру) пандиагонального МК 7х7 из различных простых чисел с константой равной или меньшей C. Или доказать, что это невозможно.

[Nataly-Mak]

Pavlovsky
сообщении #729858]здесь я привела решение вашей задачи для идеального квадрата 7-го порядка.
Вы это читали?
Но идеальный квадрат является пандиагональным!
Ваша задача решена?

Если верить J. K. Andersen, примитивный квадрат 11-го порядка имеет минимальный индекс 18191.
Если будет найден пандиагональный квадрат 11-го порядка с меньшей магической константой, ваша задача будет решена и для N=11.

Вообще, я уже уверена, что можно формулировать теорему:
минимальные регулярные пандиагональные квадраты (из различных простых чисел) по Россеру не являются минимальными среди всех пандиагональных квадратов (регулярных и нерегулярных).

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

-- Вт июн 25, 2013 21:40:11 --

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

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

Я так понимаю, известный результат для N=13 улучшен 100 раз!

Not quite, it is improved by a factor below 70.

Ага...
Предположим, что известный результат улучшен в 65 раз. Значит, примерный текущий рекорд 21459.