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

[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$ такого квадрата не существует?

[maxal]

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

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

Гипотеза состоит в том, что формула является и достаточным условием для существования квадратов всех порядков, начиная с 5.
Именно это хотелось бы доказать.

[Nataly-Mak]

Уф! Ну, наконец-то вы сформулировали гипотезу.
И кому же принадлежит такая гипотеза?

По-моему, доказать эту гипотезу невозможно.

Для порядков до 63 включительно такие квадраты просто построены. Для бОльших порядков их уже сложнее построить.

А как вы мыслите себе доказательство существования или несуществования магического квадрата любого порядка $n$ из первого потенциального массива, подобранного по указанной формуле?

[maxal]

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

И кому же принадлежит такая гипотеза?

Если вас это так волнует - считайте, что мне (хотя может кто-то и раньше высказывал).

Я думаю, справедливо даже более общее утверждение: если дано достаточно плотное множество из $n^2$ чисел (множество последовательных простых относится к таковым), что их сумма делится на $n$, и нету препятствий к существованию квадрата по модулю маленьких простых чисел (как, например, по модулю 2 если все данные числа нечетные), то магический квадрат из данных чисел существует.

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

Для порядков до 63 включительно такие квадраты просто построены. Для бОльших порядков их уже сложнее построить.

А как вы мыслите себе доказательство существования или несуществования магического квадрата любого порядка $n$ из первого потенциального массива, подобранного по указанной формуле?

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

[Nataly-Mak]

Цитата:

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

Что означает: "множество достаточно плотное"? Множество чисел Смита относится к таковым?

Эвристическое наблюдение ice00 означает просто: если данный массив чисел имеет достаточное количество разбиений на группы размером, равным размеру квадрата, с суммой чисел в каждой группе равной магической константе квадрата, то вероятность существования магического квадрата из чисел такого массива достаточно высока. Это ясно без всяких эвристик.

Все мои программы, по которым я строила магические квадраты из простых чисел, основаны именно на этом утверждении. И начинала я каждый раз с разбиения исходного массива на такие группы чисел, дающие магическую константу квадрата. И если таких групп оказывалось очень мало, то такой массив чисел сразу отвергался.
Как вы сами тут недавно заметили: исходный массив из 16 чисел только в том случае способен сложиться в магический квадрат, если в нём есть как минимум 10 четвёрок, дающих в сумме магическую константу квадрата.
Это необходимое условие построения магического квадрата, но не достаточное.

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

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

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

Работая с квадратами из смитов порядков 7 - 9, я имею все необходимые условия, и разбиений на группы имею достаточно много; и получаю очень много полумагических квадратов, однако две последние группы чисел (на главных диагоналях) никак не складываются.

А вот начиная с порядка 11 (до порядка 50 включительно) все квадраты из последовательных чисел Смита построились без проблем. Но где уверенность в том, что первый потенциальный массив из последовательных смитов для порядка $n = 1000$ тоже сложится в магический квадрат? Какие числа окажутся в этом массиве? Как они будут складываться в группы по 1000 чисел, дающие в сумме потенциальную магическую константу? Сколько будет таких групп? Как доказать, что их будет достаточно много?

Как я уже отмечала, построение квадрата 6-го порядка из последовательных смитов из первого же кандидата кажется просто чудом. Потому что квадраты 3 - 5 порядков уходят в астрономические числа.

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

[maxal]

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

Что означает: "множество достаточно плотное"? Множество чисел Смита относится к таковым?

Можно считать, что плотность множества чисел - это примерно отношение их количества к длине интервала, в котором они лежат (т.е. $\frac{n}{M-m+1}$, где $n$ - количество элементов во множества, а $M$ и $m$ - это соответственно его максимальный и минимальный элементы). Смиты, вообще говоря, не обладают такой регулярность как простые числа, поэтому сказать о плотности их множества априори что-либо тяжело.

[Nataly-Mak]

Скажите, те 28 наборов по 16 последовательных смитов, что приведены вами выше, это все кандидаты в квадрат 4-го порядка из последовательных смитов?
Других не было (со всеми накладываемыми вами условиями)?

[maxal]

Nataly-Mak
В интервале до $10^{12}$ - все. См. post285459.html#p285459

[Nataly-Mak]

Вы исчерпали весь свой массив смитов в поиске кандидатов в квадрат 4х4?

[maxal]

Nataly-Mak
У меня нет никакого массива. Смиты генерируются на лету. Просто $10^{12}$ - это та граница, до которой я осуществлял поиск.