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

[Garik2]

Новые числа запустил в 13:30. Это для того, чтобы знать, сколько будет пахать во благо и во имя. Скорость примерно в 5 раз ниже.

[svb]

Маленький вопрос. Если рассматривать пространство пандиагональных квадратов порядка $N$ с нулевой магической суммой, то желательно знать его размерность или, что то же самое, число независимых параметров. На $N^2$ величин мы накладываем $4*(N-1)$ линейных соотношений (равенство соответствующих сумм сумме первой строки) и еще одно соотношение, требующее нулевую магическую сумму. Таким образом получается искомая размерность $N^2-4*(N-1)-1=(N-1)*(N-3)$. Но это только при условии линейной независимости накладываемых соотношений. Например при $N=4$ мы получим размерность 3, но на самом деле эта размерность равна 4, вот ортогональный базис этого пространства:
$\left( {\begin{array}{*{20}c} 1 & { - 1} & 1 & { - 1} \\ { - 1} & 1 & { - 1} & 1 \\ { - 1} & 1 & { - 1} & 1 \\ 1 & { - 1} & 1 & { - 1} \\ \end{array}} \right)$, $\left( {\begin{array}{*{20}c} 1 & { - 1} & { - 1} & 1 \\ { - 1} & 1 & 1 & { - 1} \\ 1 & { - 1} & { - 1} & 1 \\ { - 1} & 1 & 1 & { - 1} \\ \end{array}} \right)$, $\left( {\begin{array}{*{20}c} 1 & 0 & 0 & { - 1} \\ 0 & { - 1} & 1 & 0 \\ 0 & 1 & { - 1} & 0 \\ { - 1} & 0 & 0 & 1 \\ \end{array}} \right)$, $\left( {\begin{array}{*{20}c} 0 & 1 & { - 1} & 0 \\ { - 1} & 0 & 0 & 1 \\ 1 & 0 & 0 & { - 1} \\ 0 & { - 1} & 1 & 0 \\ \end{array}} \right)$
Я искренне был уверен, что это досадное исключение для маленькой размерности. Каково же было мое удивление, когда для $N=6$ обнаружилось нечто подобное. Более того, скорее всего для всех четных $N$ происходит то же самое.

А ваше мнение?

[maxal]

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

maxal
как быстро ваша программа выдаёт пандиагональный квадрат из этого набора чисел? (квадрат показан чуть выше, я проверяла на нём общую формулу)

Переписал на C++. За ночь квадрат нашла - вот такой:

167 233 223 127 173 193 
131 157 137 107 197 109 
79 139 89 67 73 199 
241 229 251 181 211 101 
239 227 149 163 103 151 
71 113 83 97 191 179

-- Fri Aug 20, 2010 08:47:49 --

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

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

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.

Таких наборов несколько:

[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, 157, 197]
[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]
[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, 173, 181]
[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, 151, 173, 179]
[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, 157, 167, 179]
[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, 163, 167, 173]
[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, 149, 151, 163, 179]
[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, 149, 157, 163, 173]
[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, 139, 149, 151, 167, 173]
[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, 131, 137, 139, 149, 151, 157, 173]
[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, 131, 137, 139, 149, 151, 163, 167]

Поэтому имеет смысл строить квадрат из их объединения (содержащего 43 элемента):

[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, 151, 157, 163, 167, 173, 179, 181, 191, 197]

-- Fri Aug 20, 2010 09:18:55 --

svb в сообщении #345713 писал(а):

На $N^2$ величин мы накладываем $4*(N-1)$ линейных соотношений (равенство соответствующих сумм сумме первой строки)

Линейно независимых соотношений среди них не больше $(N-1)+3(N-2)=4N-7$.

[Nataly-Mak]

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

Переписал на C++. За ночь квадрат нашла - вот такой

Да, С++ имеет отличное быстродействие.

Цитата:

Поэтому имеет смысл строить квадрат из их объединения (содержащего 43 элемента):

Хорошая идея. Но в этом случае переменные будут пробегать не 36 значений, а 43, что намного увеличит время выполнения программы (в разы). Не выгоднее ли проверить каждый массив отдельно?

Я начала писать программу, которая составит пандиагональный квадрат из элементов: 3, 1, 5. Мне кажется, в этом методе что-то должно получиться. Если составить такой квадрат из этих трёх элементов, тогда по этому образцу можно пытаться расположить сами числа (тоже, конечно, по программе). Я уже писала подобную программу размещения чисел по образцу из вычетов, когда 12d3 высказал эту идею для квадратов 7-го порядка (только он находил образец из вычетов по модулю 9).

