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

[Mathusic]

Огромное спасибо!

[Pavlovsky]

maxal
shwedka
Огромное спасибо!!!! Не спешно разбираюсь с этой статьей. Заодно пишу перевод. Если кому интересно, готов поделится своими проблемами при понимании этой статьи и применении ее для построения пандиагональных квадратов.

-- Вс май 16, 2010 08:28:43 --

svb
У Россера достаточно простое доказательство невозможности построения традиционных пандиагональных квадратов из чисел от 1 до n^2.

В теореме 2.4 доказывается что пандиагональные квадраты порядка 2k можно разбить на 4 решетки L(2) по k^2 элементов в каждой. Причем сумма всех элементов в каждой решетке одинаковая!
Дальше моя интерпретация. То есть сумма всех элементов пандиагональных квадратов четных порядков должна делится на 4. Легко убедиться что для традиционных пандиагональных квадратов порядков n=4k+2, сумма всех элементов на 4 не делится.

[Nataly-Mak]

Pavlovsky
ваши исследования статьи Россера дали потрясающие результаты, о чём подробно рассказывается
на форуме Портала ЕН.

Один из самых важных результатов для меня на данный момент - найдено достаточное условие, которому должен удовлетворять массив из 49 чисел, чтобы из него можно было построить пандиагональный квдарат 7-го порядка.
Я уже написала программу проверки массивов на выполнение этого условия. Программа работает достаточно быстро.
Далее, получив из массива примитивный квадрат, с помощью преобразования мы легко получаем из него пандиагональный квадрат. Алгоритм получается замечательный.

Алгоритм этот, кстати, вы уже реализовали полностью для пандиагональных квадратов 5-го порядка. Для данного порядка построение примитивного квадрата из массива, состоящего из 25 чисел, является не только достаточным, но и необходимым условием построения пандиагонального квадрата из заданного массива.
В результате вы нашли наименьшие пандиагональные квадраты 5-го порядка из простых чисел (S = 395) и из смитов (S = 8318).

Спасибо вам за проделанную работу! Мне очень интересно всё, что есть ещё в этой статье. Буду очень благодарна за перевод статьи.

svb
в указанной статье Россера есть доказательство несуществования пандиагональных квадратов порядка n = 4k + 2 (k = 1, 2, 3, ....).

[Nataly-Mak]

На картинке показано преобразование примитивного квадрата 7-го порядка в пандиагональный квадрат.



Массив для примитивного квадрата я получила из произвольно выбранных натуральных чисел (чтобы только выполнялись условия теоремы). В массиве оказались одинаковые числа, но это не помешало построить пандиагональный квадрат.
Для получения из примитивного квадрата пандиагонального используется следующее преобразование:

B(3i+2j,2i+j)=A(i,j),

где A(i,j) - элементы примитивного квадрата, B(i,j) - элементы пандиагонального квадрата. Индексы вычисляются по модулю 7.

Примитивный квадрат обладает интересным свойством: сумма чисел во всех его диагоналях (главных и разломанных) равна магической константе квадрата.
Составив по программе примитивный квадрат для массива 1, 2, 3, ..., 49, я с удивлением обнаружила, что получился обратимый квадрат:

49 42 35 28 21 14 7
48 41 34 27 20 13 6
47 40 33 26 19 12 5
46 39 32 25 18 11 4
45 38 31 24 17 10 3
44 37 30 23 16 9 2
43 36 29 22 15 8 1

Интересно отметить, что программа трудилась над построением этого примитивного квадрата 4 часа! Массивы же из простых чисел проверяются примерно 30 секунд, а массивы из смитов - 2-3 секунды.
Уже проверила 20 массивов из последовательных простых чисел, 10 массивов из последовательных смитов, все наименьшие квадраты из простых и из смитов, ни из одного массива примитивный квадрат не составился.

[svb]

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

У Россера достаточно простое доказательство невозможности построения традиционных пандиагональных квадратов из чисел от 1 до n^2.

