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

[Nataly-Mak]

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

Example 3 (intermediate): I could imagine that one could start from a selected set of primes, which satisfy some weaker constrains than needed for Stanley Antimagic Squares. For example, I was able to find contest solutions for some even N starting with a set of primes composed of pairs with constant sums. Anyone who had entered known solution and would find those now, would earn 1.29 points. At some point those were record solutions, but later I improved them with a completely different approach to the problem.

А эту эвристику кто-нибудь пытался применить?
Это дало бы 1.29 балла к известным решениям (на данный момент это гарантированно второе место).
[хотя по сравнению с текущими результатами Jarek это уже, наверное, даст намного меньше]

Как я понимаю, здесь речь идёт о парах комплементарных простых чисел (пары с постоянной суммой).
Хорошая идея!

-- Пт июл 05, 2013 10:11:39 --

"Проверялку" получила



mertz
спасибо. Теперь буду проверять свои пандиагональные квадраты в вашей программе.
Если бы вы сделали программу так, чтобы она проверяла:
1. все ли числа простые;
2. нет ли повторяющихся чисел,
тогда можно было бы просить разрешения у AZ выложить "проверялку" для общего пользования.
Всё это, понятно, проверяет программа ввода решений на конкурс. Но иногда надо проверить квадрат "дома", до ввода его на конкурс.

Ну, и я уже не говорю о дальнейшей модификации программы, чтобы можно было поиграться с примитивными квадратами, изменяя содержимое ячеек Тем более что такая возможность (в Excel) уже предложена dmd.

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

[Nataly-Mak]

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

Я не спорю, что при построении такого примитивного квадрата (удовлетворяющего приведённым условиям) из простых чисел могут быть трудности; я же написала, что этот алгоритм не реализовала для простых чисел, а только для произвольных натуральных чисел.
. . . . . .
Сейчас у меня на столе среди кучи других задач лежит и эта задача. Просто стало интересно: какое решение даст этот алгоритм для N=8.

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

 11  17  31  101  283  277  263  193 
 41  47  61  131  313  307  293  223 
 191  197  211  281  463  457  443  373 
 857  863  877  947  1129  1123  1109  1039 
 587  593  607  677  859  853  839  769 
 557  563  577  647  829  823  809  739 
 0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0 

Нужные условия для тех элементов, которые уже найдены, выполняются (они заложены в программе).
Остались две строки - 16 элементов.
Не знаю, как долго программа будет искать полное решение. Не знаю также, квадрат с каким минимальным индексом будет найден. Вполне возможно, что это будет большой индекс, намного больше известного на начало конкурса решения (1584).
Но в существовании решения не сомневаюсь; и в применимости к полученному примитивному квадрату указанного выше преобразования Россера тоже не сомневаюсь.
Если преобразование сработало применительно к примитивному квадрату из произвольных натуральных чисел, почему оно не сработает для примитивного квадрата из простых чисел? Риторический вопрос

P.S. Все оставшиеся элементы в приведённом полузаполненном примитивном квадрате уже вычисляются (можно вручную квадрат достроить), но только они могут быть не простыми числами, могут возникнуть повторения чисел. Чтобы всё было, как надо, требуется дождаться решения от программы.

-- Пт июл 05, 2013 17:37:00 --

Pavlovsky
это ответ на ваш вопрос

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

Бегло посмотрел теорему 5.5. В теореме 5.5 описывается способ построения класссического квадрата из последовательных натуральных чисел. Как этот способ можно применить к построению квадрата из простых чисел?

[dmd]

Сразу видно, что достроить квадрат не удастся. В ячейке ниже 557 получается не простое число: 11+587-191=407.

Ни кто не сомневается в преобразованиях Россера. Примеры с не простыми числами не убедительны.

[Nataly-Mak]

Цитата:

P.S. Все оставшиеся элементы в приведённом полузаполненном примитивном квадрате уже вычисляются (можно вручную квадрат достроить), но только они могут быть не простыми числами, могут возникнуть повторения чисел. Чтобы всё было, как надо, требуется дождаться решения от программы.

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

-- Пт июл 05, 2013 18:04:27 --

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

Ни кто не сомневается в преобразованиях Россера. Примеры с не простыми числами не убедительны.

Не надо говорить за всех, пожалуйста.
Был вопрос Pavlovsky, я ответила на него. Если вам всё ясно, вы можете не читать мои посты.
Кроме того, в моих статьях море примеров с простыми числами (и ещё с числами Смита). Они, надеюсь, убедительны.