[Garik2]

А на сколько это сократит количество циклов? Сколько циклов будет в итоге?
Прога Ваша пашет уже 8 часов. Результат пока что нулевой. Вдруг за ночь наткнется на решение?
Средняя скорость видимого на экране цикла 10 сек.

[Nataly-Mak]

Вот они шаблончики пандиагональных квдаратов 6-го порядка из простых чисел:

1  1  3  1  1  5 
 5  1  5  5  1  1 
 5  1  5  1  5  1 
 5  5  5  5  5  5 
 1  5  1  1  5  5 
 1  5  5  5  1  1 

 1  1  3  1  1  5 
 1  5  5  1  5  1 
 5  1  5  1  5  1 
 5  5  5  5  5  5 
 5  1  1  5  1  5 
 1  5  5  5  1  1 

 1  1  3  1  1  5 
 1  5  5  5  1  1 
 5  1  1  5  1  5 
 5  5  5  5  5  5 
 5  1  5  1  5  1 
 1  5  5  1  5  1 

 1  1  3  1  1  5 
 1  5  5  5  1  1 
 1  5  1  1  5  5 
 5  5  5  5  5  5 
 5  1  5  1  5  1 
 5  1  5  5  1  1 

 1  5  3  5  5  5 
 1  5  1  5  1  5 
 5  1  1  1  5  5 
 5  1  5  1  1  5 
 1  1  1  5  5  5 
 5  5  1  1  1  5 

 1  1  3  1  5  1 
 5  5  5  1  1  1 
 1  1  5  5  5  1 
 5  5  1  5  1  1 
 1  5  5  5  1  1 
 5  1  5  1  5  1 

 1  5  3  5  5  5 
 5  5  1  1  1  5 
 1  1  1  5  5  5 
 5  1  5  1  1  5 
 5  1  1  1  5  5 
 1  5  1  5  1  5 

 1  1  3  1  5  1 
 5  1  5  1  5  1 
 1  5  5  5  1  1 
 5  5  1  5  1  1 
 1  1  5  5  5  1 
 5  5  5  1  1  1

Это для случая, когда используется число 3.

На изоморфность не проверила. Очень обрадовалась появлению шаблончиков на экране, поспешила сделать сообщение

Посчитала количество элементов 1 и 5 в шаблонах, в шести шаблонах 1 - 16 штук, 5 - 19 штук, а в двух шаблонах наоборот: 1 - 19 штук, 5 - 16 штук.

Теперь попытаюсь строить квадраты по шаблонам.

Pavlovsky
вы раскопали замечательное свойство простых чисел, что все они имеют только два представления (кроме чисел 2 и 3): 6k - 1 или 6k + 1. Это позволило получить хорошие шаблоны.

svb
вам это хорошо знакомо. Подключайтесь!

Garik2
это принципиально новый алгоритм, и здесь уже не стоит считать циклы.
Берём шаблон и пытаемся разместить в нём заданные числа в соответствии с вычетами по модулю 6. Приглашаю и вас поупражняться

[Nataly-Mak]

Запустила программу построения шаблонов для случая, когда число 3 не используется. Программа выдала 18 шаблонов. Вот, например, два:

 № 7
1  1  1  1  1  1 
 5  5  5  5  5  5 
 5  5  5  5  5  5 
 5  5  5  5  5  5 
 1  1  1  1  1  1 
 1  1  1  1  1  1 

№ 8
 1  5  1  5  1  5 
 5  1  5  1  5  1 
 1  5  1  5  1  5 
 5  1  5  1  5  1 
 1  5  1  5  1  5 
 5  1  5  1  5  1

Интересно, что элементы 1 и 5 используются в равных количествах.

[maxal]

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

Запустила программу построения шаблонов для случая, когда число 3 не используется. Программа выдала 18 шаблонов.
...
Интересно, что элементы 1 и 5 используются в равных количествах.

Их гораздо больше, и не везде количества 1 и 5 совпадают. Например, есть квадрат из одних только единиц.

-- Sat Aug 21, 2010 01:00:07 --

Если нигде не наврал, пандиагональных квадратов 6x6 из простых с суммами всех элементов 2628, 2700 и 2772 не существует.

[Nataly-Mak]

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

Их гораздо больше, и не везде количества 1 и 5 совпадают. Например, есть квадрат из одних только единиц.

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

Вот приведу все шаблоны:

(Оффтоп)

1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

1 1 1 1 1 1
5 5 5 5 5 5
5 1 5 1 5 1
1 1 1 1 1 1
1 5 1 5 1 5
5 5 5 5 5 5

