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

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

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

для S=733 -- 2.

Ну, если для магической константы 733 существует в природе всего два массива, они оба есть в моей статье

Код:

№1
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  233  239
№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

Pavlovsky
флаг вам в руки, всего два массива

Я считаю, что с минимальной константы 733 и надо начинать проверку. Что зря силы и время тратить на бОльшие константы.

whitefox · 19/12/10 1546

Nataly-Mak
Для S=735 существует всего 3 массива простых:

Код:

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,223,227,229,241;

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,229,239,241;

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,229,257;

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

whitefox
спасибо.
Возьму на вооружение.

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

Разумеется, все результаты Jarek имеют бесспорную ценность в этом поиске.

Pavlovsky · 21/02/10 1594 Екатеринбург

Неспешно обдумываю алгоритм проверки. Выбираю из двух вариантов: либо делать перебор по общей формуле или строить 4 разбиения на N групп по N чисел.
Торопиться некуда. Вдруг кто сделает это раньше, тогда и делать ничего не надо.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

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

Вдруг кто сделает это раньше, тогда и делать ничего не надо.

(Оффтоп)

YuriiS уже сделал :lol:

Вы бы поговорили с ним поласковей, авось он вам и открыл бы результат. "Кухарок" он слушаться не хочет

Pavlovsky · 21/02/10 1594 Екатеринбург

(Оффтоп)

Между "сделал" и "сказал что сделал" огромная разница.

whitefox · 19/12/10 1546

Pavlovsky
Для второго варианта предлагаю следующий подход.

Заданы: N, S и набор простых.

Находим все разбиения числа S на сумму N различных слагаемых из заданного набора простых (с точностью до порядка слагаемых).

Четырежды решаем задачу точного покрытия заданного набора простых найденным множеством разбиений (например, использую алгоритм "танцующих связей" Д. Кнута). При этом следим, чтобы полученные покрытия были попарно ортогональны (то есть чтобы любое разбиение из одного покрытия пересекалось с любым разбиением из другого покрытия точно в одной точке).

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

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

А вот и база данных для массива №1 (см. выше) с магической константой 733 (разумеется, показываю только несколько первых цепочек). Цепочки нормализованы. Всего найдено 393510 нормализованных цепочек. Нехилая БД.

(Оффтоп)

Код:

 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  79  199  211  229 
 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 
 3  5  7  97  181  211  229 
 3  5  7  97  193  199  229 
 3  5  7  101  149  229  239 
 3  5  7  101  151  227  239 
 3  5  7  101  167  211  239 
 3  5  7  101  179  199  239 
 3  5  7  101  179  211  227 
 3  5  7  101  181  197  239 
 3  5  7  101  191  197  229 
 3  5  7  101  191  199  227 
 3  5  7  101  193  197  227 
 3  5  7  103  149  227  239 
 3  5  7  103  179  197  239 
 3  5  7  103  191  197  227 
 3  5  7  107  173  199  239 
 3  5  7  107  173  211  227 
 3  5  7  107  179  193  239 
 3  5  7  107  181  191  239 
 3  5  7  107  191  193  227 
 3  5  7  109  173  197  239 
 3  5  7  109  179  191  239 
 3  5  7  109  181  199  229 
 3  5  7  113  137  229  239 
 3  5  7  113  139  227  239 
 3  5  7  113  149  227  229 
 3  5  7  113  167  199  239 
 3  5  7  113  167  211  227 
 3  5  7  113  173  193  239 
 3  5  7  113  179  197  229 
 3  5  7  113  179  199  227 
 3  5  7  113  181  197  227 
 3  5  7  127  151  211  229 
 3  5  7  127  163  199  229 
 3  5  7  127  167  197  227 
 3  5  7  127  173  179  239 
 3  5  7  127  173  191  227 
 3  5  7  127  181  199  211 
 3  5  7  131  137  211  239 
 3  5  7  131  149  199  239 
 3  5  7  131  149  211  227 
 3  5  7  131  151  197  239 
 3  5  7  131  157  191  239 
 3  5  7  131  163  197  227 
 3  5  7  131  167  181  239 
 3  5  7  131  167  191  229 
 3  5  7  131  167  193  227 
 3  5  7  131  179  181  227 
 3  5  7  131  179  197  211 
 3  5  7  131  191  197  199 
 3  5  7  137  149  193  239 
 3  5  7  137  151  191  239 
 3  5  7  137  157  197  227 
 3  5  7  137  163  179  239 
 3  5  7  137  163  191  227 
 3  5  7  137  173  179  229 
 3  5  7  137  173  181  227 
 3  5  7  137  173  197  211 
 3  5  7  137  179  191  211 
 3  5  7  137  191  193  197 
 3  5  7  139  149  191  239 
 3  5  7  139  151  199  229 
 3  5  7  139  157  193  229 
 3  5  7  139  167  173  239 
 3  5  7  139  173  179  227 
 3  5  7  149  151  179  239 
 3  5  7  149  151  191  227 
 3  5  7  149  157  173  239 
 3  5  7  149  163  167  239 
 3  5  7  149  163  179  227 
 3  5  7  149  167  173  229 
 3  5  7  149  167  191  211 
 3  5  7  149  173  197  199 
 3  5  7  149  179  191  199 
 3  5  7  149  179  193  197 
 3  5  7  149  181  191  197 
 3  5  7  151  157  181  229 
 3  5  7  151  157  199  211 
 3  5  7  151  163  193  211 
 3  5  7  151  167  173  227 
 3  5  7  151  179  191  197 
 3  5  7  157  173  191  197 
 3  5  7  163  167  191  197 
 3  5  7  167  173  179  199 
 3  5  7  167  173  181  197 
 3  5  7  167  179  181  191 
 3  5  11  19  227  229  239 
 3  5  11  37  211  227  239 
 3  5  11  47  199  229  239 
 3  5  11  47  211  227  229 
 3  5  11  53  193  229  239 
 3  5  11  59  199  227  229 
 3  5  11  61  197  227  229 
 3  5  11  67  179  229  239 
 3  5  11  67  181  227  239 
 3  5  11  67  191  227  229 
 3  5  11  67  197  211  239 
 3  5  11  71  193  211  239 
 3  5  11  73  173  229  239 
 3  5  11  73  191  211  239 
 3  5  11  79  167  229  239 
 3  5  11  79  179  227  229 
 3  5  11  79  197  199  239 
 3  5  11  79  197  211  227 

Поиск БД занял секунд 20.

-- Ср авг 28, 2013 12:13:58 --

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

Заданы: N, S и набор простых.

Находим все разбиения числа S на сумму N различных слагаемых из заданного набора простых (с точностью до порядка слагаемых).

whitefox
как я понимаю, S - это магическая константа квадрата. Пусть, например, $S=733$ .
Означает ли вторая фраза: найти все нормализованные цепочки (в моей терминологии), то есть построить БД? То, что я показала выше.

whitefox · 19/12/10 1546

Nataly-Mak
Да.

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

whitefox
осталось "потанцевать" с этими цепочками

whitefox · 19/12/10 1546

Алгоритм "танцующих связей" для решения задачи точного покрытия:
http://arxiv.org/pdf/cs/0011047v1.pdf

Nataly-Mak · 22/03/08 ∞ 7154 Саратов

Красивое название :roll:

Это у нас уже третий алгоритм будет.
Алгоритм №1 - Jarek
Алгоритм №2 - мой.
Алгоритм №3 - алгоритм точного покрытия ("танцующие связи").

whitefox
а реализовать? :wink: