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

[Nataly-Mak]

И где все? Где новые квадраты?

Вот так глубоко нельзя в теорию углубляться, svb, это я вас имею в виду. При таком погружении в теорию страдает практика, квадраты-то не строятся
Pavlovsky совсем пропал. 12d3 появился на один миг и опять исчез. Приходится за всех квадраты строить.

Да, так вот написала уже программу построения совершенного квадрата 8-го порядка с 8 независимыми переменными. Начала проверять наборы комплементарных пар. С небольшим количеством пар в наборе (примерно до 60) программа выполняется быстро, но увеличение количества пар резко замедляет выполнение.
Начала думать, как уменьшить количество независимых переменных, кажется, можно на единицу уменьшить. Сейчас буду корректировать программу. С 7 независимыми переменными должна быстрее работать.

Для классического совершенного квадрата примитивный квадрат находится за секунду:

1  5  17  21  33  37  49  53 
 2  6  18  22  34  38  50  54 
 3  7  19  23  35  39  51  55 
 4  8  20  24  36  40  52  56 
 9  13  25  29  41  45  57  61 
 10  14  26  30  42  46  58  62 
 11  15  27  31  43  47  59  63 
 12  16  28  32  44  48  60  64

Это собственно обратимый квадрат.

[Pavlovsky]

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

Pavlovsky совсем пропал.

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

[Nataly-Mak]

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

Вчера весь вечер ломала голову, как оптимизировать программу построения совершенного квадрата 8-го порядка. Сначала показалось, что можно свести количество независимых переменных к 7, сейчас 8. Но ни черта не получилось, там всюду по два числа из одной комплементарной пары и необходимо одно из них перебирать. Прямо уснула за столом, так ничего и не придумала.

Объявляю конкурс на самый эффективные алгоритмы построения совершенного квадрата 8-го порядка и идеального квадрата 9-го порядка.

Приглашаются все!

У меня для совершенных квадратов пока 8 независимых переменных, для идеальных квадратов 9-го порядка - 11. Надо учитывать, что придётся проверять десятки, а может быть, и сотни наборов комплементарных пар.
В поиске совершенного квадрата 6-го порядка я проверила сотни наборов. Но в этой программе всего 4 независимых переменных и программа выполняется очень быстро.

Абсолютно упёрся идеальный квадрат 7-го порядка из простых чисел. Уже проверила сотни наборов. В программе 6 независимых переменных. Программу уже оптимизировала до предела, работает быстро. Но надоело проверять. И подряд проверяла, и выборочно. Нет квадрата

Pavlovsky
когда вы опубликовали сообщение "По мотивам алгоритма svb", у меня промелькнула мысль: надо использовать вашу находку с примитивными квадратами в алгоритме svb. Недаром я задала вопрос о количестве независимых переменных в вашем новом алгоритме. Это очень важный вопрос!

Как я уже говорила, в алгоритме svb 12 независимых переменных, но это на втором этапе алгоритма - собственно перебор. А для работы программы второго этапа необходимо ещё сформировать комплекты отклонений, это ещё 4 независимых переменных. В итоге получаются те же 16 независимых переменных, которые мы имеем в общей формуле.

При поиске пандиагональных квадратов из смитов по программе svb я обработала несколько тысяч комплектов отклонений. До магической константы 5964 квадраты находились быстро, с 2-3 попыток (одна попытка - это тысяча комплектов отклонений). Но на константе 5856 всё закончилось. Прокрутила программу раз 20 и бросила.
Начала искать другие пути, тут была высказана идея с заготовками и их достраиванием. Но svb подверг идею резкой критике, и я её бросила. Он писал, что работает над поиском наилучших наборов отклонений, чтобы его программа работала наиболее эффективно. Но, видимо, прекратил эту работу.
Собственно, я согласна, что путь поиска оптимальных отклонений и путь поиска всех возможных заготовок в чём-то близки. Но ни тот, ни другой путь не завершены.

Как я поняла ваш алгоритм, вы строите пандиагональный квадрат 6-го порядка из примитивных квадратов 3х3, которые уже обеспечивают правильные диагонали. А затем перестановками чисел в парах пытаетесь получить правильные строки и столбцы.
Я аналогично действую в построении идеального квадрата 9-го порядка, он тоже составляется из примитивных квадратов 3х3. Но я не составляю заранее примитивные квадраты, просто начинаю сразу строить идеальный квадрат 9-го порядка, используя все зависимости, которые дают примитивные квадраты. В результате у меня в программе получается всего 11 независимых переменных, в то время как в общей формуле идеального квадрата 9-го порядка 24 независимых переменных.

