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

[Nataly-Mak]

Вообще в нетрадиционном магическом квадрате (по определению) разрешается повторение чисел.
Но мы строим МК с наложенным ограничением: все числа должны быть различные.

Видимо, svb просто недоглядел. Но в квадрате с магической константой 594 одинаковых чисел нет. Я его сразу же проверила.

У меня, например, во всех программах построения МК есть проверка чисел на повторение.

[svb]

Someone в сообщении #346173 писал(а):

Это так и должно быть, что некоторые числа повторяются?

Нет, это моя ошибка

[Nataly-Mak]

Решила посмотреть, какие шаблоны соответствуют двум известным пандиагональным квадратам из смитов. Один из них показан чуть выше, второй идеальный (тоже найден maxal'ем).

Каково же было моё удивление, когда я обнаружила, что обоим квадратам соответствуют шаблоны, состоящие из одних четвёрок! (я брала вычеты по модулю 9).
Тогда стала смотреть, какие вычеты по модулю 9 дают смиты. Оказалось, что больше всего это 4, дальше по частоте идут 6, потом 0 и 8. Редки вычеты 1, 2, 3, 5, 7. Правда, я немного смитов проверила, может быть, дальше ситуация изменится. Но, тем не менее, вычеты встречаются все от 0 до 8.

Посмотрела, какой шаблон соответствет идеальному квадрату Журбы, вот этот шаблон:

1 2 6 3 5 7
8 8 3 7 4 3
0 3 5 4 4 8
6 1 1 0 2 5
2 1 7 2 6 6
7 0 2 8 3 4

В этом квадрате магическая константа S = 150 = 6(mod 9).

Можно ли по этому шаблону построить пандиагональный квадрат из смитов?
Или всё же целесообразнее сочинить шаблоны, состоящие из наиболее часто встречающихся для смитов вычетов 0, 4, 6, 8?
В общем, есть над чем подумать.

Это ещё один шаблон, соответствующий построенному мной идеальному квадрату из произвольных натуральных чисел (тоже по модулю 9):

3 5 4 7 2 6
2 5 1 3 3 4
7 1 8 3 6 2
1 6 0 4 2 5
8 0 0 2 7 1
6 1 5 8 7 0

В этом квадрате магическая константа S = 360 = 0(mod 9).

svb
появление в вашем квадрате одинаковых чисел наводит на мысль, что вы не формируете массив чисел для квадрата заранее.
То есть вы берёте некоторый массив простых чисел (состоящий более чем из 36 чисел) и каким-то образом строите из чисел этого массива квадрат.

[svb]

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

svb
появление в вашем квадрате одинаковых чисел наводит на мысль, что вы не формируете массив чисел для квадрата заранее.
То есть вы берёте некоторый массив простых чисел (состоящий более чем из 36 чисел) и каким-то образом строите из чисел этого массива квадрат.

Да, это так. Я модифицировал свой предыдущий алгоритм, в котором использовался набор из 18 комплементарных пар. Случайно обнаружил, что базис ${\bf E}$ из $(N-1)(N-3)$ элементов вида
$\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)$
для четных порядков не полный, к нему можно добавить элемент
$\left( {\begin{array}{*{20}c} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & { - 1} & 1 & { - 1} & 1 & { - 1} \\ 0 & 0 & 0 & 0 & 0 & 0 \\ { - 1} & 1 & { - 1} & 1 & { - 1} & 1 \\ \end{array}} \right)$
Линейная независимость элементов ${\bf E}$ очевидна и для любого пандиагонального квадрата легко можно вычислить координаты в этом базисе, но приведенный элемент не представим через элементы этого базиса - так я и обнаружил этот элемент. Вычитая из любого пандиагонального квадрата тот квадрат, который представлен элементами ${\bf E}$, всегда можно получить квадрат, в котором все элементы нулевые, кроме нижней полосы размером $3 \times N$. Ясно, что этот квадрат должен быть пандиагональным. Для четных порядков существует такой квадрат (вышеприведенный), для нечетных порядков я не обнаружил таких квадратов. В общем, к определению размерности "полосы" сводится определение размерности пространства пандиагональных квадратов. Я предполагаю, что для четных порядков эта размерность равна 1, а для нечетных - 0.

Гипотеза
Размерность пространства пандиагональных квадратов с нулевой суммой равна:
$\left( {N - 2} \right)^2 $ - для четных порядков,
$\left( {N - 1} \right)\left( {N - 3} \right)$- для нечетных порядков.

