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

[trurl]

S=737, 1 hole.

(Оффтоп)

f[{
{3,47,239,1,229,181,37},
{269,73,211,23,83,11,67},
{13,53,31,197,59,227,157},
{137,173,17,163,61,7,179},
{79,43,191,151,167,5,101},
{109,149,29,71,97,193,89},
{127,199,19,131,41,113,107}
}]

f[{
{3,227,181,7,73,97,149},
{127,29,37,197,17,191,139},
{61,263,157,53,5,179,19},
{23,11,41,199,223,89,151},
{251,163,83,43,67,71,59},
{193,31,137,107,113,109,47},
{79,13,101,131,239,1,173}
}]

[Nataly-Mak]

trurl в сообщении #760942 писал(а):

S=737, 1 hole.

Отличные решения.
Преобразовала второе решение (параллельный перенос на торе), чтобы с 1 начиналось:

1 173 79 13 101 131 239
97 149 3 227 181 7 73
191 139 127 29 37 197 17
179 19 61 263 157 53 5
89 151 23 11 41 199 223
71 59 251 163 83 43 67
109 47 193 31 137 107 113

dimkadimon
ваш рекорд по решениям с использованием числа 1 побит
Но и это ещё, наверняка, не наименьшее решение.
Кстати, наименьший обычный магический квадрат 7-го порядка из различных простых чисел плюс число 1 имеет магическую константу 699 (см. A073502).

С точки зрения приближения к решению $S=737$ --- тоже очень хорошее приближение: действительно одна дырка - не простое число 1.

(Оффтоп)

trurl
вы были участником конкурса?

[Nataly-Mak]

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

вот все 69 потенциальных массивов для магической константы 743, найденных программой whitefox

Видим, что максимальное число 313. Берём все простые числа от 3 до 313 и выбрасываем те числа, которые не присутствуют ни в одном массиве, если таковые имеются.

Не присутствуют ни в одном массиве всего два простых числа - 307 и 311.
Таким образом, объединённый массив для магической константы 743 состоит из 62 простых чисел:

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  241  251  257  263  269  271  277  281  283  293  313 

Если не выбрасывать числа 307 и 311, то есть задать все простые числа от 3 до 313, тогда надо задать 64 числа в массиве.

-- Пт сен 06, 2013 18:22:35 --

Одна из программ whitefox строит приближения другого типа.
Пример приближения к решению $S=737$



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

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,239,257

И перед вами набор из 4-х точных попарно ортогональных покрытий приведённого массива.
Что же не так? А вот что - в покрытиях есть бракованные цепочки, то есть цепочки, сумма чисел в которых не равна магической константе. Иными словами, эти цепочки не принадлежат БД для данной магической константы и данного массива чисел.

[Nataly-Mak]

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

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

x1 x9 x17 x25 x5 x13 x21 x29
x10 x2 x26 x18 x14 x6 x30 x22
x27 x19 x11 x3 x31 x23 x15 x7
x20 x28 x4 x12 x24 x32 x8 x16
k-x5+p1 k-x13-p1 k-x21+p3 k-x29-p3 k-x1+p1 k-x9-p1 k-x17+p3 k-x25-p3
k-x14-p1 k-x6+p1 k-x30-p3 k-x22+p3 k-x10-p1 k-x2+p1 k-x26-p3 k-x18+p3
k-x31-p3 k-x23+p3 k-x15-p1 k-x7+p1 k-x27-p3 k-x19+p3 k-x11-p1 K-x3+p1
k-x24+p3 k-x32-p3 k-x8+p1 k-x16-p1 k-x20+p3 k-x28-p3 k-x4+p1 k-x12-p1

При рассмотрении этой схемы обнаружила, что напрасно волновалась по поводу параметров $p_i$, так как при описании квадрата они все исчезают.

Я решила пристальнее посмотреть на алгоритм, использующий псевдокомплементарные числа, для построения пандиагональных квадратов 8-го порядка.
В цитате вы видите схему квадрата для данного алгоритма.
Интересно, что искать надо всего 32 элемента квадрата, остальные 32 определяются заданной константой комплементарности k (константа комплементарности определяется магической константой квадрата S: $k=S/4$) и отклонениями от неё.