[Nataly-Mak]

Продемонстрирую алгоритм построения совершенного квадрата 8-го порядка.

Вводим в программу набор комплементарных пар, например, такой:

5 82 15 72 25 62 35 52 42 45 32 55 22 65 12 75 6 81 16 71 26 61 36 51 41 46 31 56 21 66 11 76 7 80 17 70 27 60 37 50 40 47 30 57 20 67 10 77 8 79 18 69 28 59 38 49 39 48 29 58 19 68 9 78

Пары могут следовать в любом порядке, но обязательно записывать числа попарно – два числа из каждой комплементарной пары. Константа комплементарности (сумма чисел в паре) равна 87. В этом наборе 32 пары - минимальное необходимое количество пар для построения совершенного квадрата 8-го порядка.
Результатом работы программы для данного набора будет следующий примитивный квадрат (программа работает до первого квадрата):

5  6  10  9  46  45  49  50 
 15  16  20  19  56  55  59  60 
 25  26  30  29  66  65  69  70 
 35  36  40  39  76  75  79  80 
 7  8  12  11  48  47  51  52 
 17  18  22  21  58  57  61  62 
 27  28  32  31  68  67  71  72 
 37  38  42  41  78  77  81  82

Применяем к этому примитивному квадрату матричное преобразование из моей статьи о построении классических совершенных квадратов 8-го порядка из обратимых. Получаем следующий совершенный квадрат:

5 81 10 78 50 38 45 41
60 28 55 31 15 71 20 68
25 61 30 58 70 18 65 21
80 8 75 11 35 51 40 48
37 49 42 46 82 6 77 9
72 16 67 19 27 59 32 56
17 69 22 66 62 26 57 29
52 36 47 39 7 79 12 76

Теперь покажу схему примитивного квадрата, по которой я писала программу:

a1 a2 a3 a4 a5 a6 a7 a8
b1 c1 c2 c3 c4 c5 c6 b6’
b2 c7 c8 c9 c10 c11 c12 b5’
b3 c13 c14 c15 c16 c17 c18 b4’
b4 c18’ c17’ c16’ c15’ c14’ c13’ b3’
b5 c12’ c11’ c10’ c9’ c8’ c7’ b2’
b6 c6’ c5’ c4’ c3’ c2’ c1’ b1’
a8’ a7’ a6’ a5’ a4’ a3’ a2’ a1’

a_i + a_i’ = K, b_i + b_i’ = K, c_i + c_i’ = K, где K = S/4, $S$ - магическая константа квадрата.
Независимые элементы: a_1, a_2, a_3, a_4, a_8, b_1, b_2, b_3. Все остальные элементы вычисляются.

Важно отметить, что представленный примитивный квадрат симметрический – сумма любых двух элементов, симметрично расположенных относительно центра квадрата, равна одной и той же величине $K$. Кроме того, он ещё и пандиагональный: сумма чисел во всех диагоналях, как главных, так и разломанных, равна магической константе квадрата. Всё остальное довершает матричное преобразование.

[Nataly-Mak]

Начала проверку наборов комплементарных пар на предмет построения совершенного квадрата 8-го порядка из простых чисел.
Пока нашёлся только полуфабрикат:

 67  97  607  727  1117  1237  1747  1777 
 79  109  619  739  1129  1249  1759  1789 
 151  181  691  811  1201  1321  1831  1861 
 0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0 
 317  347  857  977  1367  1487  1997  2027 
 389  419  929  1049  1439  1559  2069  2099 
 401  431  941  1061  1451  1571  2081  2111

Есть надежда на полный квадрат

[Nataly-Mak]

Ещё один полуфабрикат:

29  167  337  379  1217  1259  1429  1567 
 89  227  397  439  1277  1319  1489  1627 
 293  431  601  643  1481  1523  1693  1831 
 701  839  1009  0  0  0  0  2239 
 71  0  0  0  0  1301  1471  1609 
 479  617  787  829  1667  1709  1879  2017 
 683  821  991  1033  1871  1913  2083  2221 
 743  881  1051  1093  1931  1973  2143  2281

Осталось совсем немножко

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