Статью скачал, приступил к чтению. Как маленький мальчик написал одному писателю: "Мне очень понравилась ваша книга, читаю второй месяц - уже на 4-ой странице".

[Pavlovsky]

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

читаю второй месяц - уже на 4-ой странице".

Я уже на пятой! Если что спрашивай. Може вместе быстрей пойдет изучение...
В данный момент бьюсь над Леммой 4.1. И почему из нее следует тривиальный вывод, что пандиагональных МК 3х3 не существует.

и вот над этим

Цитата:

The general solution of these equations, the elements being linear functions of a certain number of essential, independent parameters, shall be called the general square of order n admitting the given configurations.

Никак не могу понять что такое "general square". Как можно общее решение системы линейных уравнений, которое в данном случае прямоугольник сделать квадратом?!

[svb]

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

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

читаю второй месяц - уже на 4-ой странице".

Я уже на пятой! Если что спрашивай. Може вместе быстрей пойдет изучение...

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

Цитата:

Цитата:

The general solution of these equations, the elements being linear functions of a certain number of essential, independent parameters, shall be called the general square of order n admitting the given configurations.

Никак не могу понять что такое "general square". Как можно общее решение системы линейных уравнений, которое в данном случае прямоугольник сделать квадратом?!

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

По поводу "допускающих" в окончательной редакции можно найти более красивый термин.

[Pavlovsky]

С переводом у меня нет проблем есть проблемы с пониманием.

Мы вывели общую формулу. То есть у нас n^2 линейных функций от k переменных (количество независимых параметров). Общее решение можно представить ввиде прямоугольной таблицы n^2 на k. И вдруг этот прямоугольник называем квадратом! Мало того это не просто квдарат, а магический квадрат! Так как допускать (я перевел как покрывать) данные конфигурации может только магический квадрат.

[svb]

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

Мы вывели общую формулу. То есть у нас n^2 линейных функций от k переменных (количество независимых параметров). Общее решение можно представить ввиде прямоугольной таблицы n на k. И вдруг этот прямоугольник называем квадратом! Мало того это не просто квдарат, а магический квадрат! Так как допускать (я перевел как покрывать) данные конфигурации может только магический квадрат.

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

[Pavlovsky]

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

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

Это тема! Буду думать. Спасибо.

[Nataly-Mak]

Pavlovsky
Вот здесь
post317855.html#p317855
полученная мной общая формула пандиагонального квадрата 7-го порядка. Это формула типа 24+25, то есть 24 независимых элемента и 25 зависимых, которые определяются как линейные функции от 24 независимых элементов и магической константы квадрата.
Насколько я понимаю, вы обсуждаете как раз подобное задание магического квадрата.

[Pavlovsky]

Вроде разобрался. "General" совсем лишнее слово.
Лемма 4.1 в моем переводе звучит так:
В квадрате простого порядка допускающего (покрывающего) все пути, все элементы равны N. Где N это среднеарифметическое всех элементов таблицы. Россер не использует понятие магическая сумма. Но связь очевидна: S(Магическая сумма) = n*N.

Так как через каждый элемент может проходить не более n+1 путей, то для n=3 получаем случай из леммы. И соответственно пандиагональный квадрат 3х3 может состоять только из матрицы с одинаковыми элементами.

[Pavlovsky]

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

Pavlovsky
Вот здесь
post317855.html#p317855
полученная мной общая формула пандиагонального квадрата 7-го порядка. Это формула типа 24+25, то есть 24 независимых элемента и 25 зависимых, которые определяются как линейные функции от 24 независимых элементов и магической константы квадрата.
Насколько я понимаю, вы обсуждаете как раз подобное задание магического квадрата.

Наталья, вроде как с этим вопросом разобрались. general square, по версии svb, можно перевести как обобщенный квадрат. То есть квдрат в ячейках которого вместо чисел стоят формулы.

-- Пн май 17, 2010 08:53:36 --

