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

[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 массивов займёт несколько минут.

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

[Nataly-Mak]

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

Эта формула составлена в предположении, что квадрат строится из массива, состоящего точно из 16 чисел. Формула в таком случае зависит всего от 7 параметров и проверка выполняется очень быстро.

Возможно, это будут даже не минуты (для 10000 массивов), а секунды.
Потому что, например, сравнивая работу программ ice00 со своими (аналогичными) программами, я вижу, что быстродействие моего Бейсика в сотни раз ниже.

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

Приведённые вами массивы я проверила за 2 минуты.

[maxal]

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

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

Эта формула составлена в предположении, что квадрат строится из массива, состоящего точно из 16 чисел. Формула в таком случае зависит всего от 7 параметров и проверка выполняется очень быстро.

Но выборка 7 значение параметров из 16 - это $16\cdot 15\cdot 14\cdot 13\cdot 12\cdot 11\cdot 10=57657600$ вариантов. Вероятно, их можно уменьшить в десяток раз с учётом поворотов/симметрий квадрата, но все равно остается более $10^6$ вариантов. Вы уверены, что вы учитываете все варианты и что ваша программа гарантированно найдёт магический квадрат, если он существует?

[Nataly-Mak]

Да, уверена.

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

Впрочем, вы ведь сами можете реализовать эту формулу и убедиться, насколько эффективно будет работать программа.
На языке PARI/GP программа выполнится за долю секунды (для 50 массивов).

Проверьте!

Кстати, я не сокращаю количество вариантов за счёт отображений/поворотов, программа выдаёт все магические квадраты, построенные из данного массива.

[maxal]

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

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

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

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

Я что-то перестал понимать, как именно работает ваша программа. Сначала вы говорите, что используете общую формулу, зависящую от 7 параметров. Теперь вдруг то, что она проверяет условия для четверок с строках/столбцах. Если опираться на общую формулу, то такие проверки излишни, так как общая формула автоматически гарантирует выполнение этих условий (а проверять нужно лишь, получаются ли по ней остальные элементы из заданного набора). Так что же все-таки делает ваша программа?

[Nataly-Mak]

Ну да, конечно, формула гарантирует нужные суммы во всех строках, столбцах и главных диагоналях (и даже ещё в центральной четвёрке).

Наверное, я не совсем точно выразила свою мысль. Прошу прощения

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

(например: программа начинается перебором трёх свободных переменных $a1, a2, a3$, сразу вычисляем зависимый элемент $x1$ по формуле
S - a1 - a2 - a3
и проверяем принадлежность вычисленного элемента заданному массиву.
Так, из всех комбинаций первых трёх свободных элементов останутся только те варианты, при которых элемент $x1$ принадлежит заданному массиву)

Напишите программу по этой формуле! Сами убедитесь

[Nataly-Mak]

maxal
каков же результат?
Вы убедились в эффективности процедуры проверки, основанной на моей формуле?

Далее по поводу быстроты перебора. Когда я составила общую формулу для идеальных квадратов 5-го порядка, которая зависит всего от 8 параметров, которые надо выбирать из 24 возможных значений, мной был задан здесь вопрос: реально ли выполнить такую программу?
ice00 сразу дал ответ на мой вопрос (поднимитесь по этой ветке, вы найдёте этот ответ). Он написал, что для выполнения такой программы понадобится несколько минут (не помню точно, сколько).

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

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

Теперь рассмотрим построение любого магического квадрата 5-го порядка из 25 заданных чисел.
В этом случае формула зависит от 14 параметров и все они должны принять 25 различных значений (равных числам заданного массива).

Реально ли выполнить такую программу?

Программа у меня тоже уже составлена и даже протестирована. Тестировала, искусственно задавая 6 элементов, потому что в полном объёме у меня программа, понятное дело, не выполняется быстро ("быстро" для меня означает, по крайней мере, в течение часа). Оставшиеся 8 свободных элементов благополучно варьируются (пробегая все 25 значений) и программа за несколько минут выполняется и выдаёт результаты.

Всё это подробно описано в моей статье "Общие формулы магических квадратов".

Кстати, по этой программе можно повторить опыт американцев, построивших в 1972 г. все традиционные магические квадраты 5-го порядка.
Было бы интересно сравнить время, затраченное на такое построение, современным компьютером, со временем, затраченным американцами. Как пишет Гарднер в своей книге, они затратили на выполнение программы 100 часов машинного времени. Потом ещё несколько месяцев обрабатывали результаты, выданные ЭВМ.

Можно ведь составить и другие программы (по другим алгоритмам). Второй алгоритм приведён мной в указанной статье.

У 12d3 свой алгоритм (уже третий). Как он сообщал, по его программе тоже строятся все квадраты из заданного массива чисел.

[Nataly-Mak]

Сейчас посмотрела OEIS.

maxal
поскольку вы зам. главного редактора Энциклопедии, позвольте задать вам вопросы.

Часть вопросов, касающихся последовательностей А164843 и А073502, отправила вам в личку.

Появилась последовательность из магических констант наименьших квадратов из произвольных смитов - А170928, заявленная мной недавно.
В этой статье необходимо указать, что квадраты порядков 10 - 35 найдены мной и S. Tognon (потому что квадрат порядка 10 построен с использованием двух программ - моей и ice00, а квадраты порядков 11 - 35 построены мной по программам ice00). Я писала об этом ice00.

Ещё: почему в этой статье не работает ни одна ссылка?

Далее, увидела последовательность А104157, но так и не смогла понять, что это за последовательность. Это вообще относится к магическим квадратам или нет? Поняла, что она относится к простым числам. Если она имеет отношение также к магическим квадратам (что вообще-то, скорее всего, так, потому что есть ссылка на таблицу S. Tognon о квадратах из простых чисел), то почему в статье нет ни одного примера магического квадрата? Или хотя бы ссылки на такой квадрат. Может быть, я просто не увидела такую ссылку
Тогда скажите, пожалуйста, где посмотреть примеры таких квадратов.
И что это за квадраты? Как именно они строятся из простых чисел?

Ага, кажется, поняла, что за последовательность А104157
Это последовательность из минимальных чисел в магических квадратах из последовательных простых чисел.
Правильно?
А разве эти минимальные числа нельзя увидеть в магических квадратах последовательности А073520?

Кстати, в последовательности А073520 приведены константы до порядка 35 включительно, а в последовательности А104157 приведены минимальные числа квадратов до порядка 63 включительно.
Значит, все эти квадраты из последовательных простых чисел (для порядков 36 - 63) уже построены? Почему тогда нет в последовательности А073520 магических констант этих квадратов?

Это тоже непонятно.

[maxal]

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

Вы убедились в эффективности процедуры проверки, основанной на моей формуле?

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

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

Когда я составила общую формулу для идеальных квадратов 5-го порядка, которая зависит всего от 8 параметров, которые надо выбирать из 24 возможных значений, мной был задан здесь вопрос: реально ли выполнить такую программу?

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

Теперь рассмотрим построение любого магического квадрата 5-го порядка из 25 заданных чисел.
В этом случае формула зависит от 14 параметров и все они должны принять 25 различных значений (равных числам заданного массива).
Реально ли выполнить такую программу?

Сравните: в первом случае число вариантов (без учета оптимизации перебора) равно количеству размещений из 25 по 8, т.е. $43609104000 \approx 2^{35}$, а во втором - количеству размещений из 25 по 14, т.е. $388588515194880000\approx 2^{58}$ вариантов.

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

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

Откуда у вас информация, что они все их построили? Подсчитали количество - это да, но подсчёт далеко не всегда осуществляется явным перечислением.
Их результат, кстати, представлен в последовательности A006052.

-- Tue Feb 09, 2010 02:58:06 --

Исправления в последовательности внесу на этой неделе.

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

Ага, кажется, поняла, что за последовательность А104157
Это последовательность из минимальных чисел в магических квадратах из последовательных простых чисел.
Правильно?
А разве эти минимальные числа нельзя увидеть в магических квадратах последовательности А073520?

Можно, но это не запрещает A073520 существовать как самостоятельной последовательности.
(кстати, буква A в идентификторах последовательностей - латинская, вы же почему-то везде ставите русскую, в результате найти последовательности по вашим идентификаторам проблематично.)

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

Кстати, в последовательности А073520 приведены константы до порядка 35 включительно, а в последовательности А104157 приведены минимальные числа квадратов до порядка 63 включительно.
Значит, все эти квадраты из последовательных простых чисел (для порядков 36 - 63) уже построены? Почему тогда нет в последовательности А073520 магических констант этих квадратов?

Да, построены - см. страницу Стефано: http://digilander.libero.it/ice00/magic ... stant.html
А нет их потому, что последовательности в OEIS обычно ограничиваются тремя строками по ~70 символов. Обе обсуждаемые последовательности в этом смысле заполнены под завязку, просто магические константы занимают больше места и поэтому содежат меньше членов.
Кроме того, от большего количества членов ни там, ни там нет особого прока - начиная с 5-го порядка, они прекрасно вписываются в недоказанные, но очень правдоподобные формулы (указазанные в этих последовательностях в качестве гипотез).

[Nataly-Mak]

А! Вам нужна более эффективная процедура.
Но, может быть, эффективнее предложенной мной и нет?
Хорошо, когда найдёте более эффективную, сообщите.

Насчёт количества вариантов - чего зря стараться их считать. Вы и про перебор 7 параметров из 16 говорили, что это очень много. Однако программа выполняется за минуты (на Бейсике) и за доли секунды на нормальном языке.
От общего количества вариантов в данном случае зависит далеко не всё.
И я подозреваю, что если реально перебрать 8 параметоров из 24 всего за несколько минут, то реально также перебрать 14 параметров из 25. Ну пусть это будут не доли секунды, а несколько минут. Впрочем, я ничего не утверждаю, я только спрашиваю.
Кроме того, есть более эффективный алгоритм, чем общая формула, зависящая от 14 параметров.

Теперь о квадратах 5-го порядка. Вот цитата из книги Гарднера "Путешествие во времени":

"Точное число квадратов порядка 5 не было известно до 1973 г., когда полный перебор магических квадратов был осуществлён компьютерной программой, разработанной Р. Шрёппелем, математиком и программистом из “Information International”. Прогон программы на компьютере занимает около 100 часов машинного времени. Окончательное сообщение, написанное М. Билером, появилось в октябре 1975 г. С точностью до поворотов и отражений существует 275 305 224 магических квадратов порядка 5”.

Что по-вашему означает "полный перебор магических квадратов"? Это как же можно было их все перебрать без точного представления каждого квадрата? Я что-то не понимаю. То есть они посчитали, сколько существует таких квадратов, но каждый квадрат они не строили. Так что ли?

По поводу последовательностей не всё понятно.

(Ваше замечание о том, как я пишу имя последовательности, не принимается. Я же не ссылку пишу, а просто имя. И уж вам ли писать, что проблематично найти последовательность по её имени?)

Последовательность А073520 создана раньше последовательности А104157? Я правильно понимаю?

Цитата:

Можно, но это не запрещает A073520 существовать как самостоятельной последовательности.

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

Цитата:

Кроме того, от большего количества членов ни там, ни там нет особого прока - начиная с 5-го порядка, они прекрасно вписываются в недоказанные, но очень правдоподобные формулы (указазанные в этих последовательностях в качестве гипотез).

А тут вообще ничего не поняла. В последовательности А073520 каждый член есть магическая константа наименьшего квадрата из последовательных простых чисел, который реально существует (все эти квадраты построил ice00, насколько мне известно). Или вы хотите сказать, что у вас есть сомнения в том, что эти квадраты действительно являются наименьшими (и только до порядка 5 вы в этом уверены)?

От чего нет прока? Какие формулы не доказаны? Нельзя ли объяснить подробнее?

Если существует ограничение на запись последовательности, то где-то должно быть указано общее количество найденных членов последовательности. Это указано в последовательности А073520?