Далее, для искомых 32 элементов числа массива должны быть распределены в 4 группы. Если у нас будет задан конкретный массив из 64 чисел (как, например, для магической константы 1154), то в каждой группе должно быть ровно 8 пар псевдокомплементарных чисел, в первой группе с отклонением p1, во второй группе - с отклонением -p1, в третьей группе - с отклонением p3, и в четвёртой группе - с отклонением -p3.
Это довольно жёсткое разбиение массива из 64 чисел, не для любого набора отклонений оно может существовать.
Когда я разрабатывала этот алгоритм, пользовалась массивом большего размера, а не точно из 64 чисел. В этом случае проще найти подходящие 4 группы чисел по заданным отклонениям, надо только следить, чтобы в каждой группе было не менее 8 пар псевдокомплементарных чисел.

А если разбиение массива на 4 группы найдено, дальше всё просто: организуем перебор по схеме. Каждый элемент может принимать значения только в своей группе, то есть только 16 значений.
Для оптимизации перебора надо бы сделать общую формулу такого квадрата, то есть описать предложенный выше квадрат и решить систему уравнений.

dmd куда-то пропал. Описать-то я могу, решить систему не могу.

dmd, ау! Вы мне поможете?

[whitefox]

Сегодня запустил на длительный поиск программу поиска четвёрок попарно ортогональных точных покрытий.

Через 8,5 часов работы прервал.
Пока результата нет.

Кому интересно, программу можно взять здесь: http://yadi.sk/d/Qr1NDjYR8q67V
Там же её исходник.

Если у кого программа будет выводить сообщения крякозябрами, запускайте пакетный файл.

Программу можно прервать в любой момент, а затем продолжить.

[Nataly-Mak]

Описание квадрата получилось очень коротким:

x1+x9+x17+x25+x5+x13+x21+x29=S
x10+x2+x26+x18+x14+x6+x30+x22=S
x27+x19+x11+x3+x31+x23+x15+x7=S
x20+x28+x4+x12+x24+x32+x8+x16=S
x1+x10+x27+x20-x5-x14-x31-x24=0
x9+x2+x19+x28-x13-x6-x23-x32=0
x17+x26+x11+x4-x21-x30-x15-x8=0
x25+x18+x3+x12-x29-x22-x7-x16=0

В статье написано, что мне удалось свести перебор к 24 свободным переменным. Но я не решала систему уравнений. Что даст решение системы? Интересно!

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

Кстати, данный алгоритм не может быть применён для поиска квадрата с магической константой 1154. Для данного алгоритма требуется, чтобы была константа комплементарности определена, а она равна S/4.

[Nataly-Mak]

Хочу попробовать применить данный алгоритм (использование псевдокомплементарных пар чисел) для построения пандиагонального квадрата 8-го порядка из различных простых чисел с магической константой 1160.
$K=S/4=290$
По программе whitefox (хорошая программа!) нашла 23 потенциальных массива, из них сделала объединённый массив, который состоит из 74 различных простых чисел:

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  241  251  257  263  269  271  277  281  283  293  307  311  313  317  331  337  347  349  353  359  379  383  389

Хороший массив, не очень большой.

Теперь надо написать программу. Но дело за общей формулой. Систему пока никто не решил
Придётся обратиться за помощью в Спортлото

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

Для начала надо попробовать найти разбиение приведённого массива на 4 группы псевдокомплементарных пар с заданными отклонениями p1, p3, -p1, -p3 (в каждой группе не менее 8 пар). Эту программку тоже надо написать, чем и займусь прямо сейчас.

[Nataly-Mak]

Программку разбиения массива на 4 группы псевдокомплементарных пар чисел написала.
По заданным отклонениям p1,-p1, p3, -p3 программа выдаёт 4 группы пар чисел.
Например, при отклонениях p1, -p1, p3, -p3 равных 10, -10, 20, -20 соотвестственно получим такие 4 группы пар для $K=290$:

(Оффтоп)