Для малых размерностей эта гипотеза подтверждается -
$N=2$ - размерность равна 0
$N=3$ - размерность равна 0
$N=4$ - размерность равна 4
$N=5$ - размерность равна 8
$N=6$ - размерность равна 16
- это число независимых параметров.

Так вот, используя новый базисный элемент, я получил квадрат
$\left( {\begin{array}{*{20}c} {a1} & {b1} & {a2} & {b2} & {a3} & {b3} \\ {c1} & {c2} & {c3} & {c4} & {c5} & {c6} \\ {b4} & {a4} & {b5} & {a5} & {b6} & {a6} \\ {b2'} & {a3'} & {b3'} & {a1'} & {b1'} & {a2'} \\ {c4'} & {c5'} & {c6'} & {c1'} & {c2'} & {c3'} \\ {a4'} & {b6'} & {a6'} & {b4'} & {a4'} & {b5'} \\ \end{array}} \right)$
где имеются пары: $c + c' = Sc$, $a + a' = Sa = Sc - d$ и $b + b' = Sb = Sc + d$. Например, для SUM=594 элементы выбираются из следующих наборов простых чисел:
$a,{\rm Sa = 192}{\rm , }\left( {{\rm 11}{\rm ,13}{\rm ,19}{\rm ,29}{\rm ,41}{\rm ,43}{\rm ,53}{\rm ,61}{\rm ,79}{\rm ,83}{\rm ,89}} \right)$
$b,{\rm Sb = 204}{\rm , }\left( {{\rm 5}{\rm ,7}{\rm ,11}{\rm ,13}{\rm ,23}{\rm ,31}{\rm ,37}{\rm ,41}{\rm ,47}{\rm ,53}{\rm ,67}{\rm ,73}{\rm ,97}} \right)$
$c,{\rm Sc = 198}{\rm , }\left( {{\rm 5}{\rm ,7}{\rm ,17}{\rm ,19}{\rm ,31}{\rm ,41}{\rm ,47}{\rm ,59}{\rm ,61}{\rm ,67}{\rm ,71}{\rm ,89}} \right)$

p.s. Забыл добавить. Естественно, что при переборе часто необходима замена приведенных чисел на дополнительные. Важно, чтобы элемент и его дополнительный не входили в наборы одновременно.

[Garik2]

В Вольфраме_Альфа есть раздел по магическим квадратам.
Может, пригодится?
http://mathworld.wolfram.com/topics/MagicSquares.html

[maxal]

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

В Вольфраме_Альфа есть раздел по магическим квадратам.
Может, пригодится?
http://mathworld.wolfram.com/topics/MagicSquares.html

Только это не Альфа, а MathWorld - см. http://ru.wikipedia.org/wiki/MathWorld

[Nataly-Mak]

Смиты можно рассматривать по модулю 2. Тогда все они разбиваются на две группы: с вычетом 0 (чётные) и с вычетом 1 (нечётные). И чётные, и нечётные смиты имеются примерно в равном количестве.
Поскольку все потенциальные магические константы для пандиагональных квадратов 6-го порядка чётные, значит равны 0(mod 2).
Вот можно попробовать сочинить шаблоны по модулю 2 для построения пандиагональных квадратов 6-го порядка из смитов.
Интересно, много ли их будет.

svb
хорошее развитие получил ваш алгоритм с комплементарными парами чисел.
Осталось выяснить, существуют ли пандиагональные квадраты 6-го порядка из простых чисел с магическими константами меньше 594. Таких констант осталось всего 9 штук: 486, 498, 510, 522, 534, 546, 558, 570, 582.

-- Пн авг 23, 2010 07:28:27 --

Ещё такая идея.

Берём, например, 100 первых смитов. Для них вычеты по модулю 9 получаются такие: 0, 4, 6, 8, 3, причём 3 всего 2 штуки.
Составляем пандиагональный квадрат 6-го порядка из этого массива вычетов, магическую константу заранее не задаём, какая получится. Если удастся составить пандиагональный квадрат из вычетов, это будет шаблон. Потом по шаблону можно попытаться составить квадрат из самих смитов.

[Garik2]

Nataly. Пока теоретически думаете, дайте мне для рассчитывания значения в МК3. Что у меня комп простаивает-то? Для самого ожидаемого, конечно случая из 486, 498, 510, 522, 534, 546, 558, 570, 582.

[Nataly-Mak]