[Nataly-Mak]

Пока программа проверяет следующие наборы комплементарных пар, вручную достраиваю привидённый выше примитивный квадрат до полного:

29 167 337 379 1217 1259 1429 1567
89 227 397 439 1277 1319 1489 1627
293 431 601 643 1481 1523 1693 1831
701 839 1009 1051 1889 1931 2101 2239
71 209 379 421 1259 1301 1471 1609
479 617 787 829 1667 1709 1879 2017
683 821 991 1033 1871 1913 2083 2221
743 881 1051 1093 1931 1973 2143 2281

Можно сказать, что совершенный квадрат 8-го порядка получен, но только в нём два дефекта: два числа не являются простыми и есть одинаковые числа. Собственно, поэтому программа и выдала полуфабрикат.

Но интересный факт: обратила внимание на структуру полученного примитивного квадрата, она такова, что в левой половине квадрата расположены только первые числа из комплементарных пар, а в правой половине квадрата - только вторые числа. Такое же расположение вижу во всех других примитивных квадратах 8х8, полученных по этой программе (для дальнейшего превращения в совершенный квадрат 8-го порядка).
Эта закономерность позволила немного оптимизировать программу: при проверке вычисляемых элементов квадрата на принадлежность массиву теперь проверяю только ту половину массива, к которой элемент должен принадлежать; это в два раза сокращает каждую процедуру проверки. Оптимизация чуть ускорила выполнение программы.

[Nataly-Mak]

Пока крутится программа проверки наборов комплементарных пар простых чисел на предмет построения совершенного квадрата 8-го порядка, думаю над тем, как построить пандиагональный квадрат 11-го порядка из простых чисел, хотя бы какой-нибудь - не наименьший.
У нас уже есть пандиагональные квадраты всех порядков до 10, кроме порядка 9.

Для порядка 11 всё очень просто: надо построить примитивный квадрат 11х11 и с помощью преобразования Россера превратить его в пандиагональный. При этом примитивный квадрат не должен обладать никакими дополнительными свойствами, так как порядок 11 простое число.

Помнится, что svb где-то писал, что для порядка 11 у него примитивный квадрат не получился так же легко, как для порядка 7. Это понятно, так же легко не получится Но надо же искать какие-то пути.

Я попробовала достраивание примитивного квадрата 7х7 до примитивного квадрата 11х11. Может быть, уже приводила картинку, но повторюсь:



Только 4 числа здесь не являются простыми (они выделены). Но можно попытаться достроить так, чтобы все числа были простыми. Осталось всего 2 столбца! Вполне возможно, что при других разностях всё получится. Но надо пробовать. Надо брать ещё другие примитивные квадраты 7х7 и пытаться их достраивать.

Это один из возможных путей. Можно придумать другие способы построения примитивного квадрата 11-го порядка.

Пыталась достроить примитивный квадрат 5х5 из смитов до примитивного квадрата 7х7. У нас не найден пандиагональный квадрат 7-го порядка из смитов. Тоже с ходу не получилось, надо много экспериментировать. Времени на все эксперименты не хватает

[Nataly-Mak]

Есть первый идеальный квадрат 7-го порядка из простых чисел

20233 27799 30637 37123 44017 7753 13759
43093 7717 13723 19309 26863 34429 36187
25939 33493 39979 42157 6793 13687 19273
5857 12763 19237 25903 32569 39043 45949
32533 38119 45013 9649 11827 18313 25867
15619 17377 24943 32497 38083 44089 8713
38047 44053 7789 14683 21169 24007 31573

S = 181321

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

После неудачного поиска совершенного квадрата 8-го порядка решила пока оставить его и вернуться к идеальным квадратам 7-го порядка. И вот удача! Квадрат нашёлся. Ну, теперь можно заново перепроверить все потенциальные константы подряд, начиная с найденной и двигаясь вниз. Может, есть и с меньшей магической константой.

[Nataly-Mak]

Всё, проверила все потенциальные магические квадраты для идеального квадрата 7-го порядка из простых чисел, начиная с минимально возможной 4319. Больше идеальных квадратов по представленному алгоритму не нашлось. Осталось доказать, что алгоритм не теряет решения.

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

[Nataly-Mak]

Немного дополнила статьи "Нетрадиционные пандиагональные квадраты (часть II)" и "Нетрадиционные совершенные квадраты".

[Nataly-Mak]

