2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 113, 114, 115, 116, 117, 118, 119 ... 192  След.
 
 Re: Магические квадраты
Сообщение20.08.2010, 05:07 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ну, и я о том же :-)

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


20/01/10
766
Нижний Новгород
Nataly-Mak в сообщении #345597 писал(а):
Так это и значит, что вы строите квадрат из комплементарных пар чисел! Правильно?
Так точно - я к этому не стремился :-( . Элемент
$\left( {\begin{array}{*{20}c}
   0 & 1 & { - 1} & 0 & 0 & 0  \\
   { - 1} & 0 & 0 & 1 & 0 & 0  \\
   1 & 0 & 0 & { - 1} & 0 & 0  \\
   0 & { - 1} & 1 & 0 & 0 & 0  \\
   0 & 0 & 0 & 0 & 0 & 0  \\
   0 & 0 & 0 & 0 & 0 & 0  \\
\end{array}} \right)$
не лежит в рассматриваемом подпространстве.

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


22/03/08

7154
Саратов
Но, может быть, программная реализация вашей формулы эффективнее моей. Моя программа только для одного набора (который я только что указала) отработала мгновенно - счастливый случай. Больше ни для одного набора мне не удалось выполнить программу до квадрата и тем более до конца.
12 свободных элементов из 36 - это тоже много. И лобовой перебор очень долог.
Я как-то спросила maxal'а, выяснил ли он возможность построения ассоциативного квадрата из комплементарных пар смитов с суммой 4400. Он ответил: "Пока нет, всё ещё вычисляет". Как я поняла, и у него программа построения ассоциативного квадрата работает очень долго.

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


21/02/10
1594
Екатеринбург
Пусть у нас есть набор 36 чисел и S сумма этих чисел.

0) Тогда, по теоремам 2.4 и 2.5 сумма S должна делиться на 36
1) По теореме 2.4, набор чисел можно разделить на 4 группы по 9 чисел с одинаковой суммой равной S/4.
2) По теореме 2.5, набор чисел можно разделить на 9 групп по 4 числа с одинаковой суммой равной S/9.
3) До кучи, набор можно разбить на 6 групп по 6 чисел с одинаковой суммой S/6.

Условия 1-3 проверить напрямую непросто, поэтому переходим к остаткам по числу k. Заменим все числа набора на остатки от деления на k. Тогда условия 1-3 можно сформулировать в следующем виде:

1) Набор остатков чисел по модулю k можно разделить на 4 группы по 9 чисел с одинаковой суммой по модулю k равной S/4 mod(k).
2) Набор остатков чисел по модулю k можно разделить на 9 групп по 4 числа с одинаковой суммой по модулю k равной S/9 mod(k).
3) Набор остатков чисел по модулю k можно разбить на 6 групп по 6 чисел с одинаковой суммой по модулю k S/6 mod(k).

Пример.
Код:
3   5   47   109   131   137
89   73   53   97   61   59
151   167   83   7   11   13
71   41   107   103   67   43
17   19   29   79   139   149
101   127   113   37   23   31

Сумма чисел равна 2592.
Проверяем условия для k=6. Набор остатков по модулю 6 состоит: 3 1шт; -1 19шт; 1 16шт

3) Набор остатков можно разбить на 6 групп по 6 чисел с суммой по модулю 432 mod(6)=0. Очевидно, это условие выполняется.

2) Набор остатков можно разбить на 9 групп по 4 числа с суммой по модулю 288 mod(6)=0. Очевидно, это условие выполняется.

1) Набор остатков можно разбить на 4 группы по 9 чисел с суммой по модулю 648 mod(6)=0. Легко проверить, что такого разбиения не может быть.

Делаем вывод. Из представленного набора построить пандиагональный МК невозможно.

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


03/08/09

235
Программа Nataly крутится уже 12 часов. И продолжает крутиться. Это при моей-то нехилой скорости...

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


21/02/10
1594
Екатеринбург
Из выше сказанного следует, необходимым условием построения пандиагонального МК 6х6 из заданного набора простых чисел является: сумма чисел деленная на 4 должна быть нечетным числом.

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


11/01/06
5669
Pavlovsky в сообщении #345608 писал(а):
Из выше сказанного следует, необходимым условием построения пандиагонального МК 6х6 из заданного набора простых чисел является: сумма чисел деленная на 4 должна быть нечетным числом.

Другими словами, количество простых вида $4k+1$ в наборе должно быть кратно 4-м.

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


03/08/09

235
Да... Дополнительные ограничения ускорили бы перебор вариантов.

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


22/03/08

7154
Саратов
Garik2 в сообщении #345607 писал(а):
Программа Nataly крутится уже 12 часов. И продолжает крутиться. Это при моей-то нехилой скорости...

Предлагаю вам остановить её. Она может крутиться ещё n раз по 12 часов, то есть неделю точно может крутиться :-)

Надо думать над эффективными алгоритмами.

-- Пт авг 20, 2010 10:23:00 --

Pavlovsky
спасибо за анализ. Очень хорошие критерии отбора вы получили. Это позволит выбрать хорошие потенциальные массивы для построения пандиагональных МК 6-го порядка.

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


03/08/09

235
Пусть крутится, пока вы коллективно ищите улучшение. А вдруг я раньше напорюсь на решение? :P

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


22/03/08

7154
Саратов
Так ведь ваше решение будет неинтересным решением, потому что вы запустили программу для тестируемого массива чисел, из чисел которого пандиагональный квадрат точно существует (и один такой квадрат уже известен) :-)
Если вы получите решение, то просто установите, за сколько времени программа "вырулила" на решение.

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

Pavlovsky
воспользовалась вашими критериями и проверила массивы с магическими константами в интервале [434,630).
Необходимым условиям удовлетворяют только следующие массивы (указаны магические константы):

Код:
438 450 462 474 486 498 510 522 534 546 558 570 582 594 606 618

Вот как резко сократилось количество потенциальных массивов. Теперь осталось проверить всего 16 массивов.

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

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


03/08/09

235
Так напишите, что мне нужно вставить в MK3

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


22/03/08

7154
Саратов
Вот я как раз только что написала, что сейчас займусь формированием потенциальных массивов. Пока установила, какие возможны магические константы.

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


03/08/09

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

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


22/03/08

7154
Саратов
Вот первый потенциальный массив простых чисел:

Код:
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 163 191

сумма всех чисел массива равна 2628. Массив даёт МК с магической константой 438.
Обычный МК из этих чисел строится сразу (воспользовалась программой ice00):

Код:
ORDER=6  MAGIC=438

107 97  31  149 13  41 
11  163 37  23  101 103
139 5   19  89  59  127
43  53  131 3   191 17 
109 47  83  61  67  71 
29  73  137 113 7  79

Сумма чисел массива делится на 36. Сумма чисел массива делённая на 4 есть число нечётное (2628/4 = 657).
Правильно я проверила необходимые условия?

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

Garik2
массив удовлетворяет необходимым условиям; это не означает, что пандиагональный квадрат из чисел данного массива обязательно построится. Вот здесь и нужна эффективная "проверялка", которой у нас пока нет.

maxal
ваше условие тоже выполняется: количество чисел вида 4k + 1 в этом массиве равно 16.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2871 ]  На страницу Пред.  1 ... 113, 114, 115, 116, 117, 118, 119 ... 192  След.

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



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

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


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

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