7  293 
 17  283 
 19  281 
 23  277 
 29  271 
 31  269 
 37  263 
 43  257 
 59  241 
 61  239 
 67  233 
 71  229 
 73  227 
 89  211 
 101  199 
 103  197 
 107  193 
 109  191 
 127  173 
 137  163 
 149  151 

OTKLONENIE 10 
KOLICHESTVO PAR 21 

 3  277 
 11  269 
 17  263 
 23  257 
 29  251 
 41  239 
 47  233 
 53  227 
 83  197 
 89  191 
 101  179 
 107  173 
 113  167 
 131  149 

OTKLONENIE -10
KOLICHESTVO PAR 14 

 3  307 
 17  293 
 29  281 
 41  269 
 47  263 
 53  257 
 59  251 
 71  239 
 83  227 
 113  197 
 131  179 
 137  173 

OTKLONENIE 20 
KOLICHESTVO PAR 12 

 7  263 
 13  257 
 19  251 
 29  241 
 31  239 
 37  233 
 41  229 
 43  227 
 47  223 
 59  211 
 71  199 
 73  197 
 79  191 
 89  181 
 97  173 
 103  167 
 107  163 
 113  157 
 131  139 

OTKLONENIE -20
KOLICHESTVO PAR 19

Понятно, что должны быть выбраны точно по 8 пар из каждой группы, причём все числа, входящие в эти пары, должны быть различные. Возможно ли это при данном разбиении, я пока не проверила. Вообще-то, это проверится и при построении квадрата - при переборе всех элементов по схеме (или по общей формуле).

[whitefox]

Эксперименты с программой поиска четвёрок попарно ортогональных точных покрытий показали, что поиск идёт не достаточно быстро, в то время как генерация полумагических квадратов осуществляется с высокой скоростью.

Поэтому предлагаю следующий подход к созданию многопоточной программы:

1. программа должна иметь "генератор заданий", "диспетчер" и неограниченное количество "обработчиков";
2. каждый из этих элементов выполняется в отдельном потоке;
3. генератор заданий находит полумагические квадраты и помещает их в "очередь заданий";
4. диспетчер извлекает очередное задание из очереди и передаёт его очередному обработчику;
5. если "очередь обработчиков" пуста, то диспетчер создаёт нового обработчика и передаёт задание ему;
6. обработчик полным перебором проверяет возможность из данного полумагического квадрата построить пандиагональный магический квадрат;
7. когда обработчик завершает своё задание, он становится в очередь обработчиков.

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

Фактически в программе должны быть два генератора и два диспетчера для порождения и обработки двух последовательностей полумагических квадратов, отвечающих шаблонам (01402,01402) и (01402,00511) соответственно.

[Nataly-Mak]

И mertz куда-то пропал, так и не сделав до конца программу для поиска решения $S=737$
Было бы весьма интересно посмотреть, что делала бы программа, получив в своё распоряжение жёстко ограниченный массив простых чисел - не 75 первых нечётных простых, как в последней версии mertz сделал, а всего 57 первых нечётных простых чисел (от 3 до 271). Никакие большие числа тогда бы не лезли в решения, как сейчас лезут.
Увы, эксперимент пока откладывается на неопределённое время. Может быть, Jarek это сделает, когда вернётся.

[whitefox]

Исправил баг, ссылка прежняя http://yadi.sk/d/Qr1NDjYR8q67V

[Nataly-Mak]

Подождала, подождала решение системы...
Ну и решила написать программу без общей формулы. Как-то мне тогда удалось свести перебор к 24 свободным переменным, сейчас получилось 25. Может быть, я фиксировала угловой элемент квадрата.

Как бы там ни было, алгоритм работает!
Единственный прокол - не хватило разных чисел, чего я и боялась. Но этот прокол можно ликвидировать, если постараться Разбиений существует много.
Если уж для магической константы 1160 не удастся этот прокол ликвидировать, то для следующих констант (побольше) должно всё получиться.

В верхней половинке квадрата всё хорошо, повторений нет, это первые 32 элемента, а вот те элементы, которые уже определяются константой комплементарности и отклонениями, почти все повторяются.