1 5 1 5 1 5
1 1 1 1 1 1
5 1 5 1 5 1
5 5 5 5 5 5
1 1 1 1 1 1
5 5 5 5 5 5

1 5 1 5 1 5
5 5 5 5 5 5
5 1 5 1 5 1
1 1 1 1 1 1
5 5 5 5 5 5
1 1 1 1 1 1

1 1 1 1 1 1
5 5 5 5 5 5
1 1 1 1 1 1
1 5 1 5 1 5
5 5 5 5 5 5
5 1 5 1 5 1

1 1 1 1 1 1
5 5 5 5 5 5
1 1 1 1 1 1
5 1 5 1 5 1
5 5 5 5 5 5
1 5 1 5 1 5

1 1 1 1 1 1
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
1 1 1 1 1 1
1 1 1 1 1 1

1 5 1 5 1 5
5 1 5 1 5 1
1 5 1 5 1 5
5 1 5 1 5 1
1 5 1 5 1 5
5 1 5 1 5 1

1 5 1 5 1 5
1 5 1 5 1 5
1 5 1 5 1 5
1 5 1 5 1 5
1 5 1 5 1 5
1 5 1 5 1 5

1 1 1 1 1 1
1 5 1 5 1 5
5 5 5 5 5 5
1 1 1 1 1 1
5 5 5 5 5 5
5 1 5 1 5 1

1 1 1 1 1 1
5 1 5 1 5 1
5 5 5 5 5 5
1 1 1 1 1 1
5 5 5 5 5 5
1 5 1 5 1 5

1 1 1 1 1 1
5 5 5 5 5 5
1 5 1 5 1 5
1 1 1 1 1 1
5 1 5 1 5 1
5 5 5 5 5 5

1 5 1 1 5 5
1 5 5 1 1 5
1 5 1 1 5 5
1 5 5 1 1 5
1 5 1 1 5 5
1 5 5 1 1 5

1 5 1 5 5 1
5 5 1 5 1 1
1 5 1 5 5 1
5 5 1 5 1 1
1 5 1 5 5 1
5 5 1 5 1 1

1 1 5 5 1 5
5 1 1 5 1 5
1 1 5 5 1 5
5 1 1 5 1 5
1 1 5 5 1 5
5 1 1 5 1 5

1 5 5 1 1 5
1 5 1 1 5 5
1 5 5 1 1 5
1 5 1 1 5 5
1 5 5 1 1 5
1 5 1 1 5 5

1 1 5 1 5 5
5 1 5 1 1 5
1 1 5 1 5 5
5 1 5 1 1 5
1 1 5 1 5 5
5 1 5 1 1 5

1 5 5 1 5 1
5 5 1 1 5 1
1 5 5 1 5 1
5 5 1 1 5 1
1 5 5 1 5 1
5 5 1 1 5 1

Какие шаблоны я потеряла?

А с использованием числа 3 у вас сколько шаблонов получается? У меня всего 8 штук. Я их все показала.

Цитата:

Если нигде не наврал, пандиагональных квадратов 6x6 из простых с суммами всех элементов 2628, 2700 и 2772 не существует.

А как вы проверили?
____
Да, похоже я что-то наврала в программе. Почему у меня, например, нет квадрата из один пятёрок?
Он ведь тоже будет пандиагональный.

А такая мысль пришла в голову: поскольку элементы 1 и 5 равноправно участвуют в построении квадрата, то можно в любом шаблоне заменить 1 на 5 и 5 на 1.
Это правильная мысль?
Тогда квадрат из всех пятёрок получится из квадрата из всех единиц.

Garik2
останавливайте программу для массива с магической константой 438. maxal доказал, что пандиагонального квадрата с такой магической константой не существует.
Теперь надо проверять для магической константы 474. А у меня ещё массив не сформирован для этой константы. Осталось проверить всего 7 магических констант!

[Nataly-Mak]

Конечно, констант осталось проверить 13, а не 7
Это они у меня выписаны на листе бумаги, одна строка заканчивается константой 546, а продолжение во второй строке, вот я только в первой строке и посчитала константы.

Массив, дающий константу 474, моя программа не захотела формировать с числом 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  151  181  193  197

Возможно, есть и другие массивы. Но я пока с одним поработаю. Итак, 18 единиц и 18 пятёрок надо разместить по какому-нибудь шаблону, то есть размещать надо сами числа, соответствующие вычетам 1 и 5.
Надо писать программу построения квадрата по шаблону.

