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

[Jnrty]

Jnrty:

Vasily, у Вас два сообщения в этой теме, и оба - offtopic. Предупреждение. При продолжении будет бан.

Nataly-Mak, прошу не развивать дискуссию с Vasily.

[Nataly-Mak]

Внимание!

Конкурс "Нетрадиционные пандиагональные квадраты" продлевается на два месяца, до 12 марта 2011 г. (18 мск.).

[Nataly-Mak]

В гостевой книге сайта мне написали следующее:

Цитата:

Не нашел в Вашей книге магических) квадратов, образованных простыми числами-близнецами. Наверное, для полноты темы следует их включить. См. http://www.primepuzzles.net/puzzles/puzz_121.htm

Конкурс Зиммерманна закончился, собираюсь вернуться к магическим квадратам.
Я остановилась на алгоритмах построения нетрадиционных пандиагональных квадратов 8-го порядка. Начну писать статью с алгоритмов построения классических пандиагональных квадратов 8-го порядка; мне известно несколько таких алгоритмов, самый последний - из статьи Россера.

Напоминаю всем, что продолжается конкурс "Нетрадиционные пандиагональные квадраты". Жду участников

[Nataly-Mak]

Написала третью часть статьи "Нетрадиционные пандиагональные квадраты".
Как уже сообщала, статья посвящена методам построения пандиагональных квадратов 8-го порядка, классических и нетрадиционных.

Прошу коллег написать змечания по статье.
На очереди пандиагональные квадраты 9-го порядка. Это самый сложный порядок. До сих пор не построено ни одного пандиагонального квадрата из простых чисел. Задача включена в конкурс, однако решения нет.
Надо бы ещё покрутить программу поиска идеального квадрата из простых чисел, пока результатов нет.
Нужны новые эффективные алгоритмы для построения нетрадиционных пандиагональных квадратов 9-го порядка. Из произвольных натуральных чисел я разработала такие алгоритмы, но они не годятся для квадратов из простых чисел.

[Nataly-Mak]

svb
не знаете ли вы, что с вашим переводом статьи Россера? Вы закрыли файл?
Почему-то по ссылке
http://svb.hut/DOWN/Rosser_ru.pdf
файл не открывается.
У меня-то перевод давно скопирован. Но вот на моём конкурсе по квадратам я указала эту ссылку. Только сейчас вдруг заметила, что ссылка не работает.
Вроде с самого начала объявления конкурса она работала, хотя не уверена, что я проверяла тогда.
Может быть, вы возражаете против свободного использования вашего перевода? Что ж, это ваше право.

[Nataly-Mak]

Выше я уже приводила несколько нетрадиционных пандиагональных квадратов 9-го порядка. В одном из них 32 числа не являются простыми. Но этот квадрат построен другим методом, не аналогичным методу Россера для классического пандиагонального квадрата.
Кстати, об этом методе Россера. Он работает для любого порядка $n=3m, m=3, 4, ...$. В частности, можно построить этим методом классический пандиагональный квадрат 15-го порядка - задача, над которой очень долго бились я и Г. Александров. Тогда мы не читали ещё статью Россера.

Интересно, что метод Россера для классического квадрата 9-го порядка, основанный на построении примитивного квадрата с последующим применением к нему преобразования (см. теорема 5.5, случай 3), можно с успехом применить и для построения нетрадиционных пандиагональных квадратов 9-го порядка. Тут вся сложность в построении примитивного квадрата. Каким он должен быть, каким условиям должен удовлетворять?
Я много анализировала этот вопрос. Приведу один пример. В этом примере строится нетрадиционный пандиагональный квадрат из простых чисел, но только с повторениями чисел. Тем не менее пример показателен. В нём есть примитивный квадрат, к этому квадрату применено преобразование Россера
$A(i,j)=B(i+j,2i+3j)$ и получен нетрадиционный пандиагональный квадрат 9-го порядка.
Это примитивный квадрат:

5 59 23 23 5 59 59 23 5
53 107 71 71 53 107 107 71 53
13 67 31 31 13 67 67 31 13
13 67 31 31 13 67 67 31 13
5 59 23 23 5 59 59 23 5
53 107 71 71 53 107 107 71 53
53 107 71 71 53 107 107 71 53
13 67 31 31 13 67 67 31 13
5 59 23 23 5 59 59 23 5

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