(Оффтоп)

Ах да, не даю вам алгоритмы, которые позволят найти решения хотя бы близкие к решениям лидера конкурса Увы, я сама не знаю таких алгоритмов.
Вы участник конкурса, вам и флаг в руки. Ищите эффективные алгоритмы. После конкурса всем расскажете ваши убедительные примеры.

Кстати, чтобы выявить закономерности в том или другом методе построения, я всегда начинала с классических квадратов (им соответствуют примитивные квадраты, называемые обратимыми); потом переходила к квадратам из произвольных натуральных чисел и только после этого строила квадраты из простых чисел, когда уже все закономерности были выявлены (между прочим, Россер в своей статье поступал так же: начинал с классических квадратов; например, Теорема 5.5 у него как раз для классических квадратов; но он, кажется, забыл, написать, что всё это прекрасно работает и для нетрадиционных квадратов, если у Pavlovsky возник такой вопрос). Так что, примеры из произвольных натуральных чисел как раз самые убедительные, они самые ценные для меня.
Ну, а у вас, может быть, всё иначе. Это вполне понятно: у каждого своя метода.

[dmd]

xls-файл для квадрата 8х8

[Nataly-Mak]

Турнирная таблица чуть-чуть ожила ниже первой строчки

Цитата:

15 2.97 James Buddenhagen Xico, Veracruz, Mexico 6 Jul 2013 03:36

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

[Nataly-Mak]

Головоломка в тему
http://www.primepuzzles.net/puzzles/puzz_695.htm

Здесь надо строить пандиагональные квадраты из простых чисел-близнецов.
Вообще-то я привела свой квадрат 4-го порядка в головоломке #689 Radko Nachev просто как попутный результат. Carlos Rivera выделил это в отдельную головоломку.

Это мой наименьший квадрат 4-го порядка из простых чисел-близнецов:

17 191 31 181
151 61 137 71
179 29 193 19
73 139 59 149

Квадрат составлен из следующих пар близнецов:

(17,19), (29,31), (59,61), (71,73), (137,139), (149,151), (179,181), (191,193)

Магическая константа квадрата равна 420.

Carlos спрашивает в головоломке, какие ещё подобные квадраты можно построить для порядков 5,6,...

Что касается нечётных порядков... как такие квадраты строить? Ведь если использовать пары близнецов, то количество всех чисел будет чётным. Как можно составить, например, квадрат порядка 5 из пар близнецов, если в квадрате должно быть 25 чисел? Значит, тогда одна пара будет неполной.

Сейчас сильно задумалась над вопросом: возможно ли построить пандиагональный квадрат 6-го порядка из простых близнецов?
Уже проверила более десятка потенциальных массивов из 36 чисел (18 пар близнецов), квадрат пока не найден.
Возможно ли построить такой квадрат теоретически
Известно, что в пандиагональном квадрате 6-го порядка все составляющие его числа должны образовывать либо пары комплементарных, либо пары псевдокомплементарных чисел (доказано svb).
Думаю над этой задачей. Приглашаю всех подумать

P.S. Кстати, пандиагональные квадраты 4-го порядка составляются только из пар комплементарных чисел. Как видим, для квадрата 4-го порядка 8 пар комплементарных чисел среди простых близнецов найдены. Вполне возможно, что найдутся и 18 пар комплементарных или псевдокомплементарных чисел для квадрата 6-го порядка. Надо искать.

Поясню для тех, кто незнаком с термином "пары комплементарных чисел".
Так называют пары чисел с одинаковой суммой. В приведённом здесь пандиагональном квадрате 4-го порядка имеем пары комплементарных чисел:
(17,193) (19,191) (31,179) ...
и т. д. всего 8 пар.

Сумма чисел в паре называется константой комплементарности совершенного магического квадрата (все пандиагональные квадраты 4-го порядка являются совершенными).
В данном примере константа комплементарности равна 210.

С парами псевдокомплементарных чисел сложнее. Понятие введено svb при разработке алгоритма построения нетрадиционных пандиагональных квадратов 6-го порядка. В определении участвует ещё понятие "отклонение от комплементарности". Подробно алгоритм svb описан в теме "Магические квадраты".

И ещё раз обращаю внимание на цитату из сообщения Jarek. Как я поняла, он строил квадраты из пар комплементарных чисел.

Цитата:

For example, I was able to find contest solutions for some even N starting with a set of primes composed of pairs with constant sums.

-- Сб июл 06, 2013 10:53:16 --

