2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 77, 78, 79, 80, 81, 82, 83 ... 192  След.
 
 Re: Магические квадраты
Сообщение09.02.2010, 13:09 
Модератор
Аватара пользователя


11/01/06
5660
Nataly-Mak в сообщении #286677 писал(а):
Формула определения потенциального массива не имеет ничего общего с доказательством существования/несуществования самого квадрата. Она даёт только необходимые для построения таких квадратов массивы.

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

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение09.02.2010, 13:20 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение09.02.2010, 20:13 
Модератор
Аватара пользователя


11/01/06
5660
Nataly-Mak в сообщении #286680 писал(а):
И кому же принадлежит такая гипотеза?

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

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

Nataly-Mak в сообщении #286680 писал(а):
Для порядков до 63 включительно такие квадраты просто построены. Для бОльших порядков их уже сложнее построить.

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

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

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение10.02.2010, 08:08 
Заблокирован
Аватара пользователя


22/03/08

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

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

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

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

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

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение11.02.2010, 02:18 
Модератор
Аватара пользователя


11/01/06
5660
Nataly-Mak в сообщении #286860 писал(а):
Что означает: "множество достаточно плотное"? Множество чисел Смита относится к таковым?

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

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение11.02.2010, 12:01 
Заблокирован
Аватара пользователя


22/03/08

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

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение11.02.2010, 15:05 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение11.02.2010, 16:34 
Заблокирован
Аватара пользователя


22/03/08

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

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение11.02.2010, 16:50 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение11.02.2010, 18:08 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
То есть квадрат 4х4 не найден в том интервале, в котором найден квадрат 3х3?

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение11.02.2010, 18:22 
Модератор
Аватара пользователя


11/01/06
5660
Nataly-Mak
А что мои слова можно понять как-то по-другому? Перечитайте еще раз сказанное ранее и не задавайте тривиальных вопросов.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение11.02.2010, 20:45 
Аватара пользователя


20/01/10
766
Нижний Новгород
Может заинтересует?
http://svb-sokoban.narod.ru/DOWN/magic.rar
Специально для Наталии: паскалевский вариант её генератора 5х5
и минимальный инструмент для компиляции.

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение11.02.2010, 20:57 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
svb в сообщении #287244 писал(а):
Может заинтересует?
http://svb-sokoban.narod.ru/DOWN/magic.rar
Специально для Наталии: паскалевский вариант её генератора 5х5
и минимальный инструмент для компиляции.


Большое спасибо!
Завтра попробую разобраться.
Вы какой алгоритм использовали?

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение11.02.2010, 22:53 
Аватара пользователя


20/01/10
766
Нижний Новгород
Nataly-Mak писал(а):
Вы какой алгоритм использовали?

У меня в тексте программ указано:Алгоритм программы взят из текста на языке BASIC, который приведен в статье Н.Макаровой "Общие формулы магических квадратов".

Кстати, ортогональный базис пандиагональных квадратов 5х5 (плюс матрица из одних 1):
Код:
-1  1  0  0  0    0  0  0  1 -1   -1  0  1  0  0    0  0  1  0 -1
0  0 -1  1  0    0  1 -1  0  0    1  0  0 -1  0    0 -1  0  0  1
1  0  0  0 -1   -1  0  0  0  1    0 -1  0  1  0    0  1  0 -1  0
0 -1  1  0  0    0  0  1 -1  0    0  1  0  0 -1   -1  0  0  1  0
0  0  0 -1  1    1 -1  0  0  0    0  0 -1  0  1    1  0 -1  0  0
       a                b                c                d

-a-c   a   c+d   b  -b-d
  c   b-d -a-b  a-c   d
a-b -c+d   0   c-d -a+b
-d  -a+c  a+b -b+d  -c
b+d  -b  -c-d  -a   a+c

 Профиль  
                  
 
 Re: Магические квадраты
Сообщение12.02.2010, 07:03 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Цитата:
Кстати, ортогональный базис пандиагональных квадратов 5х5 (плюс матрица из одних 1)


Очень интересная формула!

Я пока ничего не смотрела из выложенного вами материала и даже ещё не скачала.
Не хотите ли вы сами поискать наименьший магический квадрат 5х5 из последовательных чисел Смита по своей программе?

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

Скажите, а за сколько времени ваша программа проверяет один потенциальный массив из 25 чисел?

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2871 ]  На страницу Пред.  1 ... 77, 78, 79, 80, 81, 82, 83 ... 192  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group