71 5 5 67 71 71 5 67 67
59 67 31 53 5 59 31 71 53
31 53 107 59 31 13 53 59 23
107 23 23 13 107 107 23 13 13
5 13 67 71 23 5 67 107 71
67 71 53 5 67 31 71 5 59
53 59 59 31 53 53 59 31 31
23 31 13 107 59 23 13 53 107
13 107 71 23 13 67 107 23 5

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

[Nataly-Mak]

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

svb
не знаете ли вы, что с вашим переводом статьи Россера? Вы закрыли файл?
Почему-то по ссылке
http://svb.hut/DOWN/Rosser_ru.pdf
файл не открывается.

svb
прошу прощения. У меня неправильно написана ссылка, правильно должно быть так:
http://svb.hut.ru/DOWN/Rosser_ru.pdf
Странно, что за всё время конкурса никто не написал, что статья не открывается. Значит, никто и не пытался открыть?

[Nataly-Mak]

Закончила писать часть статьи "Нетрадиционные пандиагональные квадраты", посвящённую пандиагональным квадратам 9-го порядка (пока не выкладываю, до окончания конкурса).
Приведу только один нетрадиционный пандиагональный квадрат из различных произвольных натуральных чисел, построенный методом Россера:

56 90 165 216 248 67 106 40 146
63 152 53 89 5 222 226 221 103
199 257 60 175 59 86 4 62 232
61 72 205 235 214 172 82 92 1
115 7 58 71 45 241 192 326 79
304 233 112 30 64 68 44 81 198
80 38 310 211 266 27 87 74 41
97 47 77 37 150 217 244 181 84
159 238 94 70 83 34 149 57 250

Пока писала статью, пришлось во всё заново вникнуть; пришла в голову новая идейка, надо будет попробовать её реализовать.
Покрутила немного программу построения идеального квадрата из простых чисел. Испытала несколько первых потенциальных массивов, они содержат от 40 до 49 комплементарных пар простых чисел. Вот такие полуфабрикаты строятся в 1-2 секунды из многих потенциальных массивов:

23 2861 29 47 2777 2753 137 2687 1583
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 1433 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1283 179 2729 113 89 2819 2837 5 2843

На формирование первой строки и симметричной последней строки задействовано 8 независимых переменных, а на остальное достраивание остаётся только 3 независимых переменных (всего в программе 11 независимых переменных). Тем не менее именно на достраивании программа "буксует".

[Nataly-Mak]

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

5 215 425 17 227 437 29 239 449
47 257 467 59 269 479 71 281 491
89 299 509 101 311 521 113 323 533
635 845 1055 647 857 1067 659 869 1079
677 887 1097 689 899 1109 701 911 1121
719 929 1139 731 941 1151 743 953 1163
1265 1475 1685 1277 1487 1697 1289 1499 1709
1307 1517 1727 1319 1529 1739 1331 1541 1751
1349 1559 1769 1361 1571 1781 1373 1583 1793

Примитивный квадрат получился просто замечательный, во-первых, он обладает свойством пандиагональности, как любой примитивный квадрат, во-вторых, он симметрический, то есть обладает свойством ассоциативности.
Полный аналог обратимого квадрата! И, конечно, можно запросто написать матричное преобразование, превращающее этот примитивный квадрат в идеальный магический квадрат. А можно и не писать никаких преобразований, воспользоваться очень простым приёмом: пронумеровать элементы примитивного квадрата в естественном порядке и заполнить матрицу 9х9 в соответствии с каким-нибудь (любым!) классическим идеальным квадратом (числа в классическом квадрате суть порядковые номера элементов в примитивном квадрате).

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

[Nataly-Mak]

Часть программы построения примитивного квадрата 9х9 для нетрадиционного идеального квадрата написала. Свела количество независимых переменных к 7. Теперь программа работает намного быстрее.
Взяла для тестирования массив простых чисел с центральным числом 1747, в массиве 47 комплементарных пар. Вот результат выполнения первого этапа:

