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

[Nataly-Mak]

Pavlovsky
для прорывной идеи осталось додумать маленький кусочек

-- Пн авг 05, 2013 10:46:21 --

Может, для порядков N - составных помогут греко-латинские квадраты

Пример

Первый ортогональный квадрат:

0 3 6 1 4 7 2 5 8
2 5 8 0 3 6 1 4 7
1 4 7 2 5 8 0 3 6
3 6 0 4 7 1 5 8 2
5 8 2 3 6 0 4 7 1
4 7 1 5 8 2 3 6 0
6 0 3 7 1 4 8 2 5
8 2 5 6 0 3 7 1 4
7 1 4 8 2 5 6 0 3

Второй ортогональный квадрат:

0 3 6 1 4 7 2 5 8
1 4 7 2 5 8 0 3 6
2 5 8 0 3 6 1 4 7
6 0 3 7 1 4 8 2 5
7 1 4 8 2 5 6 0 3
8 2 5 6 0 3 7 1 4
3 6 0 4 7 1 5 8 2
4 7 1 5 8 2 3 6 0
5 8 2 3 6 0 4 7 1

Греко-латинский квадрат:

00 33 66 11 44 77 22 55 88
21 54 87 02 35 68 10 43 76
12 45 78 20 53 86 01 34 67
36 60 03 47 71 14 58 82 25
57 81 24 38 62 05 46 70 13
48 72 15 56 80 23 37 61 04
63 06 30 74 17 41 85 28 52
84 27 51 65 08 32 73 16 40
75 18 42 83 26 50 64 07 31

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

[Pavlovsky]

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

для прорывной идеи осталось додумать маленький кусочек

Есть хорошая старая комедия с Челентано – он играет роль владельца фирмы выпускающей чудобронестекло. В цехе помощники докладывают – господин инженер -всё сделано – время добавлять вашу секретную добавку…
Челентано им – отвернитесь… - поворачивается к печи, открывает люк и плюёт в кипящую стекломассу – ТЬФУ - вот вам моя секретная добавка…

[Nataly-Mak]

Решаю задачу о построении пандиагонального квадрата 5-го порядка из последовательных простых чисел. Похоже, решать закончила, так как имеющийся у меня генератор простых чисел дальше 2145000000 почему-то не хочет генерировать простые числа.
В интервале (1, 2145000000) все простые проверила. Если моя программа не врёт, решений в этом интервале нет.
У Jarek в пандиагональном квадрате 4-го порядка из последовательных простых чисел вон какие огромные числа. У меня таких и нету чисел.
В общем, зелёный виноград, не хочу такой кушать

Замечание о приведённых выше ортогональных латинских квадратах...
Эти квадраты пандиагональные в том смысле, что имеют одинаковые суммы по всем диагоналям, как главным, та и разломанным. Поэтому построенные из этих ЛК магические квадраты (как классические, так и нетрадиционные) тоже будут пандиагональными.

[Nataly-Mak]

Д-а-а-а... дьявольские они и есть дьявольские

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

Наименьший обычный магический квадрат 5-го порядка из последовательных простых чисел (см. A073520):

13 17 61 113 109
107 59 97 19 31
103 53 79 37 41
67 83 47 73 43
23 101 29 71 89
S=313

Взяла массив последовательных простых чисел, из которых составлен этот квадрат:

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

Запускаю программу, но... убираю требование быть простым числом сначала для одного элемента квадрата - решение не находится; затем для двух элементов и т.д. Наконец, когда требование быть простым было снято для 5 элементов квадрата, решение нашлось:

13 113 67 79 41
111 23 37 83 59
107 29 103 55 19
47 51 89 53 73
35 97 17 43 121
S=313

Вот ранжированный массив чисел, из которых составлен этот пандиагональный квадрат (звёздочками отмечены не простые числа):

13  17  19  23  29  *35*  37  41  43  47  *51*  53  *55*  59  67  73  79  83  89  97  103  107  *111*  113  *121*

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

Есть ли надежда на решение этой проблемы

Картинку покажу, найденный квадрат в программе mertz



Такое у меня первое приближение к решению, плохое, конечно.
Кто найдёт лучшее?

[dimkadimon]