Следующая проблема относится к теореме 3.1, где описывается преобразование примитивного квадрата в пандиагональный. Как создавать такое преобразование для конкретных n, разобрался кроме одного случая. Для n=6, невозможно создать подобное преобразование. Толи чего то не понял, толи n=6 исключение, для которого методика Россера не применима.

[Nataly-Mak]

Цитата:

Следующая проблема относится к теореме 3.1, где описывается преобразование примитивного квадрата в пандиагональный. Как создавать такое преобразование для конкретных n, разобрался кроме одного случая. Для n=6, невозможно создать подобное преобразование. Толи чего то не понял, толи n=6 исключение, для которого матодика Россера не применима.

Как сообщала на форуме Портала ЕН, у меня для порядка 6 не построился примитивный квадрат (я взяла набор чисел, из которого пандиагональный квадрат составляется - последовательные простые числа 67, ..., 251).
Так что, у меня пока нечего и преобразовывать - нет примитивного квадрата порядка 6. А у вас есть? Если взять, например, примитивный квадрат из набора 1, 2, ..., 36 (это будет обратимый квадрат), то его бестолку пытаться преобразовывать, потому что классического пандиагонального квадрата 6-го порядка не существует.

А для других порядков вида n = 4k + 2 тоже разобрались? Для порядка 10, например. Может быть, исключение составляют все порядки данного вида, а не только порядок 6?

-- Пн май 17, 2010 08:49:48 --

Тестирую свою программу построения примитивного квадрата порядка 7. Для набора из первых 49 натуральных чисел, как я уже сообщала, она нашла примитивный квадрат, им оказался обратимый квадрат.
Теперь ввела в качестве массива числа арифметической прогрессии: 3, 13, 23, ...., 483. Программа для этого набора тоже примитивный квадрат построила.
В этом квадрате числа также записаны по порядку, как в обратимом квадрате.
В общем, программа вроде работает правильно. Осталось найти примитивный квадрат из простых чисел.

Прверила уже 140 массивов из последовательных простых и 70 массивов из последовательных смитов. Нет примитивного квадрата!

[Pavlovsky]

maxal

Ты вроде занимался проблемой возможности (невозможности) построения пандиагональных МК 4х4 из последовательных простых чисел. Как у тебя дела в этом направлении?
Тоже решил поковыряться в этом направлении.

Пандиагональные МК 4х4 должны состоять из 8 пар комплементарных чисел с одинаковой суммой. То есть пока можно забыть про магические квадраты и решить задачу из теории (простых) чисел.

Задача. Найти 16 последовательных простых чисел, образующих 8 пар комплементарных чисел.

Среди 50 миллионов первых простых чисел такой последовательности не нашел.

Ниже представлены все последовательности 14-ти последовательных простых чисел образующих 7 пар комплементарных чисел, среди первых 50 миллионов простых чисел.
Первое число медиана (половина суммы пары комплементарных чисел). Следующие 7 чисел смещение, для образования пары комплементарных чисел надо медиану сложить и вычесть со смещением.

8021811 10 20 22 40 52 58 62
20066025 2 16 22 38 62 64 82
62550600 11 17 19 23 29 37 43
102979590 29 37 47 59 71 73 83
110608470 1 19 29 31 47 73 79
136450140 11 59 61 67 77 91 107
162607725 4 26 34 52 62 64 76
353656545 2 28 56 62 68 76 92
390175935 4 8 14 22 34 52 56
489539985 2 16 28 58 68 98 104
591815055 2 14 16 28 44 68 74
593566935 2 14 56 58 62 64 98
609486540 17 29 31 43 53 71 73
622696515 2 16 22 26 44 52 62
633778593 26 40 44 50 64 76 86
683850999 10 32 38 88 100 110 122
783914670 13 17 29 37 43 47 53
951212625 4 16 28 32 56 58 74

Может пригодится следующее тривиальное утверждение. Пусть даны различные простые числа (p1,p2,…,pk). Тогда последовательность из чисел не делящихся на заданные простые числа содержит бесконечное число комплементарных чисел, с медианами кратными p1*p2*…*pk/2.