Мной построен пандиагональный квадрат 8-го порядка из различных простых чисел из пар комплементарных чисел (см. статью, рис. 37).

[Nataly-Mak]

Цитата:

1 15.00 Jarek Wroblewski Wroclaw, Poland 6 Jul 2013 07:35

Неужели никто не поднимет "перчатку"?

Такого абсолютного лидерства я не припомню за всю историю своего участия в конкурсах.

-- Сб июл 06, 2013 12:37:36 --

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

Вот этот полузаполненный примитивный квадрат нашёлся за несколько минут:

 11  17  31  101  283  277  263  193 
 41  47  61  131  313  307  293  223 
 191  197  211  281  463  457  443  373 
 857  863  877  947  1129  1123  1109  1039 
 587  593  607  677  859  853  839  769 
 557  563  577  647  829  823  809  739 
 0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0 

Просто из научного интереса занимаюсь с этой программой
Немного ужесточила требования, нашла такой квадрат:

11  31  239  349  1249  1229  1021  911 
 41  61  269  379  1279  1259  1051  941 
 83  103  311  421  1321  1301  1093  983 
 293  313  521  631  1531  1511  1303  1193 
 419  439  647  757  1657  1637  1429  1319 
 389  409  617  727  1627  1607  1399  1289 
 347  0  0  0  0  0  0  0 
 137  0  0  0  0  0  0  0 

Это тоже быстро, минут 20.
Остались не найдены 14 элементов. Точнее: они найдены, они уже вычисляются, но могут быть неправильными (не простыми числами, или повторяющими уже имеющиеся элементы).

[Nataly-Mak]

Есть ещё новый результат!

Цитата:

2 7.01 Wes Sampson La Jolla, California, United States 6 Jul 2013 08:32

Мировой разум начинает побеждать задачу.

[dmd]

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

Кому интересно - присоединяйтесь.

[Nataly-Mak]

Это что-то типа Приложения, какое делал mertz, например, к конкурсу "Monochromatic Squares". Классное Приложение! Не только "проверялка". Я с помощью этого Приложения нашла некоторые решения в ручном режиме, например, C6.
А картинки в этом Приложении рисовались великолепные
(см. книгу)

К сожалению, текущий конкурс не заинтересовал mertz, как я понимаю. И Приложения хорошего в его исполнении, видимо, не будет.
Я попросила его сделать "проверялку", он её сделал. Но это не более чем просто "проверялка", да и то не полная: она проверяет только пандиагональность квадрата, но не проверяет числа на простоту и на повторение.

[dmd]

Выглядеть это будет примерно вот так:

.

Пока это ещё черновая заготовка, почти ничего не работает. Если всё нормально пойдет, то можно будет добавить выбор порядка квадрата и тип преобразования. Если процедура Import работает в демонстрациях, то и загрузка квадрата из внешнего файла будет. Математика она кроме того, что CAS, она ещё и относительно простой конструктор интерфейсов для алго-математических задач. Примеры различных демонстраций можно посмотреть на их сайте. Надо просто попробовать, может и получится создать универсальную проверялку для квадратов. Пока никаких идей у меня нет по основной проблеме конкурса - займусь этим на досуге.

[Nataly-Mak]

dmd
идея очень хорошая. Дерзайте.

Я посмотрела картинку, мне нравится. Если это будет работать, отличное будет Приложение к конкурсу.

[Nataly-Mak]

И ещё улучшение у Jarek:

Цитата:

1 15.00 Jarek Wroblewski Wroclaw, Poland 6 Jul 2013 15:12
2 7.00 Wes Sampson La Jolla, California, United States 6 Jul 2013 08:32

У Wes результат уменьшился на 0.01. Разница ровно 8 баллов. Удастся ли Wes сократить разрыв и хоть чуть-чуть приблизиться к лидеру?

[Nataly-Mak]

Ни дня без улучшений!

Цитата:

1 15.00 Jarek Wroblewski Wroclaw, Poland 7 Jul 2013 06:10

Если так будет до конца конкурса, наверняка должны быть найдены минимальные решения.
Что скажете, коллеги?

Jarek сообщил на Yahoo, что его результат для N=7 меньше 800. Нижняя граница для N=7 равна 733. Уже совсем близко.

Но что очень важно: минимальность решения надо доказать. А это сделать не всегда просто. Если решение в точности совпадёт с нижней границей, понятно, что оно минимальное. Если же оно будет чуть больше нижней границы, тогда нужно ещё доказать, что оно минимальное.
Даже для N=6 доказать минимальность решения было непросто.