Garik2
вы выражали желание проверить построенные МК на пандиагональность.
Я выложила все МК 6-го порядка из смитов с магической константой 2472 и предложила всем желающим проверить их на пандиагональность. Уже начала проверять сама, проверила примерно десятую часть, пандиагональных квадратов не нашла. Но мне приходится маленькими порциями проверять, потому что, как уже говорила, Бейсик не берёт большие массивы. Бросила это скучное занятие.
Для магических констант из простых я не знаю, какая самая ожидаемая
Возможно, 522. Вот у svb получились квадраты с такой константой, только в них маленький изъян: есть одинаковые числа.
____
Уже написала программу для шаблонов с вычетами 0, 3, 4, 6, 8. Шаблонов выдаётся море. Вот, например, два:

8  3  0  3  0  4 
 6  0  3  3  3  3 
 4  0  3  0  3  8 
 6  3  8  4  6  0 
 3  3  0  0  6  6 
 0  0  4  8  0  6 

 8  6  0  0  0  4 
 3  0  3  3  6  3 
 4  0  3  0  3  8 
 0  3  8  4  3  0 
 3  0  0  3  6  6 
 0  0  4  8  0  6

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

[Pavlovsky]

Использовать вычеты для чисел Смита так красиво как для простых чисел не получится.

Вот статистика по остаткам от деления чисел Смита (до 5000) на 9.

0 36
1 2
2 3
3 5
4 94
6 38
8 8

Строить шаблоны для чисел Смита сомнительное занятие. А вот тот факт что среди чисел Смита преобладают числа с остатком 4 от деления на 9, можно попробовать использовать.

Чтобы быстро найти пандиагональный МК с достаточно маленькой магической суммой, можно строить МК только из чисел с остатком 4. И соответственно сосредоточится на магических суммах вида 18k+6 (с учетом, что магическая сумма должна делиться на 6.).

[Nataly-Mak]

Да, но строить квадрат из чисел с одинаковым остатком не выгодно, потому что получается одна группа вычетов и нет никакого выигрыша (в смысле убыстрения выполнения программы).
Надо по крайней мере две группы вычетов. И на две такие группы смиты делятся - это вычеты по модулю 2. Почему же не получится? Точно так, как из простых чисел, имеем две группы вычетов: 0 и 1. Можно попытаться построить шаблоны. Ну, в общем всё так же, как из простых чисел.

Далее, шаблоны из вычетов 0, 3, 4, 6, 8 тоже неплохие. Разве нет? Я их уже построила. Можно брать любой шаблон, массив из 100 первых смитов, и - вперёд!
Сейчас ещё посмотрю, какие у шаблонов получаются магические константы. Я магическую константу заранее не задавала, пользовалась при написании программы для шаблонов той же самой общей формулой пандиагонального квдарата 6-го порядка, но с неизвестной магической константой. В показанных выше двух шаблонах S = 0(mod 9). Интерсено, что оба известные пандиагональные квадраты из смитов имеют S = 6(mod 9). Случайность?
Сейчас посмотрю, есть ли среди построенных шаблонов шаблоны с S = 6(mod 9). Может быть, такой шаблон и надо выбрать для начала.

Кроме того, есть среди шаблонов шаблоны без вычета 3 (троек очень мало, в первой сотне смитов их всего 2 штуки). Можно отдать предпочтение шаблонам без вычета 3. Тогда все смиты (в первой сотне) разделятся на 4 группы: с вычетами 0, 4, 6, 8. Мне, например, идея нравится.
Надо попробовать реализовать.
Можно взять массив не из 100 смитов, а меньше (если без вычета 3).

-- Пн авг 23, 2010 13:10:07 --

Вот, например, хороший шаблон, всего одна 3 и ни одной 6, S = 6(mod 9):

4  8  0  8  0  4 
 4  4  4  3  0  0 
 8  0  0  0  8  8 
 0  8  8  4  0  4 
 0  4  8  0  8  4 
 8  0  4  0  8  4 

Таким образом, надо включить в массив все смиты с вычетами 0, 3, 4, 8. Всего 4 группы получается, причём одна группа состоит всего из 2 элементов (самих смитов с вычетом 3 - 588 и 1776).
Конечно, никто не гарантирует, что пандиагональный квадрат по такому шаблону обязательно построится, но... других-то эффективных алгоритмов у меня пока не имеется.

[Nataly-Mak]

Итак, сформировала 4 группы смитов с вычетами 0, 3, 4, 8. В первой группе взяла 12 штук, во второй группе - 15 штук, в третьей группе - 28 штук, в четвёртой группе - 13 штук. Всего массив из 68 смитов.
Как оказалось, переменная, соответствующая вычету 3, зависимая, поэтому я решила взять побольше таких смитов (от количества чисел в этой группе ничего не зависит). От количества чисел в группах с вычетами 0, 4, 8 многое зависит: в этих группах находятся свободные переменные и очень важно, сколько значений они будут пробегать.