Поздравляю Pavlovsky и Tristrom Cooke - они получили оригинальные решения. Pavlovsky, значит ваш метод 4 заработал? Жду новых результатов!

Я последние две недели путешествовал и совсем не думал о задаче. Осталось мало времени и большого не ожидаю. Попробую несколько мелких идей.

[dimkadimon]

Решение для N=7 и S=735 с двумя дырками:

(73,47,151,61,103,23,277),
(173, ? ,239,43,3,269,67),
(163,101,149,157,17,59,89),
(53,131,29,181,233,71,37),
(271,97,19,41,79,223,5),
(197,167,11,139,107,83,31),
(? ,251,137,113,193,7,229)

[Pavlovsky]

Вместо дырок можно вставить число? Пусть не простое.

[Nataly-Mak]

dimkadimon в сообщении #752760 писал(а):

Решение для N=7 и S=735 с двумя дырками:

(73,47,151,61,103,23,277),
(173, ? ,239,43,3,269,67),
(163,101,149,157,17,59,89),
(53,131,29,181,233,71,37),
(271,97,19,41,79,223,5),
(197,167,11,139,107,83,31),
(? ,251,137,113,193,7,229)

В дырки вставляются отрицательные числа:

(73,47,151,61,103,23,277),
(173,-59,239,43,3,269,67),
(163,101,149,157,17,59,89),
(53,131,29,181,233,71,37),
(271,97,19,41,79,223,5),
(197,167,11,139,107,83,31),
(-195,251,137,113,193,7,229)

Такие решения я называю приближениями к настоящему решению.

-- Ср авг 07, 2013 12:36:31 --

Новая головоломка в тему:
http://www.primepuzzles.net/puzzles/puzz_699.htm

Идея головоломки принадлежит Radko Nachev, решения найдены мной.
Для N=7 в минимальности квадрата не уверена. Скорее всего, он не минимальный. Это регулярный квадрат, то есть построен из квадрата Стенли. Наверное, есть нерегулярный квадрат с меньшей магической константой.
Задача сродни конкурсной, разница только в том, что разрешается использовать число 1.
Так что, можно решать попутно эту головоломку и публиковать решения на сайте у Карлоса.
И здесь, разумеется, тоже можно выкладывать
Эти решения не являются всё-таки решениями конкурсной задачи, поэтому их можно показывать.

[Nataly-Mak]

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

Ещё такой пандиагональный квадрат 7-го порядка из простых чисел нашла в черновых статьях:

113 67 443 439 31 149 191
379 101 89 281 43 317 223
211 293 97 163 449 41 179
233 389 131 109 461 73 37
359 241 13 107 173 479 61
47 263 409 311 139 181 83
91 79 251 23 137 193 659

$S=1433$
Не спешите вводить решение на конкурс
В квадрате есть одно не простое число.

В этом приближении всего одна "дырка"
Правда, и магическая константа довольно большая, больше, чем у dimkadimon.
В "дырке" находится не простое число 91.
Сейчас попробую применить к этому квадрату идею Pavlovsky. Не по полной программе, конечно, (программы-то у меня нет для этой идеи) а так - маленький эксперимент вручную.

-- Ср авг 07, 2013 19:24:43 --

Работает идея
Получила такой пандиагональный квадрат с магической константой 1399:

113 67 443 439 31 115 191
379 101 89 247 43 317 223
211 259 97 163 449 41 179
233 389 131 109 461 73 3
359 241 13 107 139 479 61
47 263 375 311 139 181 83
57 79 251 23 137 193 659

Только теперь в квадрате 5 не простых чисел, то есть 5 "дырок". Плохо получилось. Зато магическая константа уменьшилась.
Это я вычла из всех элементов одной группы 34.
Похоже, трудно подобрать такие комбинации прибавлений/вычитаний, чтобы все числа в результате этих операций получились простые.
Какой-то тут должен быть "маленький кусочек" алгоритма, который знает только Jarek

-- Ср авг 07, 2013 19:45:22 --

Теоретические размышления по поводу показанного выше эксперимента

