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

[mertz]

I did have solutions for 733.

Three solutions with 3 holes.

f[{
{3,43,37,137,151,163,199},
{337,97,53,61,101,71,13},
{173,23,277,223,5,3,29},
{21,11,17,109,193,149,233},
{73,139,103,41,89,107,181},
{59,179,239,79,3,127,47},
{67,241,7,83,191,113,31}
}]

f[{
{3,79,151,251,193,19,37},
{137,97,5,67,31,257,139},
{193,211,47,223,41,7,11},
{3,131,101,13,173,199,113},
{181,17,139,73,163,53,107},
{59,89,229,83,103,127,43},
{157,109,61,23,29,71,283}
}]

f[{
{3,271,73,41,151,1,193},
{89,67,109,211,17,101,139},
{181,131,53,37,5,313,13},
{21,11,179,199,127,29,167},
{97,173,157,7,205,23,71},
{283,19,83,47,31,163,107},
{59,61,79,191,197,103,43}
}]

[Nataly-Mak]

mertz в сообщении #759430 писал(а):

I did have solutions for 733.

Three solutions with 3 holes.

О, это очень хорошо.
А по какой программе вы нашли эти решения?

[mertz]

Jareks program. I did not set up 3 hole solutions to go to the display. I am running now to find a 2 hole. I have dozens of three hole solutions now.

[mertz]

2 hole solutions for 733

f[{
{3,13,17,193,277,157,73},
{191,79,227,37,7,83,109},
{139,61,151,11,59,163,149},
{21,131,53,283,113,31,101},
{29,179,67,97,43,181,137},
{223,41,19,107,211,71,61},
{127,229,199,5,23,47,103}
}]

f[{
{3,67,131,139,31,283,79},
{11,211,97,109,89,103,113},
{127,193,19,101,179,43,71},
{151,17,149,107,67,61,181},
{199,59,7,73,307,5,83},
{13,29,277,163,37,47,167},
{229,157,53,41,23,191,39}
}]

[Nataly-Mak]

mertz в сообщении #759444 писал(а):

2 hole solutions for 733

mertz
Отлично!
А вы можете выложить программу, которая ищет решение $S=733$
Та версия, которую вы выложили, ищет только решения для $S\geqslant 737$.

Я уже писала выше, что надо начать решать задачу именно с магической константы 733. Попытаться найти решение или доказать, что его не существует.
Не стоит тратить силы и время на поиск решений с бОльшими магическими константами.
Если удастся доказать невозможность построить пандиагональный квадрат с магической константой 733, тогда можно переходить к следующей потенциальной константе - 735. Понимаю, что возможен и такой вариант: ни построить решение $S=733$, ни доказать его несуществование никак не получится пока, на данном этапе исследований (не хватит данных, знаний, опыта, вычислительных ресурсов и т.д.). Тогда, конечно, можно пробовать поиск решения $S=735$ и/или решений с бОльшими константами.

Вчера выполнила до конца поиск всех шаблонов из вычетов по модулю 6, их нашлось всего 120. Я почему-то думала, что будет гораздо больше. Такое количество шаблонов вполне реально обработать на предмет поиска наборов из 4-х ортогональных покрытий, как мне кажется (whitefox уже опубликовал вчера типы возможных покрытий).
Если такого набора не найдётся ни одного, тем самым будет доказано несуществование решения. Если же такие наборы будут найдены, останется выполнить этап проверки этих наборов на предмет построения пандиагонального квадрата.

-- Вс сен 01, 2013 07:16:51 --

mertz
вы можете управлять массивом простых чисел, который используется в программе Jarek

При поиске решения $S=733$ надо использовать такой массив простых чисел:

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

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

[Nataly-Mak]

Моя программа тоже трудится неплохо
удалось найти решение с 4 дырками:



Конечно, уже есть решения mertz с 2 дырками; но для моей программы и 4 дырки - прогресс.
Ставлю ей "удовлетворительно"

Борцы с дырками упорно отмалчиваются.
Jarek написал, что теоретически борьба с дырками возможна, но у него были обескураживающие тесты. Но хоть какие-то тесты были! У нас же нет никаких
Уже есть несколько решений $S=733$ с разным количеством ошибок - от 8 до 2. Поработать с этими решениями никто не желает.

[mertz]

S=733. 4 hours. 381 three hole. 2 two hole.
S=735. 30 minutes. 0 three hole. 0 two hole.

Jarek's "primes" are not primes. It is a list of numbers that I can not explain. I do not understand any of the work you are doing. I am just taking his program and playing with it.

