Магические квадраты

[maxal]

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

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

я уже выше писал, какая выгода - см. post285314.html#p285314

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

А по вашей формуле можно получать ассоциативные и пандиагональные квадраты?

По приведенным формулам - нет. Но для ассоциативных и/или пандиагональных квадратов можно вывести аналогичные формулы (которые будут зависеть от меньшего числа параметров).

[Nataly-Mak]

Цитата:

По приведенным формулам - нет. Но для ассоциативных и/или пандиагональных квадратов можно вывести аналогичные формулы (которые будут зависеть от меньшего числа параметров).

Это ясно. И я уже всё это сделала в указанной выше статье "Общие формулы магических квадратов".

Формула для квадрата 5-го порядка, зависящая от 15 параметров, известна очень давно, я нашла её в книге Б. А. Кордемского "Математическая смекалка" (1957 г. издания). Приводит её и Чебраков в своей книге.

Если же строить магический квадрат 5-го порядка из массива, состоящего ровно из 25 чисел (например, квадраты из последовательных чисел Смита), тогда количество параметров можно уменьшить на 1. И эта формула тоже приведена в моей статье.

Однако даже 14 параметров (которые, кстати, все являются элементами квадрата!) перебрать из 25 возможных чисел - это очень большое количество вариантов. Мне это не по силам. А вам?

-- Ср фев 03, 2010 09:55:27 --

Вообще-то наша дискуссия "свалилась" в магические квадраты

Но продолжу.
В моей статье "Общие формулы магических квадратов - часть III" приведена общая формула магического квадрата 7-го порядка (см. рис. 11) в предположении, что квадрат строится из массива, состоящего ровно из 49 чисел (либо заранее задана магическая константа квадрата). В этой формуле 34 независимых переменных (все переменные являются элементами квадрата!).

Но вот можно ли найти по такой формуле магический квадрат? Надо, чтобы 34 переменных пробежали все 49 значений. Возможно выполнить такую программу на нормальном языке программирования?

[maxal]

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

Но вот можно ли найти по такой формуле магический квадрат? Надо, чтобы 34 переменных пробежали все 49 значений. Возможно выполнить такую программу на нормальном языке программирования?

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

Дискуссия перенесена в "Магические квадраты".

[Nataly-Mak]

maxal в сообщении #285330 писал(а):

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

Но вот можно ли найти по такой формуле магический квадрат? Надо, чтобы 34 переменных пробежали все 49 значений. Возможно выполнить такую программу на нормальном языке программирования?

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

Дискуссия перенесена в "Магические квадраты".

Ну, так ведь мы об одной задаче и говорим! Только вы говорите о построении квадрата из простых из произвольного массива чисел, а я - из ограниченного массива. Разница есть, но не принципиальная (с позиций программирования)
Хорошо, давайте рассматривать тот же квадрат 7-го порядка и строить его не из последовательных смитов (когда в массиве точно 49 чисел), а из произвольных. Тогда формула будет немного другая и, предполагаю, что параметров в ней будет не 34, а 35.
Что это меняет с точки зрения реализации алгоритма? Вы можете оптимизировать этот алгоритм настолько, чтобы выполнить программу за реальное время? Вот в чём мой вопрос!
И это та самая задача, над которой я бьюсь уже 4 месяца, и не могу решить.
А помочь никто не хочет

[maxal]

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

Хорошо, давайте рассматривать тот же квадрат 7-го порядка и строить его не из последовательных смитов (когда в массиве точно 49 чисел), а из произвольных.

Арифметические свойства смитов гораздо хуже простых чисел. Я же говорил об оптимизации поиска именно простых элементов. Со смитами задача сложнее, и перебор будет гораздо трудоёмче.

-- Wed Feb 03, 2010 02:12:30 --

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

О формуле Бергхольта см. статью "Общие формулы магических квадратов".

Я там обратил внимание на формулу Ермакова, которому якобы не удалось получить по ней традиционный магический квадрат. Вот значения параметров дающие таковой (а именно квадрат Дюрера):
$A=16$, $B=13$, $C=4$, $D=1$, $a=-1$, $b=0$, $c=4$, $d=0$