Группы можно расширить, скажем, до 36 чисел в каждой группе. Это будет соответствовать самой общей формуле, в которой каждая свободная переменная прбегает 36 значений. У меня такая программа не выполняется за реальное время, а у maxal'а выполняется. Хотя, я 12 часов программу ни разу и не крутила. Кроме того, у меня программа на Бейсике, а у maxal'а на С++.
Понятно, что чем больше будет массив чисел, тем выше вероятность построения квадрата. Если взять в каждой группе по 36 чисел, будет задействован массив из 144 чисел. Это приличный массив.

Приступаю к написанию программы. Может быть, эксперимент и не удастся, но... интерес экспериментатора легко понять
Математическое ожидание равно 0, потому что смиты очень плохо складываются в магические квадраты, тем более в пандиагональные.

[Nataly-Mak]

Написала 2/3 программы, уже 20 элементов получаются. Эта часть программы выполняется шутя, вот какой выдаётся результат:

778  0  27  0  378  0 
 0  0  58  0  0  1908 
 0  576  1755  648  0  728 
 0  6344  1736  0  0  0 
 666  202  1952  1872  1376  382 
 7784  0  922  0  0  895

Уже видно, что сама идея - построение квадрата по шаблону - работает. А почему бы ей не работать?

Конечно, вряд ли квадрат сложится до конца. Но если увеличить массив чисел...

Потом думаю: может, лучше взять шаблон из вычетов 0, 4, 6, 8? Не нравится мне вычет 3 в выбранном мной шаблоне. Потому не нравится, что у смитов с этим вычетом совсем другой разброс, нежели у смитов с вычетами 0, 4, 8.

-- Пн авг 23, 2010 19:38:24 --

Вот нашла шаблон без 3 (шаблонов очень много!):

8  4  0  8  0  4 
 0  4  4  8  0  8 
 8  0  8  0  8  0 
 0  8  4  0  4  8 
 0  8  0  8  4  4 
 8  0  8  0  8  0

Магическая константа S = 6(mod 9).

Но ещё лучше, по-моему, взять шаблон из вычетов 0, 4, 6, если такой имеется. Смиты с такими вычетами имеют примерно одинаковый разброс. Вот первые десять смитов с вычетами 0, 4, 6:

с вычетом 0: 27, 378, 576, 648, 666, 729, 1449, 1755, 1872, 1881
с вычетом 4: 4, 22, 58, 85, 94, 121, 166, 202, 265, 274
с вычетом 6: 438, 483, 627, 636, 645, 654, 663, 690, 762, 825

Для сравнения первые 10 смитов с вычетом 3:

588, 1776,2964, 3864, 4557, 5088, 5772, 6096, 6816, 7068

[Nataly-Mak]

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

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

Осенило во сне : смиты с одинаковым вычетом 4 тоже можно разбить на группы (любое количество групп можно сделать)!

Сейчас допишу вчерашнюю программу построения квадрата по шаблону. Потом сформирую 4 группы из смитов с одним и тем же вычетом 4 и воспользуюсь этой же программой. По-моему, идея верная. Просто вместо первого выбранного мной шаблона с вычетами 0, 3, 4, 8 будет подразумеваться шаблон, состоящий из одних четвёрок. Оба эти шаблона имеют S = 6(mod 9).

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

[Nataly-Mak]

Программа тест прошла!

Взяла известный пандиагональный квадрат из смитов, сформировала из чисел, составляющих этот квадрат, 4 группы смитов:

1-ая группа:1255 958 4306 3865 2605 2839 4414 706 2434 4126 2578 4702 562
2-ая группа: 634
3-ья группа: 2722 2965 2182 391 2902 2038 3505 454 1858 4594 1921
4-ая группа: 2326 4054 4198 58 166 3802 1795 895 4369 346 2155

Здесь точно 36 чисел. Для всех этих смитов вычеты равны 4 (по модулю 9). Разделение на группы я сделала в соответствии с первым выбранным мной шаблоном с вычетами 0, 3, 4, 8, для которого я уже написала программу.

Запустила тест-программу, квадрат построился моментально, он в точности совпадает с квадратом, найденным maxal'ем:

2722  2326  1255  4054  958  2965 
 2182  391  2902  634  4306  3865 
 4198  2605  2839  4414  58  166 
 706  3802  1795  2038  2434  3505 
 4126  454  895  2578  4369  1858 
 346  4702  4594  562  2155  1921

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

Дальше дело техники. Запускаем программу на неделю и ждём пандиагональный квадрат