[Nataly-Mak]

mertz в сообщении #759444 писал(а):

2 hole solutions for 733

f[{
{3,13,17,193,277,157,73},
{191,79,227,37,7,83,109},
{139,61,151,11,59,163,149},
{21,131,53,283,113,31,101},
{29,179,67,97,43,181,137},
{223,41,19,107,211,71,61},
{127,229,199,5,23,47,103}

Представила это решение в виде шаблона из вычетов по модулю 6:

3 1 5 1 1 1 1
5 1 5 1 1 5 1
1 1* 1 5 5 1 5
3* 5 5 1 5 1 5
5 5 1 1 1 1 5
1 5 1 5 1 5 1
1 1 1 5 5 5 1

Звёздочками помечены две дырки. Дырка, соответствующая не простому числу 21, несколько нарушила гармонию цепочек; столбец, содержащий это число, имеет недопустимый вид. Да и вообще вычет 3 в шаблоне должен быть всего один. Повторенное простое число 61 гармонии цепочек не нарушило.
Далее, в решении присутствует число 283, которого в решении с магической константой 733 быть не может.

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

[Nataly-Mak]

Нашла ещё решение с 5 дырками для магической константы 733:

5  131*  59  131  163  241  3 
 229  211  19  61  23  53  137 
 13  83*  109  199  179  139  11 
 193  41  65*  191  -5*  67  181 
 101  79  127  73  97  89  167 
 43  31  227  71  173  37  151 
 149  157  127*  7  103  107  83 

Дырки отмечены звёздочками. Три простых числа повторяются 83, 127 и 131.

Мои эксперименты показывают, что решения с дырками находятся из Массива №2:

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 227 229 239

Этот массив отличается от Массива №1 всего парой чисел: здесь - (227,229), в Массиве №1 - (223,233).
Обратите внимание, что и в решениях mertz с 2 дырками (см. выше) нет чисел Массива №1 - 223 и 233, а есть числа Массива №2 - 227 и 229.
Конечно, выводы делать рано, слишком мало данных для анализа, это может быть просто случайность. Однако, сколько ни кручу программу для Массива №1, решений нет вообще никаких.
Когда только начинала работать по этой программе, ввела сначала Массив №1, получила вот этот полуфабрикат с 35 найденными элементами (14 дырок):

199  0  41  223  5  0  3 
0  61  23  151  233  149  0 
239  0  47  11  173  0  211 
0  101  0  109  0  43  0 
71  37  163  83  59  181  139 
7  107  0  67  0  127  191 
29  179  0  89  0  167  131 

И больше, сколько помню, не нашла ни одного решения из чисел этого массива.

Следует отметить, что анализ чисел массива по модулю 6, выполненный whitefox, будет одинаков для обоих массивов, так как пары чисел (223, 233) и (227,229) дают одну и ту же пару вычетов по модулю 6 - 1,5.
Так что, с вычетами можно работать независимо от массива (первый или второй), но вот строить квадрат всё же предпочтительнее пока (до появления новых данных) из чисел Массива №2.

[Nataly-Mak]

whitefox в сообщении #759000 писал(а):

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

1 1 1 1 1 1 1
1 1 1 1 1 3 5
1 1 1 1 5 5 5
1 1 3 5 5 5 5
1 5 5 5 5 5 5

Первые пять шаблонов позволят разделить, найденную Nataly-Mak, базу данных из 393714 разбиений (393510 для Массива №2) на пять подбаз.

Эти цепочки мне очень нравятся. Надо поработать в этом направлении.
Сейчас решила посмотреть, много ли будет цепочек вида (1 1 1 1 1 1 1).
Работаю с Массивом №2:

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 227 229 239

Программа нахождения всех цепочек такого вида выполнилась за долю секунды, цепочек найдено всего 3754.
Вот несколько первых цепочек:

(Оффтоп)

7  13  19  61  193  211  229 
 7  13  19  73  181  211  229 
 7  13  19  73  193  199  229 
 7  13  19  97  157  211  229 
 7  13  19  103  151  211  229 
 7  13  19  103  163  199  229 
 7  13  19  103  181  199  211 
 7  13  19  109  157  199  229 
 7  13  19  109  163  193  229 
 7  13  19  109  181  193  211 
 7  13  19  127  139  199  229 
 7  13  19  127  157  181  229 
 7  13  19  127  157  199  211 
 7  13  19  127  163  193  211 
 7  13  19  139  151  193  211 
 7  13  19  139  163  181  211 
 7  13  19  139  163  193  199 
 7  13  19  151  163  181  199 
 7  13  19  157  163  181  193 
 7  13  31  43  199  211  229 
 7  13  31  61  181  211  229 
 7  13  31  61  193  199  229 
 7  13  31  73  181  199  229 
 7  13  31  79  163  211  229 
 7  13  31  79  181  193  229 
 7  13  31  79  193  199  211 
 7  13  31  97  157  199  229 
 7  13  31  97  163  193  229 
 7  13  31  97  181  193  211

Точно так же можно найти цепочки остальных 4 видов.
Получив БД из цепочек 5 видов, переходим ко второму этапу - поиску наборов из 4-х ортогональных покрытий. whitefox уже установил, какого вида могут быть покрытия.

Цепочек вида (1 1 1 1 5 5 5) получилось много - 281234.
Несколько первых цепочек такого вида:

(Оффтоп)

 5  7  11  31  211  229  239 
 5  7  11  43  199  229  239 
 5  7  11  43  211  227  229 
 5  7  11  61  181  229  239 
 5  7  11  61  193  227  229 
 5  7  11  61  199  211  239 
 5  7  11  67  193  211  239 
 5  7  11  71  199  211  229 
 5  7  11  73  181  227  229 
 5  7  11  73  197  211  229 
 5  7  11  73  199  211  227 
 5  7  11  79  163  229  239 
 5  7  11  79  181  211  239 
 5  7  11  79  191  211  229 
 5  7  11  79  193  199  239 
 5  7  11  79  193  211  227 
 5  7  11  89  181  211  229 
 5  7  11  89  193  199  229 
 5  7  11  97  157  227  229 
 5  7  11  97  163  211  239 
 5  7  11  97  173  211  229 
 5  7  11  97  181  193  239 
 5  7  11  97  191  193  229 

Да, я-то думала, что цепочек будет мало, ошиблась
Будет точно 5 подмножеств (подбаз), которые дадут вместе всю БД цепочек для данного массива чисел.

[Pavlovsky]

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

Очевидно, что эта БД будет намного меньше БД, составленной из всех цепочек.

Это утверждение весьма не очевидно. Полагаю БД сильно не уменьшится.

[Nataly-Mak]

Pavlovsky
вы, как всегда, опоздали: я уже исправилась.
БД вообще не уменьшится, она просто разделится на 5 подмножеств.
Два подмножества я уже нашла, осталось найти ещё три.

-- Пн сен 02, 2013 08:36:31 --

Цепочек вида (1 5 5 5 5 5 5) получилось 57683.
Несколько первых:

(Оффтоп)

 5  7  11  47  197  227  239 
 5  7  11  53  191  227  239 
 5  7  11  71  173  227  239 
 5  7  11  83  191  197  239 
 5  7  11  101  173  197  239 
 5  7  11  101  179  191  239 
 5  7  11  107  137  227  239 
 5  7  11  107  167  197  239 
 5  7  11  107  173  191  239 
 5  7  11  107  179  197  227 
 5  7  11  113  131  227  239 
 5  7  11  113  167  191  239 
 5  7  11  113  173  197  227 
 5  7  11  113  179  191  227 
 5  7  11  131  149  191  239 
 5  7  11  131  167  173  239 
 5  7  11  131  173  179  227 
 5  7  11  137  149  197  227 
 5  7  11  137  167  179  227 
 5  7  11  149  173  191  197 
 5  7  11  167  173  179  191

-- Пн сен 02, 2013 08:45:18 --

Цепочек вида (1 1 1 1 1 3 5) получилось 11141.
Несколько первых:

3  5  7  79  199  211  229 
 3  5  7  97  181  211  229 
 3  5  7  97  193  199  229 
 3  5  7  109  181  199  229 
 3  5  7  127  151  211  229 
 3  5  7  127  163  199  229 
 3  5  7  127  181  199  211 
 3  5  7  139  151  199  229 
 3  5  7  139  157  193  229 
 3  5  7  151  157  181  229 
 3  5  7  151  157  199  211 
 3  5  7  151  163  193  211

-- Пн сен 02, 2013 08:53:01 --

И последнее подмножество - цепочки вида (1 1 3 5 5 5 5) состоит из 39698 цепочек.
Несколько первых:

(Оффтоп)

3  5  7  23  227  229  239 
 3  5  7  41  211  227  239 
 3  5  7  53  197  229  239 
 3  5  7  53  199  227  239 
 3  5  7  59  191  229  239 
 3  5  7  59  193  227  239 
 3  5  7  61  191  227  239 
 3  5  7  71  179  229  239 
 3  5  7  71  181  227  239 
 3  5  7  71  191  227  229 
 3  5  7  71  197  211  239 
 3  5  7  73  179  227  239 
 3  5  7  79  173  227  239 
 3  5  7  83  167  229  239 
 3  5  7  83  179  227  229 
 3  5  7  83  197  199  239 
 3  5  7  83  197  211  227 
 3  5  7  89  163  227  239 
 3  5  7  89  173  227  229 
 3  5  7  89  179  211  239 
 3  5  7  89  191  199  239 
 3  5  7  89  191  211  227 
 3  5  7  89  193  197  239

Все пять подмножеств дают 393510 цепочек (что и было мной получено раньше для всей БД).

Могу выложить эти пять подмножеств цепочек.

[Pavlovsky]

whitefox
Поделитесь пожалуйста превдарительными результатами своих исследований. Насколько вероятно найти решение 733 для N=7, за реальное время?
Я пока так и не решился реализовавывать свои идеи. Жду идею, такую, что руки сами бы потянулись к клавиатуре.

-- Пн сен 02, 2013 10:15:04 --

Пока своих супер идей нет, гоняю программу mertz для магической суммы 737. Программа работает вторые сутки. Найдено 19 решений с одной дыркой.

[Nataly-Mak]

Pavlovsky
whitefox уже поделился результатами исследований:

whitefox в сообщении #759420 писал(а):

whitefox в сообщении #759226 писал(а):

Nataly-Mak
В найденном вами шаблоне оба покрытия одной пары соответствуют шаблону 0 1 4 0 2, а оба покрытия другой пары -- шаблону 0 0 5 1 1.

Попробую найти все возможные сочетания для шаблонов покрытий.

Возможны только следующие сочетания шаблонов покрытий:
((0 1 4 0 2, 0 1 4 0 2), (0 0 5 1 1, 0 0 5 1 1))
((0 1 4 0 2, 0 0 5 1 1), (0 1 4 0 2, 0 0 5 1 1)).

Пять подбаз я сделала. Шаблоны для покрытий имеются.
Чего-то не хватает? Руки не тянутся к клавиатуре?

Так вам нужны 5 подбаз или нет? Чтобы не разбивать заново, можно воспользоваться готовым разбиением.
Попробуйте теперь найти хотя бы один набор из 4-х ортогональных покрытий.

-- Пн сен 02, 2013 09:49:40 --

Выкладываю архив
http://yadi.sk/d/yZywDoNJ8_qTU

В архиве 5 подбаз (файлы A21.txt, A22.txt,...,A25.txt) и все 120 шаблонов из вычетов по модулю 6 (файл Shablony733.txt).
Как я уже отметила, шаблоны годятся для обоих массивов; БД составлена для Массива №2.

whitefox
вся надежда на вас
Я пока не писала программу для создания покрытий, а надо бы.

[Nataly-Mak]

Сделала 5 подбаз и для Массива №1.
Пока не выкладываю, не востребовано

Цепочки вида (1 1 1 1 1 1 1) - 3805 шт.
(1 5 5 5 5 5 5) - 57449 шт.
(1 1 1 1 5 5 5) - 281598 шт.
(1 1 1 1 1 3 5) - 11157 шт.
(1 1 3 5 5 5 5) - 39705 шт

Всего: 393714 шт.

-- Пн сен 02, 2013 11:13:42 --

Подбираюсь к покрытиям.

Цитата:

Возможны только следующие сочетания шаблонов покрытий:
((0 1 4 0 2, 0 1 4 0 2), (0 0 5 1 1, 0 0 5 1 1))
((0 1 4 0 2, 0 0 5 1 1), (0 1 4 0 2, 0 0 5 1 1)).

Ещё раз для ясности обозначу цепочки.

Вид 1 - (1 1 1 1 1 1 1) с суммой 7
Вид 2 - (1 1 1 1 1 3 5) с суммой 13
Вид 3 - (1 1 1 1 5 5 5) с суммой 19
Вид 4 - (1 1 3 5 5 5 5) с суммой 25
Вид 5 - (1 5 5 5 5 5 5) с суммой 31

Итак, попробую для начала найти пару ортогональных покрытий вида (0 1 4 0 2).
В таком покрытии содержится 1 цепочка вида 2, 4 цепочки вида 3 и 2 цепочки вида 5.
Работать буду с Массивом №2, он мне больше нравится