Да и наименьший 3x3 квадрат из последовательных смитов уже найден (у вас эта задача представлена как нерешённая) см. post275573.html#p275573

[maxal]

Кстати, там же приведен наименьший совершенный квадрат 4x4 из простых чисел. Однако, он не совсем минимальный - существует квадрат с той же магической константой 240, но меньшим максимальным элементом:

11, 79, 47, 103, 
89, 61, 53, 37, 
73, 17, 109, 41, 
67, 83, 31, 59

[Nataly-Mak]

maxal в сообщении #285335 писал(а):

Я там обратил внимание на формулу Ермакова, которому якобы не удалось получить по ней традиционный магический квадрат. Вот значения параметров дающие таковой (а именно квадрат Дюрера):
$A=16$, $B=13$, $C=4$, $D=1$, $a=-1$, $b=0$, $c=4$, $d=0$
Да и наименьший 3x3 квадрат из последовательных смитов уже найден (у вас эта задача представлена как нерешённая) см. post275573.html#p275573

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

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

Про Ермакова никаких "якобы"! Так написано в книге Кордемского, что Ермакову не удалось найти такие значения параметров.

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

-- Ср фев 03, 2010 14:14:23 --

Вчера я отправила ice00 письмо, в котором попросила его написать в OEIS предложение новой последовательности. Он обещал сделать это.
Приведу копию письма, чтобы показать, о какой последовательности идёт речь.

"Можно начать так, что предлагается новая последовательность – магических констант наименьших магических квадратов из чисел Смита.

Магический квадрат порядка 3 есть в книге: М. Гарднер. От мозаик Пенроуза к надёжным шифрам. – М.: Мир, 1993.
Вот этот квадрат:

94 382 346 
526 274 22 
202 166 454

Магическая константа S = 822.

Предлагаемые магические квадраты порядков 4 – 6 построены участниками научного форума dxdy.ru.
Далее приводятся эти квадраты со ссылками, где они находятся на форуме.

Квадрат порядка 4.
post226917.html#p226917

22 346 562 265 
778 274 85 58 
4 454 382 355 
391 121 166 517

Магическая константа S = 1195.

Квадрат порядка 5.
post257980.html#p257980

355 576 4 319 382 
454 85 391 648 58 
27 535 346 526 202 
706 166 378 121 265 
94 274 517 22 729

Магическая константа S = 1636.

Квадрат порядка 6.
post258614.html#p258614

729 4 636 762 22 319 
27 663 654 526 85 517 
391 645 58 378 438 562 
382 346 454 121 634 535 
355 648 94 483 627 265 
588 166 576 202 666 274

Магическая константа S = 2472.

Итак, последовательность магических констант следующая:

(n = 3) 822, (n = 4) 1195, (n = 5) 1636, (n = 6) 2472

Магические квадраты порядков 7 – 9 не найдены.
Магические квадраты порядков 10 – 35 построены. Эти квадраты можно посмотреть на сайте:
http://www.natalimak1.narod.ru/minsmit1.htm

Продолжение последовательности для магических квадратов порядков 10 - 35:

12202, 16335, 21333, 27612, 35185, 43968, 54013, 65464, 78281, 92422, 107932, 126404, 147816, 171556, 197041, 224506, 253587, 285314, 320620, 359151, 400064, 442886, 487920, 536844, 589129, 644797

Будем надеяться, что опубликование этой последовательности в OEIS поможет восполнить пробел – найти магические квадраты порядков 7 - 9.
_____

Для второй последовательности - магических констант наименьших магических квадратов из последовательных смитов - нам не хватает теперь всего двух квадратов: 4-го и 5-го порядка. Квадрат 6-го порядка найден. Для того, чтобы начать новую последовательность в OEIS, необходимо как минимум 4 первых члена последовательности.

Итак, будем искать квадраты 4-го и 5-го порядков из последовательных смитов?

Немного повторюсь. Я спрашивала tolstopuz'а, проверял ли он квадраты 4-го порядка. Он ответил, что не помнит точно, вроде проверял до миллиарда (или до двух, тут уже я не помню).
Зато точно знаю, что первые 1000 кандидатов я проверила по своей программе. Квадрат из этих кандидатов не был найден.