[Nataly-Mak]

Выбрала шаблон № 13 (счастливое число ).
Написала программу для приведённого выше массива.
Долго думала, как же её лучше всего написать, ничего не придумала, как опять по общей формуле. Только теперь все свободные переменные разбились на две группы и поэтому каждая пробегает только 18 значений (а не 36, как в самой общей формуле). Но переменных всё так же 16.

Тем не менее программа должна выполняться намного быстрее: что 18 значений пробежать, а что 36. Значительный выигрыш!

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

97  53  7  0  5  0 
37  137  107  79  31  83 
109  11  127  13  197  17 
61  131  71  0  0  0 
19  101  103  181  47  23 
151  41  59  43  0  113

Всё, что здесь сложилось, хорошо сложилось, правильно. Но дальше уже туго дело идёт.

Массив подаёт надежды. Хотя ничего определённого пока нельзя сказать.

К тому же, шаблонов много. Если по этому шаблону не составится пандиагональный квадрат, то, может быть, по какому-то другому составится.
В общем, тут работы очень много.

А куда у меня помощники все подевались?

[Pavlovsky]

С шаблонами надо разбираться.
Скажем

1 1 1 1 1 1 
5 1 5 1 5 1 
5 5 5 5 5 5 
1 1 1 1 1 1 
5 5 5 5 5 5 
1 5 1 5 1 5 

1 1 1 1 1 1 
5 5 5 5 5 5 
1 5 1 5 1 5 
1 1 1 1 1 1 
5 1 5 1 5 1 
5 5 5 5 5 5 

Эти два шаблона получаются друг из друга переносом на торе.

[maxal]

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

А с использованием числа 3 у вас сколько шаблонов получается? У меня всего 8 штук.

У меня в 2 раза больше, только я рассматривал лишь по модулю 3 (по модулю 2 рассматривать не имеет смысла, так как там все всегда ok):

[1, 1, 2, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1, 0, 2, 2, 1, 2, 2]
[1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 0, 2, 2, 1, 2, 2]
[1, 1, 2, 2, 2, 1, 2, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 1, 0, 2, 2, 1, 2, 2]
[1, 1, 2, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 2, 1, 2, 0, 2, 2, 1, 2, 2]
[1, 2, 1, 2, 1, 2, 1, 1, 2, 2, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 2, 2, 2, 0, 2, 2, 2, 1, 2]
[1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 1, 1, 2, 1, 2, 1, 2, 0, 2, 2, 2, 1, 2]
[1, 2, 2, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 2, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 1, 2, 1, 2, 0, 2, 1, 2, 2, 2]
[1, 2, 1, 2, 1, 2, 1, 1, 2, 2, 2, 1, 2, 1, 2, 2, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 1, 1, 0, 2, 1, 2, 2, 2]
[2, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 2, 1, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 0, 1, 2, 1, 1, 1]
[2, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 2, 1, 1, 2, 2, 2, 2, 1, 1, 1, 2, 2, 1, 2, 1, 2, 1, 0, 1, 2, 1, 1, 1]
[2, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 2, 2, 1, 1, 1, 2, 2, 1, 2, 1, 2, 1, 0, 1, 1, 1, 2, 1]
[2, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 2, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 0, 1, 1, 1, 2, 1]
[2, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 0, 1, 1, 2, 1, 1]
[2, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 2, 0, 1, 1, 2, 1, 1]
[2, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 1, 2, 2, 2, 2, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 1, 2, 0, 1, 1, 2, 1, 1]
[2, 2, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 1, 2, 2, 2, 1, 1, 1, 2, 0, 1, 1, 2, 1, 1]

Соответственно: 1 - это ваша 1, 2 - это 5, 0 - это 3.

-- Sat Aug 21, 2010 08:10:54 --

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

А такая мысль пришла в голову: поскольку элементы 1 и 5 равноправно участвуют в построении квадрата, то можно в любом шаблоне заменить 1 на 5 и 5 на 1.
Это правильная мысль?
Тогда квадрат из всех пятёрок получится из квадрата из всех единиц.

Да, это соответствует умножению всего квадрата на -1.

[Nataly-Mak]

Пока у меня всё в тумане.

Pavlovsky
я отметила, что на изоморфность шаблоны не проверяла. Но коль скоро среди найденных мной 18 шаблонов есть изоморфные, тогда различных будет ещё меньше

Откуда же у maxal'а аж 86 различных шаблонов?

[maxal]

Шаблоны без 3-ки пока убираю, что-то процедура проверки на изоморфность барахлит. Отлажу - выложу результат.