373  223  37  607  457  307  877  691  541 
 823  0  0  0  0  0  0  0  991 
 163  0  0  0  0  0  0  0  331 
 1213  0  0  0  0  0  0  0  1381 
 1663  0  0  0  1747  0  0  0  1831 
 2113  0  0  0  0  0  0  0  2281 
 3163  0  0  0  0  0  0  0  3331 
 2503  0  0  0  0  0  0  0  2671 
 2953  2803  2617  3187  3037  2887  3457  3271  3121

Это находится за 2 секунды.

Нашла в своей статье "Построение идеальных квадратов нечётного порядка из обратимых квадратов" матричное преобразование. Попробовала применить его к примитивному квадрату 9х9 из произвольных натуральных чисел. Работает! Нетрадиционный идеальный квадрат 9-го порядка получается.
Итак, задача свелась к построению примитивного квадрата.

[Nataly-Mak]

Собственно, примитивный квадрат уже полностью построен на данном этапе, в программе сделан выход в конец сразу же при первом найденном полуфабрикате (см. предыдущий пост).
На втором этапе, понятно, будет простое заполнение примитивного квадрата по известным формулам и проверка полученных элементов на принадлежность массиву и на различность. Этот этап должен выполняться малые доли секунды.
Достроила приведённый выше полуфабрикат вручную. Примитивный квадрат получен, но, конечно, элементы внутри квадрата оказались самые разные: это и не простые числа, и одинаковые числа, и даже одно число оказалось отрицательным. Вот этот квадрат:

373 223 37 607 457 307 877 691 541
823 673 487 1057 907 757 1327 1141 991
163 13 -173 397 247 97 667 481 331
1213 1063 877 1447 1297 1147 1717 1531 1381
1663 1513 1327 1897 1747 1597 2167 1981 1831
2113 1963 1777 2347 2197 2047 2617 2431 2281
3163 3013 2827 3397 3247 3097 3667 3481 3331
2503 2353 2167 2737 2587 2437 3007 2821 2671
2953 2803 2617 3187 3037 2887 3457 3271 3121

Сейчас применю к этому примитивному квадрату своё матричное преобразование (вчера уже поздно было, не успела). Должен получиться нетрадиционный идеальный квадрат 9-го порядка.

Тогда можно сказать, что программа построения нетрадиционных идеальных квадратов 9-го порядка готова. Повторюсь: в программе всего 7 независимых переменных.
Осталось найти такой массив простых чисел (состоящий из комплементарных пар, не менее 40 пар), чтобы примитивный квадрат состоял из различных простых чисел.

-- Вс мар 06, 2011 09:27:58 --

Да, нетрадиционный идеальный квадрат 9-го порядка [в результате применения матричного преобразования (см. указанную выше статью) к приведённому примитивному квадрату] получился:

13 2887 457 3397 1141 1777 1831 1213 3007
2431 1327 1381 2503 667 2803 307 3247 1057
3457 223 3097 907 2347 1981 877 2671 163
1897 1531 2167 331 2953 877 3013 757 2197
373 3667 673 2047 1747 1447 2821 -173 3121
1297 2737 481 2617 541 3163 1327 1963 1597
3331 823 2617 1513 1147 2587 397 3271 37
2437 247 3187 691 2827 991 2113 2167 1063
487 2281 1663 1717 2353 97 3037 607 3481

[Nataly-Mak]

Наверное, коллеги так умаялись конкурсом Зиммерманна, что пока не в состоянии думать о магических квадратах

Вот примитивный квадрат для идеального квадрата 9-го порядка, построенный не по программе, а другим методом: взяла примитивный квадрат 7х7 для идеального квадрата 7-го порядка из простых чисел и специальным образом достроила его до примитивного квадрата 9х9:

35491 35527 36463 37387 37423 37459 38383 39319 39355
42121 42157 43093 44017 44053 44089 45013 45949 45985
11791 11827 12763 13687 13723 13759 14683 15619 15655
17341 17377 18313 19237 19273 19309 20233 21169 21205
23971 24007 24943 25867 25903 25939 26863 27799 27835
30601 30637 31573 32497 32533 32569 33493 34429 34465
36151 36187 37123 38047 38083 38119 39043 39979 40015
5821 5857 6793 7717 7753 7789 8713 9649 9685
12451 12487 13423 14347 14383 14419 15343 16279 16315

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