Пробовала построить идеальный квадрат из смитов 7-го порядка, тут всё очень плохо
Начала проверять с небольших потенциальных магических констант, программа бежит, комплементарных пар в наборах мало. Увеличила потенциальные константы порядка 1178996 и больше, пар стало побольше, но всё равно ничего не находится.

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

357286 337486 402718 512266 90274
325246 434794 170266 352246 417478
165226 432238 340006 247774 514786
262534 327766 509746 245218 354766
589738 167746 277294 342526 322726

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

165226 352246 337486 322726 509746
245218 432238 417478 402718 589738
167746 354766 340006 325246 512266
90274 277294 262534 247774 434794
170266 357286 342526 327766 514786

Далее выполняю вручную оригинальное достраивание этого примитивного квадрата до примитивного квадрата 7х7, путём окаймления, чтобы не нарушилась симметричность квадрата:

149494 164456 351476 336716 321956 508976 523938
150264 165226 352246 337486 322726 509746 524708
230256 245218 432238 417478 402718 589738 604700
152784 167746 354766 340006 325246 512266 527228
75312 90274 277294 262534 247774 434794 449756
155304 170266 357286 342526 327766 514786 529748
156074 171036 358056 343296 328536 515556 530518

Конечно, в окаймлении большинство чисел не являются смитами. Тем не менее, в квадрате большая часть чисел - смиты.
Теперь применяю к полученному примитивному квадрату своё матричное преобразование и получаю следующий идеальный квадрат 7-го порядка
почти из смитов:

589738 527228 75312 170266 358056 336716 322726
171036 351476 337486 402718 512266 449756 155304
325246 434794 529748 156074 164456 352246 417478
149494 165226 432238 340006 247774 514786 530518
262534 327766 515556 523938 150264 245218 354766
524708 230256 167746 277294 342526 328536 508976
357286 343296 321956 509746 604700 152784 90274

Ну, а настоящий идеальный квадрат 7-го порядка из смитов будет где-то очень далеко. Проверила тот набор комплементарных пар, из которого maxal построил идеальный квадрат 5-го порядка, этот набор состоит из 556 пар, но программа не нашла примитивный квадрат из чисел этого набора.
Магическая константа наименьшего идеального квадрата 5-го порядка из смитов равна 1700030. Чему она будет равна для наименьшего идеального квадрата 7-го порядка из смитов - трудно даже предположить

[Nataly-Mak]

Ещё попытка получить примитивный квадрат 11-го порядка.

Взяла примитивный квадрат 7х7, который построила по программе для идеального квадрата 7-го порядка, и достроила его слева и справа столбцами. Получила примитивный прямоугольник 7х11, здесь показываю часть этого прямоугольника, у меня есть ещё 15 столбцов, но и это не предел, вправо прямоугольник можно продолжить.

521 823 859 1237 2917 3251 4283 5857 6599 6793 7717 7753 7789 8713 9649 11519 12241 13339 13457
6491 6793 6829 7207 8887 9221 10253 11827 12569 12763 13687 13723 13759 14683 15619 17489 18211 19309 19427
12041 12343 12379 12757 14437 14771 15803 17377 18119 18313 19237 19273 19309 20233 21169 23039 23761 24859 24977
18671 18973 19009 19387 21067 21401 22433 24007 24749 24943 25867 25903 25939 26863 27799 29669 30391 31489 31607
25301 25603 25639 26017 27697 28031 29063 30637 31379 31573 32497 32533 32569 33493 34429 36299 37021 38119 38237
30851 31153 31189 31567 33247 33581 34613 36187 36929 37123 38047 38083 38119 39043 39979 41849 42571 43669 43787
36821 37123 37159 37537 39217 39551 40583 42157 42899 43093 44017 44053 44089 45013 45949 47819 48541 49639 49757

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

Кто смелый и умелый? Задачка совсем простенькая
Жду готовый примтивный квадрат 11х11

[Pavlovsky]

Наталия извините, что долго не отвечал на ваши вопросы. Хотелось ответить на них достаточно подробно. Но чего то не пишется. Поэтому отвечу пока кратко.

Цитата:

когда вы опубликовали сообщение "По мотивам алгоритма svb", у меня промелькнула мысль: надо использовать вашу находку с примитивными квадратами в алгоритме svb. Недаром я задала вопрос о количестве независимых переменных в вашем новом алгоритме. Это очень важный вопрос!

