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

[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?

[maxal]

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

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

Нет, "полный перебор" скорее означает именно перебор всех. Вот здесь http://gaspalou.fr/magic-squares/order-5.htm говорится о воспроизведении этого подсчета - в 1997 году он занял 6 часов:
In September 1997, I drove such an enumeration in 6 hours and half with a reduced program (group G of order 32 and permutation "complement to 26") on a K6 of AMD, running at 200 MHz, under Turbo Pascal. I found the well known total of 2 202 441 792 squares.

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

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

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

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

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

Ну во-первых, не так уж легко (хотя и можно), а во-вторых, в OEIS существует множество родственных последовательностей - гораздо даже более близких чем A104157 и A073520.

-- Tue Feb 09, 2010 03:57:33 --

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

Или вы хотите сказать, что у вас есть сомнения в том, что эти квадраты действительно являются наименьшими (и только до порядка 5 вы в этом уверены)?

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

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

А формулы вот эти:

%F A104157 Conjecture: for n>4, a(n)=prime(s) where s>1 is the smallest integer such that (Sum[i=s..s+n^2-1] prime(i))/n is an integer of the same evenness as n.

%F A073520 Conjecture: for n>=5, a(n) equals the smallest integer of the form (A000040(s+1)+...+A000040(s+n^2))/n = (A007504(s+n^2)-A007504(s))/n of the same oddness as n.

A000040 - это последовательность простых чисел (то есть A000040(k)=prime(k) представляют собой k-е простое число).

[Nataly-Mak]

Теперь я вас перестаю понимать.

Давайте ещё раз (приведённые вами формулы я не понимаю...).

Существует формула, по которой определяются потенциальные кандидаты в магический квадрат порядка $n$ из последовательных простых чисел. Эта формула очень проста: берутся подряд n^2 простых чисел, определяется их сумма и проверяется, кратна ли эта сумма $n$. Ещё должно выполняться условие: потенциальная магическая константа квадрата должна иметь ту же чётность, что и порядок квадрата.

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

Вы об этом говорите или о чём-то другом?

О традиционных квадратах 5-го порядка тоже ничего не понимаю: что значит "перебор всех"? Так их (сами квадраты) построили или не построили? Или только каким-то образом "перебрали", то есть посчитали?

Ну, вот, уже в 1997 году понадобилось всего 6 часов. А сейчас понадобится ещё меньше, вполне возможно, что программа выполнится всего за пару часов.
Если её хорошо написать

[maxal]

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

Существует формула, по которой определяются потенциальные кандидаты в магический квадрат порядка $n$ из последовательных простых чисел. Эта формула очень проста: берутся подряд n^2 простых чисел, определяется их сумма и проверяется, кратна ли эта сумма $n$. Ещё должно выполняться условие: потенциальная магическая константа квадрата должна иметь ту же чётность, что и порядок квадрата.

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

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

А значит и доказывать уже нечего! Меньшего квадрата просто быть уже не может, раз это первый кандидат в такой квадрат.

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

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

О традиционных квадратах 5-го порядка тоже ничего не понимаю: что значит "перебор всех"? Так их (сами квадраты) построили или не построили?

Насколько я могу судить по приведенной цитате, построили.

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

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

Вполне возможно.

[Nataly-Mak]

Цитата:

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

Ну, так значит, все реально построенные квадраты как раз имеют свою ценность!

А вы говорите, что нет никакого проку их все приводить. Логики не усматриваю

[maxal]

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

Ну, так значит, все реально построенные квадраты как раз имеют свою ценность!

Они в каком-то смысле ожидаемы и предсказуемы (по формулам). Вот если бы как-то удалось опровегнуть формулу, то ценность была бы куда больше.

[Nataly-Mak]

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

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

Ну, так значит, все реально построенные квадраты как раз имеют свою ценность!

Они в каком-то смысле ожидаемы и предсказуемы (по формулам). Вот если бы как-то удалось опровегнуть формулу, то ценность была бы куда больше.

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

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

Вы хотите сказать, что надо доказать само существование магического квадрата любого порядка $n$ из последовательных простых чисел (или доказать, что для какого-то порядка $n$ такого квадрата не существует?