11827 14419 37423 38047 45949 31573 27835 17341 8713
34429 24943 21205 5821 14683 12487 37459 38083 44017
15343 35527 38119 44053 32497 27799 18313 9685 11791
25867 21169 6793 15655 12451 38383 36187 44089 32533
35491 39043 42157 32569 25903 19237 9649 12763 16315
19273 7717 15619 13423 39355 36151 45013 30637 25939
40015 42121 33493 24007 19309 7753 13687 16279 36463
7789 13723 14347 39319 37123 45985 30601 26863 17377
43093 34465 23971 20233 5857 13759 14383 37387 39979

Второе приближение к искомому идеальному квадрату

Эх, надо было сразу строить примитивный квадрат из простых чисел для идеального квадрата 9-го порядка, потом просто выбросить из него две строки и два столбца и получился бы примитивный квадрат для идеального квадрата 7-го порядка.
___________

По программе проверила потенциальные массивы с центральными числами от 1277 до 1759, эти массивы содержат от 40 до 49 комплементарных пар простых чисел. Для них программа работает быстренько (2-3 минуты).
Потом проверила несколько массивов выборочно с такими центральными числами: 2447 (59), 3347 (68), 4091 (91), 7247 (132), 7477 (127), 7919 (142), 19387 (277), 25903 (361). В скобках указано количество комплементарных пар в массиве. Для последних двух массивов не выполнила программу до конца, прервала, долго (более часа). Последнее центральное число - центральное число в найденном идеальном квадрате 7-го порядка из простых чисел.
Пока идеальный квадрат 9-го порядка не найден.

[Nataly-Mak]

Вчера друг прислал книгу: Н. И. Игнатьев, "В царстве смекалки или арифметика для всех" (в 3-х томах). Раритет, дореволюционное издание.

Начала смотреть, сразу, конечно, нашла главу о магических квадратах.
Вот цитата из предисловия к этой главе:

Цитата:

Теория волшебных квадратов, казалось бы, стоит особняком в ряду иных отделов математики и имеет мало «практических» приложений. Тем не менее пренебрегать ею не следует. Над ней работали такие высочайшие математические умы, как Ферма, и с помощью её не раз приходили к самым удивительным и значительным открытиям.

Сразу приятно удивила общая формула пандиагональных квадратов 4-го порядка (в книге они называются полными). Я знаю общую формулу Бергхольта (она описана в моей статье "Общие формулы магических квдаратов"), но в книге другая формула.



Ссылки для скачивания книги выложила в разделе "Книги для общего доступа".

[Nataly-Mak]

И далее в книге приводится общая формула для пандиагональных квадратов 5-го порядка.
Затем формулы пандиагональных и обычных квадратов 8-го порядка.
Но всё это только для классических магических квадратов.

[Nataly-Mak]

Конкурс "Нетрадиционные пандиагональные квадраты" закончился, итоги я подвела в теме о конкурсе.
Теперь выкладываю свою статью о пандиагональных квадратах 9-го порядка:
http://www.natalimak1.narod.ru/pannetr3.htm

Мной получены достаточные условия, которым должен удовлетворять примитивный квадрат, чтобы из него можно было построить пандиагональный квадрат с помощью преобразования Россера. Эти условия оказались очень простыми. Интересно, что они в некотором смысле аналогичны условиям, которым должен удовлетворять примитивный квадрат для пандиагонального квадрата 8-го порядка. В примитивном квадрате 8х8 элементы первой строки и первого столбца должны образовывать четыре пары чисел с одинаковой суммой, а в примитивном квадрате 9х9 элементы первой строки и первого столбца должны образовывать три тройки с одинаковой суммой чисел.
Эти условия я увидела не сразу, помогла мне "анатомия" классического пандиагонального квадрата из статьи Россера. Разложив этот квадрат на два ортогональных латинских квадрата, увидела эти условия.
Но вот не знаю, являются ли эти условия и необходимыми для построения примитивного квадрата 9х9, из которого можно получить пандиагональный квадрат 9-го порядка преобразованием Россера.