Это верхняя половинка квадрата:

5  7  137  283  317  251  53  107 
127  311  3  97  17  71  257  277 
113  11  241  233  179  223  29  131 
281  263  149  59  13  47  191  157

Тут всё замечательно, хватило разных чисел на половинку.

А это весь квадрат, в нижней половинке полно повторений:



Программа работает быстро. Я использовала разбиение с отклонениями: 32 (11 пар), -32 (14 пар), 4 (19 пар), -4 (12 пар).
В этом алгоритме вся сложность в том, чтобы найти разбиение массива чисел на 4 группы, содержащие по 8 непересекающихся пар (условие это необходимое, но не достаточное для построения квадрата). Это примерно то же самое, что найти набор из 4-х точных попарно ортогональных покрытий для квадрата 7-го порядка.
Для квадрата с магической константой 1584 у меня это получилось быстро.

[Nataly-Mak]

Сегодня целый день (балее 14 часов) работала программа mertz, искала решение $S=743$ (последняя версия Pan3.exe, в которой задано 75 первых нечётных простых чисел).
Вот что нашла:



У меня вопрос к создателям программы Jarek и mertz:
если я завтра снова буду крутить эту же программу и искать то же самое решение $S=743$, у меня будут другие решения искаться или всё будет повторяться один в один?
Другими словами: есть ли в программе элемент случайности?

P.S. Какое хорошее приближение мы видим на иллюстрации! Всего одна дырка - повторенное простое число 101. Нет больших чисел, максимальное число 283 (максимально возможное простое число для магической константы 743 равно 313).

[mertz]

It is random every run. I have altered Jarek's program so I can not make any guarantee that it is working correctly.

S=737, first 60 primes. dup 179, non-prime 85.

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

f[{
{3,173,191,73,199,85,13},
{103,151,53,23,7,269,131},
{127,89,193,149,5,113,61},
{101,67,107,79,163,179,41},
{167,11,47,271,29,31,181},
{139,227,37,83,137,43,71},
{97,19,109,59,197,17,239}
}]

[Nataly-Mak]

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

It is random every run. I have altered Jarek's program so I can not make any guarantee that it is working correctly.

Будем ждать возвращения Jarek.

Цитата:

S=737, first 60 primes. dup 179, non-prime 85.

Первое решение хорошее, во втором есть недопустимое число 269, так что, фактически две дырки.

Число 269 появляется часто, настырное
По-хорошему, его тоже надо выбросить. В массиве надо оставить только (!) 56 простых чисел; я показывала этот массив выше: все числа от 3 до 271, кроме числа 269.

В программе должно быть либо:
1. ввод данных из внешнего файла, в котором записаны простые числа;
2. исходные данные (135 первых нечётных простых чисел) прямо в программе в виде списка данных (в Бейске, насколько помню, для этого используется оператор Data).

Откуда-то ведь исходные данные вводятся в программу.
В обоих случаях можно задать программе конкретный массив из 56 простых чисел, который я показала.

-- Вс сен 08, 2013 07:24:30 --

Предварительные итоги неутешительны...
Пока всё плохо.
Поиск решения $S=733$ идёт с трудом (алгоритм 4-х точных попарно ортогональных покрытий), нужны мощные вычислительные ресурсы, которых у нас не так много (имею в виду российских участников темы).
Магические константы 737 и 743 по программе Jarek-mertz вроде и подают надежду, но решения тоже не находятся, хотя несколько участников усердно крутят эту программу.

На форуме ПЕН я писала: "Как специалист по квадратам, я хорошо представляю, насколько трудно найти оптимальное решение 733". Пока моё высказывание подтверждается.

Вспоминаю историю. Поиск наименьшего решения для N=6 из различных простых чисел был очень долгим, работали maxal, Pavlovsky, svb и я.
После того, как svb разработал замечательный алгоритм, он нашёл решение $S=486$. И... недоработали
Оптимальным решением оказалось $S=450$ (стало известно совсем недавно; сообщил автор этого решения Radko Nachev).
Вот так всё непросто!