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

[Nataly-Mak]

Ну, и я о том же

[svb]

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)$
не лежит в рассматриваемом подпространстве.

[Nataly-Mak]

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

[Pavlovsky]

Пусть у нас есть набор 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. Легко проверить, что такого разбиения не может быть.

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

[Garik2]

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

[Pavlovsky]

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

[maxal]

Pavlovsky в сообщении #345608 писал(а):

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

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

[Garik2]

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

[Nataly-Mak]

Garik2 в сообщении #345607 писал(а):

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

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

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

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

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

[Garik2]

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

[Nataly-Mak]

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

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

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

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

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

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

[Garik2]

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

[Nataly-Mak]

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

[Garik2]

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

[Nataly-Mak]

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

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.