Исходный пандиагональный квадрат 7-го порядка с одной "дыркой" регулярный, он получен из квадрата Стенли.
Полагаю, что уменьшение/увеличение элементов одной группы на одно и то же число будет давать опять же регулярные квадраты. Следовательно, в этом примере мы ничего не добьёмся: пандиагональный квадрат из различных простых чисел с магической константой меньше 1597 не может быть получен из исходного квадрата данными преобразованиями.

[Nataly-Mak]

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

[dmd]

Вообразим минимальный квадрат nXn из простых чисел. Если в каждой ячейке квадрата прибавить/отнять одну и ту же константу $d$, то пандиагональность сохранится, но магическая константа соответственно увеличится/уменьшится на $d\cdot n$ и квадрат уже будет не из простых. Обратная процедура тоже возможна. Будем собирать минимальный квадрат из чётных чисел, одну из ячеек которого зададим нулём. Для каждого собранного квадрата пробежимся в цикле по простым $d$ от $3$ до какого-то разумного предела, увеличивая все ячейки на $d$ и проверяя совокупную простоту квадрата.

Нигде не насочинял?

[Nataly-Mak]

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

269 243 347 257 299 219 473
369 137 435 239 199 465 263
359 297 345 353 213 255 285
249 327 225 377 429 267 233
467 293 215 237 275 419 201
393 363 207 335 303 279 227
1 447 333 309 389 203 425

Это получено в результате увеличения всех элементов исходного квадрата на 196.
Кстати, квадрат dimkadimon нерегулярный (как утверждает моя программа).

[Nataly-Mak]

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

If I understand correctly, you start with any pandiagonal square (easy to constuct, e.g. with all numbers equal) and while keeping pandiagonality intact, change terms (N at a time) to arrive at distinct prime terms.

Jarek
лукавите насчёт квадрата, состоящего из одинаковых чисел (если я правильно поняла перевод)?
Если мы возьмём пандиагональный квадрат, составленный из одинаковых чисел, то любое прибавление/вычитание одного и того же числа над элементами одной группы этого квадрата будет давать одинаковые числа в этой группе.

Пример
возьмём пандиагональный квадрат 5-го порядка, составленный из нулей. Прибавим к элементам первой групппы простое число 2, к элементам второй группы простое число 3 и т.д. В результате получим такой пандиагональный квадрат 5-го порядка из последовательных простых чисел:

2 3 5 7 11
5 7 11 2 3
11 2 3 5 7
3 5 7 11 2
7 11 2 3 5

Очень хороший квадрат! Тот самый, который я так долго искала
Одно плохо - этот квадрат составлен не из различных простых чисел. Каждое простое число в этом квадрате повторено 5 раз.

P.S. А может, в квадрате из одинаковых чисел и спрятан тот "маленький кусочек алгоритма", который надо додумать? Ну никак у меня этот "маленький кусочек" недодумывается

[Pavlovsky]

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

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

Это неверное предположение. Например мне подобными преобразованиями удалось получить квадрат порядка 7 с магической суммой 1565. В качестве исходных квадратов брались регулярные квадраты.

Для N=7 можно построить 4 ортоганальных пандиагональных латиснких квадрата. Пользуясь терминологией Россера, они получаются из путей P(1,2),P(1,3),P(1,4),P(1,5). Если пандиагональный квадрат регулярный, то два из четырех наборов, являются строками и колонками в исходном примитивном квадрате. То есть изменение этих наборов действительно приводит к получению снова регулярного квадрата. Эта операция эквивалентна добавлению/вычитанию константы к строкам(колонкам) примитивного квадрата. Но ведь еще остается две группы, изменение их должно приводить к нерегулярному квадрату.

[Nataly-Mak]

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

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

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

Это неверное предположение. Например мне подобными преобразованиями удалось получить квадрат порядка 7 с магической суммой 1565. В качестве исходных квадратов брались регулярные квадраты.

Я уже написала об этом.

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

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

Написала это не просто так. Я построила примитивный квадрат из исходного квадрата и посмотрела, какие числа изменяются в результате преобразования. Эти числа в квадрате расположились буквой Г, а не в строках или столбцах. Отсюда и следует, что примитивный квадрат в результате такого преобразования не получается. Это подтвердил эксперимент.

Или для вас важно объяснить всё самому себе, насмотря на уже данное объяснение?