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

[mertz]

I have seven 1 hole solutions now. If the error is a non-prime, it is always a multiple of 5.

[Nataly-Mak]

mertz
у вас есть решение $S=733$ с 7 дырками? Покажите, пожалуйста.

[mertz]

s=737. 15 solutions. 1 hole.

The program find zero solutions for 733 and 735.

I put the inner loop back in. It only runs if holes < 4. It works once in every 50,000 searches. Makes more 1 hole solutions.

https://www.dropbox.com/s/pvpcyeuf9fb8355/Pan2.exe

[Nataly-Mak]

mertz
работаю по новой версии программы.
Сегодня задала 2 потока, работает 1. Отлынивает мой компьютер
Но всё-таки удалось получить решение с одной дыркой для $S=737$, раньше у меня были решения только с двумя дырками для этой магической константы.



В общем, магическая константа 737 подаёт надежды.

Написала программу построения шаблонов (старую не нашла, пропала, наверное со старым компьютером).
Построила шаблон из вычетов по модулю 6 (по данным, полученным whitefox) для магической константы 733.
Все цепочки вроде допустимого вида (надо тщательнее посмотреть на все диагонали); по суммам тоже, кажется, всё в порядке. А вот с количествами вычетов непорядок. Должно быть 23 вычета 1 и 25 вычетов 5. В данном шаблоне это не выполняется.

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

-- Сб авг 31, 2013 12:22:50 --

Теперь вроде всё правильно:

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

Можно попробовать строить квадрат по этому шаблону, используя общую формулу.
Будет две группы чисел (23 числа и 25 чисел), 23 свободных переменных.
Как показывает мой опыт, перебор для подобного шаблона, состоящего из двух больших групп вычетов, идёт очень долго.

Сейчас попробую шаблон из вычетов по модулю 9.

[whitefox]

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

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

[Nataly-Mak]

whitefox
ещё нужны шаблоны?

[whitefox]

Давайте.

[Nataly-Mak]

(Оффтоп)

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

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

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

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

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

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

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

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

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

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

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

Хватит?
На изоморфность не проверяла.

[whitefox]

Спасибо

[Nataly-Mak]

Шаблон из вычетов по модулю 9 не захотел быстро построиться, не дождалась.
Сделала шаблон из вычетов по модулю 5. Может быть, это и лучше. Здесь 4 группы чисел примерно одинакового размера,
вычет 0 - 1 число
вычет 1 - 11 чисел
2 - 12
3 - 14
4 - 11

 0  1  1  1  1  1  3 
 1  2  2  3  4  3  3 
 1  2  2  4  3  3  3 
 1  4  3  4  2  2  2 
 1  3  3  4  4  2  1 
 1  4  4  4  2  4  4 
 3  2  3  3  2  3  2 

Попробую написать программу по этому шаблону, посмотрю, как будет идти перебор.

[Nataly-Mak]

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

Есть небольшой успех в программе по общей формуле (без шаблонов), нашла решение с 9 дырками для магической константы 733:

 103  0  41  149  139  0  3 
 17  197  73  151  167  31  97 
 239  0  67  7  131  0  163 
 109  53  0  79  0  157  19 
 37  23  61  193  101  107  211 
 29  229  0  71  47  59  113 
 199  13  0  83  0  173  127 

Это у меня уже второе приближение найдено для константы 733; первое приближение было с 35 найденными элементами (14 дырок), оно показано выше; такие приближения находятся легко.
Здесь, кажется, все дырки уже можно заполнить (вычислить), надо посмотреть.

Сейчас поставлю выход после 42 найденных элементов, то есть буду искать решение с 7 дырками.

[Nataly-Mak]

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

Здесь, кажется, все дырки уже можно заполнить (вычислить), надо посмотреть.

Вычислила дырки, их осталось восемь: два повторения (127 и 173), отрицательное число (-1) и остальные не простые числа.



Господа, у кого есть программа борьбы с дырками, попробуйте с этим решением поколдовать.

Ну, хоть какое-то решение найдено, есть на что глянуть, если очень захочется
Лучше у меня пока не получается.

P.S. Решение в нормальном формате (если кто поколдовать захочет):

103 91 41 149 139 207 3
17 197 73 151 167 31 97
239 127 67 7 131 -1 163
109 53 173 79 143 157 19
37 23 61 193 101 107 211
29 229 185 71 47 59 113
199 13 133 83 5 173 127

[Jarek]

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

Jarek
вопрос к вам: какой массив простых чисел вы задействовали в вашей программе
При поиске решения с магической константой 737 сейчас у меня появилось решение с двумя ошибками, в котором присутствует число 373. Это число ни в каком случае не может входить в решение с магической константой 737, так как оно слишком большое для данной магической константы.
Я определяю максимально возможный размер массива так: вычисляю сумму всех чисел для квадрата с данной магической константой; при $S=737$ сумма всех чисел в квадрате равна 5159. Далее вычисляю сумму первых 48 нечётных простых чисел - от 3 до 227 (она равна 4886) и потом смотрю на разность этих двух сумм. В данном примере $5159-4886=273$.
Очевидно, что число 373 не может входить в квадрат с магической константой 737.

I didn't do a good job here, all primes below 800 are allowed by the program. You are right, the program should not recognize as primes numbers, which are too large to be used in final solution.

-- Сб авг 31, 2013 21:24:19 --

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

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

I didn't do that. In theory it might be possible, but tests I made once were discouraging and I abandoned the idea of trying to fix such solutions.

[Nataly-Mak]

Только что найдено решение с 7 дырками с магической константой 733:

 89  0  181  173  73  0  3 
 11  113  19  199  131  163  97 
 83  0  41  31  59  0  227 
 197  157  0  47  0  5  23 
 53  29  151  139  179  103  79 
 61  71  7  107  193  127  167 
 239  149  0  37  13  43  137 

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

Поставлю выход для 44 найденных элементов, будет решение с 5 дырками (если будет).

Jarek
спасибо за ответы на вопросы.

-- Вс сен 01, 2013 00:01:56 --

Увы, дырок меньше не стало.
Итак, решение $S=733$ с 7 дырками:

89 89 181 173 73 125 3
11 113 19 199 131 163 97
83 125 41 31 59 167 227
197 157 219 47 85 5 23
53 29 151 139 179 103 79
61 71 7 107 193 127 167
239 149 115 37 13 43 137

Сейчас моя программа ищет решение с 5 дырками.

[whitefox]

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)).