Собственно мой вариант алгоритма svb использует примитивные квадраты описанные мною. Увы большого выигрыша это не дает. Используя свой вариант алгоритма, неспешно просеиваю магические константы, но пока ничего не найдено.

Цитата:

Как я уже говорила, в алгоритме svb 12 независимых переменных, но это на втором этапе алгоритма - собственно перебор. А для работы программы второго этапа необходимо ещё сформировать комплекты отклонений, это ещё 4 независимых переменных. В итоге получаются те же 16 независимых переменных, которые мы имеем в общей формуле.

Естественно у меня получается тоже 16 независимых переменных. Основной постулат линейной алгебры утверждает: Любая замена уравнений в системе уравнений их линейной комбинацией, любая замена переменных должна давать одно и тоже число независимых переменных. Другое дело мы ведь не систему линейных уравнений решаем. Нам нужно решение системы линейных уравнений из заданного множества чисел, плюс в решении все переменные должны быть различными. Получается дискретная задача, которая может решаться только перебором.
Перебираем различные частичные решения и проверяем выполняется ли система уравнений. То есть сама система линейных уравнений выполняет вспомогательную функцию. Манипулируя системой уравнений можно существенно сократить перебор.

Цитата:

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

Это не совсем так. Описанные мною, примитивные квадраты заполняются не числами Смита, а суммой двух чисел. Затем под каждую сумму подбирается пара чисел Смита. В результате получаем МК с выставленными диагоналями. Подробное описание своего алгоритма дам чуть позже.

[Nataly-Mak]

Тогда я не совсем вникла в описанный вами выше алгоритм: где там примитивные квадраты. Вот когда я писала программу построения идеального квадрата 9-го порядка, так там эти примитивные квадраты прямо в чистом виде по всем решёткам, какую ни возьми. И, повторюсь: эти самые примитивные квадраты, точнее, их свойства, позволили резко сократить количество независимых переменных (с 24 до 11). То же самое в совершенном квадрате 6-го порядка. А вот в пандиагональном квадрате 6-го порядка я пока не усекла, где там примитивные квадраты получаются, просто не вникала особо; когда вы опубликовали свой алгоритм, я была уже далеко от пандиагональных квадратов 6-го порядка и больше к ним пока не возвращалась.

____

Увлекательнейшее занятие получилось с достраиванием примитивного прямоугольника до примитивного квадрата 11х11.
Прямоугольник получается огромный, я выполнила достраивание по программе сначала без проверки всех чисел на принадлежность массиву простых чисел. У меня получился огромный примитивный прямоугольник, в котором 34 столбца, а строк $n$, даже не сосчитала строки, но очень много, около 500.
Вот такой примитивный прямоугольник! Теперь начинаю "рыскать" по этому прямоугольнику в поисках хоть одной строки длиной 11, состоящей полностью из простых чисел.
Мне удалось найти только одну такую строку, в результате имеем примитивный прямоугольник 8х11:

7717  7753  7789  8713  9649  11519  12241  13339  13457  15497  17203 
 13687  13723  13759  14683  15619  17489  18211  19309  19427  21467  23173 
 15277  15313  15349  16273  17209  19079  19801  20899  21017  23057  24763 
 19237  19273  19309  20233  21169  23039  23761  24859  24977  27017  28723 
 25867  25903  25939  26863  27799  29669  30391  31489  31607  33647  35353 
 32497  32533  32569  33493  34429  36299  37021  38119  38237  40277  41983 
 38047  38083  38119  39043  39979  41849  42571  43669  43787  45827  47533 
 44017  44053  44089  45013  45949  47819  48541  49639  49757  51797  53503

Числа на повторяемость не проверяла, но вроде не должны повторяться.
Осталось всего три строки получить.
У меня в массиве простых чисел задействовано 16000 чисел, массив большего размера Бейсик не берёт. Так что, увы, дальше не могу проверить.

Не возьмётся ли кто-нибудь порешать задачу дальше?

-- Пн окт 18, 2010 14:06:27 --

Вот ёлки зелёные!

Есть два одинаковых числа - 19309. Всё насмарку
Вот в таком огромном примитивном прямоугольнике не находится ни одной строчки, состоящей из простых чисел (дополнительно к известным 7 строкам).
При этом нужно даже не всю строчку длиной 34, а только часть строчки длиной 11.
Ну и дела!