В случае построения магического квадрата 4-го порядка из последовательных смитов надо использовать алгоритм, рассчитанный на построение квадрата из массива, состоящего точно из 16 чисел. В этом случае формула квадрата будет зависеть от 7 переменных, и программа выполняется очень быстро (даже на Бейсике!).
Формула может быть, например, такой:

a1 a2 x1 a3
x6 a4 a6 a7
x7 x3 a5 x5
x4 x8 x9 x2

Здесь $ai$ (i = 1, 2, ..., 7) - независимые переменные, $xi$ (i = 1, 2, ..., 9) - зависимые переменные, выражаемые через ai и магическую константу квадрата, которая определятся заданным массивом чисел.

Всё есть для поиска квадрата!

Для квадрата 5-го порядка общая формула в моей статье (о чём уже сказано выше).
Кроме этой формулы есть другой алгоритм для построения магического квадрата 5-го порядка из смитов, который тоже здесь был представлен.
Есть, наконец, программа, которую сделал 12d3, но он не нашёл квадрат из последовательных смитов, а только из произвольных, и куда-то исчез. Его программа у меня, к сожалению, не работает.

Так, что ещё не упомянула?

Исчезли товарищи Бодигрим и tolstopuz, которые хорошо решали подобные задачи.

[Nataly-Mak]

Сейчас проверила ещё порядка 800 кандидатов в магический квадрат 4-го порядка из последовательных смитов.
Последний проверенный массив:

259179  259182  259186  259188  259195  259215  259246  259249  259258  259296  259335  259341  259360  259377  259393  259404

S = 1037101.

maxal,
вы, может быть, уже на 20-ом миллиарде, а я всё на первом миллионе проверяю. Пожалуйста, скажите, если вы проверили уже до 2 миллионов, чтобы мне не делать пустую работу.

[maxal]

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

вы, может быть, уже на 20-ом миллиарде, а я всё на первом миллионе проверяю. Пожалуйста, скажите, если вы проверили уже до 2 миллионов, чтобы мне не делать пустую работу.

Я проверил до $10^{12}$ и нашел лишь несколько потенциальных наборов из последовательных смитов для квадрата 4x4, используя некоторые необходимые условия для существования такого квадрата. Сколько-то из этих наборов потом даже проверил (с отрицательным результатом), а оставшиеся отложил до написания более эффективной процедуры проверки. Но руки пока так и не дошли.
Если вам интересно, то начальные смиты в наборах-кандидатах таковы:
91329687108, 92729436668, 96611496687, 132874826441, 159986092329, 165940397905, 176686027393, 286322657444, 315798713546, 436037888259, 557807843677, 563613691449, 572547474642, 666392165728, 676275305424, 676509590499, 680733657384, 758152678306, 773307270786, 775817553268, 786821119195, 801569383788, 819051495774, 819438518146, 882911909394, 890482581640, 904981318249, 939166938121

[Nataly-Mak]

Э-э-э...
Мне интересно, но таких смитов у меня нету и мой Бейсик с такими большими числами не работает.

Интересно, а какие необходимые условия вы предъвили потенциальному массиву чисел?
Я применяю только одно условие: сумма всех чисел массива кратна 4. Понятно, что массивов, удовлетворяющих этому условию, очень много. Я проверила уже больше 1500, квадрат не найден.
А процедура проверки у меня очень простая, на Бейсике 50 массивов проверяются примерно 3 минуты. На нормальном языке это время будет соизмеримо с секундами или даже с долями секунды.
У меня программа составлена на проверку сразу 50 массивов. Такими порциями я и проверяю.

Да, вот сейчас сообразила, ещё одно необходимое условие: среди чисел массива должно быть 4 числа, дающих в сумме магическую константу квадрата.

А ещё какие условия?

[maxal]

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

Интересно, а какие необходимые условия вы предъвили потенциальному массиву чисел?
Я применяю только одно условие: сумма всех чисел массива кратна 4.

Это само собой, эта сумма деленная на 4, представляет собой потенциальную магическую константу S. Из данного набора чисел я составлял все четверки различных чисел, сумма которых равна S. Таких четверок должно быть как минимум 10 (четыре строки Ri, четыре столбца Ci, две диагонали Di), но на самом деле даже 14 (добавляются четверки: V угловых элементов, I внутренних элементов и две четверки A и B противоположных граничных неугловых элементов). Принадлежность этим дополнительным четверкам элементов квадрата такая:

V A A V
B I I B
B I I B
V A A V

Определим граф, вершинами которого являются такие четверки, а ребро между двумя четверками означает наличие у них двух общих элементов. Тогда первые 10 четверок образуют независимое множество (т.е. вообще без ребер), а с дополнительными 4-мя четверками граф выглядит так:


Таким образом, возникает задача о поиске в графе, полученном из данного набора чисел, индуцированного подграфа, показанного выше. И тут уже можно использовать различные эвристики. Например, если в графе нет независимого множества размера 10, то он нам не подходит. Если нет двух вершин степени как минимум 6, то также не подходит и т.д.
Вот для примера граф соответствующий набору, начинающемуся с 91329687108 (при этом из всех элементов квадрата, вычтен этот минимальный элемент, а ребра помечены соответствующими парами общих элементов для простоты анализа, полные подграфы образованные однотипными ребрами выделены жирным):

Можете сами убедится, что искомого индуцированного подграфа в этом графе нет.

-- Wed Feb 03, 2010 13:48:31 --

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

мой Бейсик с такими большими числами не работает

Давно бы уже скачали и поставили себе Бейсик, который работает с большими числами. Называется UBASIC - см. http://en.wikipedia.org/wiki/UBASIC

[Nataly-Mak]

Это всё очень интересно!

(К сожалению, я не знаю теорию графов; но вот про дополнительные 4 четвёрки чисел, дающих в сумме магическую константу, - это здорово. Как-то никогда не обращала внимания на то, что есть такие четвёрки чисел в магическом квадрате 4-го порядка; о центральной четвёрке узнала совсем недавно, tolstopuz сказал.)

Получается, что каждый найденный вами потенциальный массив на 99% кандидат в магический квадрат - при таких жёстких требованиях к нему.

За ссылку на Бейсик спасибо. Я подумаю
Старческий консерватизм...
Кстати, лирическое отступление: "мать русского квадратостроения" отметила несколько дней назад 60-летие

[maxal]

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

Получается, что каждый найденный вами потенциальный массив на 99% кандидат в магический квадрат - при таких жёстких требованиях к нему.

Именно. Но поэтому же проверить их наверняка довольно трудоемкое занятие. Я проверил сколько-то из них вручную (по сути доказав, используя те или иные аргументы, что искомого индуцированного подграфа в их графах нет), но потом мне это надоело, и я отложил задачу до написания автоматической процедуры проверки. Конечно, проще было бы найти готовую библиотеку для поиска индуцированных подграфов, но сходу такую найти не удалось.

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

Кстати, лирическое отступление: "мать русского квадратостроения" отметила несколько дней назад 60-летие

Поздравляю и желаю дальнейших успехов на поприще квадратостроения!

-- Thu Feb 04, 2010 13:28:54 --

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

Мне интересно, но таких смитов у меня нету и мой Бейсик с такими большими числами не работает.

Если хотите сами поискать магические квадраты среди найденных мной кандидатов, то вот список их элементов, уменьшенных на минимальный элемент:

91329687108: [0, 15, 38, 47, 48, 52, 54, 57, 58, 63, 75, 84, 85, 90, 96, 110]
92729436668: [0, 7, 22, 25, 32, 34, 40, 50, 52, 75, 86, 87, 96, 108, 148, 166]
96611496687: [0, 3, 21, 22, 25, 29, 33, 35, 53, 54, 57, 60, 64, 67, 71, 90]
132874826441: [0, 7, 23, 25, 26, 59, 64, 80, 82, 84, 85, 98, 103, 116, 118, 170]
159986092329: [0, 2, 31, 33, 35, 83, 85, 87, 91, 93, 126, 145, 191, 193, 197, 224]
165940397905: [0, 7, 8, 11, 12, 15, 36, 38, 139, 143, 144, 145, 152, 153, 163, 170]
176686027393: [0, 8, 23, 31, 39, 47, 62, 77, 89, 97, 121, 124, 128, 163, 190, 197]
286322657444: [0, 43, 73, 78, 86, 91, 99, 116, 120, 121, 169, 172, 177, 190, 198, 199]
315798713546: [0, 3, 4, 6, 10, 24, 30, 42, 44, 49, 69, 73, 87, 94, 111, 114]
436037888259: [0, 5, 87, 117, 132, 159, 162, 186, 204, 209, 231, 256, 273, 285, 303, 343]
557807843677: [0, 5, 19, 31, 33, 46, 50, 64, 77, 85, 91, 104, 110, 123, 150, 176]
563613691449: [0, 6, 28, 33, 48, 61, 75, 95, 103, 108, 119, 123, 139, 146, 150, 166]
572547474642: [0, 1, 12, 21, 51, 60, 73, 75, 76, 86, 88, 96, 126, 150, 162, 163]
666392165728: [0, 10, 12, 14, 19, 24, 47, 48, 54, 65, 74, 88, 103, 120, 122, 136]
676275305424: [0, 2, 24, 25, 39, 61, 72, 86, 144, 169, 177, 178, 192, 200, 214, 237]
676509590499: [0, 5, 33, 36, 37, 43, 48, 51, 61, 65, 72, 75, 79, 83, 93, 115]
680733657384: [0, 12, 27, 57, 84, 87, 111, 126, 174, 207, 218, 221, 233, 234, 260, 261]
758152678306: [0, 26, 36, 40, 50, 72, 86, 108, 112, 120, 130, 144, 148, 152, 166, 170]
773307270786: [0, 66, 74, 82, 87, 91, 92, 100, 109, 126, 127, 140, 144, 153, 170, 183]
775817553268: [0, 16, 46, 56, 72, 82, 122, 134, 254, 256, 260, 266, 292, 302, 312, 314]
786821119195: [0, 27, 31, 63, 80, 89, 90, 108, 122, 171, 176, 180, 185, 217, 234, 243]
801569383788: [0, 22, 26, 35, 39, 44, 46, 52, 105, 109, 114, 118, 127, 129, 138, 164]
819051495774: [0, 18, 52, 62, 74, 80, 84, 92, 96, 104, 108, 122, 124, 132, 144, 156]
819438518146: [0, 117, 124, 137, 144, 151, 243, 261, 288, 346, 353, 355, 360, 362, 382, 389]
882911909394: [0, 80, 139, 143, 156, 160, 191, 208, 219, 254, 271, 276, 328, 334, 374, 391]
890482581640: [0, 14, 16, 36, 37, 39, 41, 52, 59, 68, 74, 75, 76, 80, 96, 129]
904981318249: [0, 7, 18, 25, 69, 70, 87, 89, 92, 94, 110, 111, 156, 162, 174, 180]
939166938121: [0, 13, 22, 45, 68, 81, 85, 87, 90, 91, 94, 99, 110, 113, 122, 144]

[Nataly-Mak]

maxal
Я проверила приведённые вами массивы.

Увы! Ни один из них в магический квадрат не сложился. Ошибка исключена, сразу после вашего последнего массива вставила массив, из которого построен квадрат tolstopuz'а:

...........
0 13 22 45 68 81 85 87 90 91 94 99 110 113 122 144
4 22 58 85 121 166 265 274 346 355 382 391 454 517 562 778

И для этого массива магические квадраты сразу выдаются.

Насчёт того, какой массив проверять по моей программе. Как мне кажется, моей программе абсолютно всё равно, какой в неё будет введён массив-кандидат - хорошо подготовленный или плохо подготовленный. Она проверяет любой массив по одному сценарию и выдаёт однозначный ответ: составляется из данного массива магический квадрат или нет.
Конечно, если накладывать на массив только одно условие (кратность суммы чисел массива 4), то кандидатов получается слишком много. Однако если переписать мою программу на нормальный язык программирования, то проверка, скажем, 10000 массивов займёт несколько минут.

Если у вас есть ещё кандидаты, давайте, я мигом проверю

P. S. Спасибо за поздравление.

[maxal]

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

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

По какому конкретно алгоритму она проверяет?

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

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

Однако если переписать мою программу на нормальный язык программирования, то проверка, скажем, 10000 массивов займёт несколько минут.

Это медленно, к сожалению.