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

[Nataly-Mak]

Друг прислал книгу У. Болл, Г. Коксетер. Математические эссе и развлечения. – М.: Мир, 1986. Он выложил книгу на файлообменнике Народа; может быть, кто-то захочет скачать, вот ссылка для скачивания:

http://narod.ru/disk/14684506000/Boll%2 ... %2C%201986)(ru)(600dpi)(471s).djvu.html

Просмотрела немного книгу, конечно, больше всего остановилась на главе «Магические квадраты». В книге приводится общая формула для магического квадрата 4-го порядка. Цитата:

Цитата:

На рис. 7.18 показана общая схема Бергхольта для построения любых магических квадратов четвёртого порядка [14] (совершенных при a=b=d-c=1/2(A-B-C+d), симметрических при a+c=d=b-c и A+C=B+D).

Общая схема, изображённая на рис. 7.18 выглядит так:

A-a  C+a+c  B+b-c  D-b
D+a-d     B   C   A-a+d
C-b+d    A   D   B+b-d
B+b   D-a-c   A-b+c   C+a

Пример (из книги), известный наименьший магический квадрат 4-го порядка из простых чисел и числа 1

3 71 5 23
53 11 37 1
17 13 41 31
29 7 19 47

получается при таких значениях: A=13, B=11, C=37, D=41, a=10, b=18, c=24, d=-2.
Но я так и не поняла, как же пользоваться этой формулой. Она похожа на формулу, приведённую в книге Ю. В. Чебракова (я приводила эту формулу). Если только лобовым перебором? Например, мы хотим построить магический квадрат из смитов по данной схеме. Тогда нам придётся по этой формуле перебирать все A, B, C, D – смиты, и все a, b, c, d – произвольные целые числа, затем вычислять каждый элемент по формулам и проверять, принадлежат ли полученные значения множеству смитов, а потом проверять суммы чисел в строках, столбцах и диагоналях квадрата.

[12d3]

Есть 2 новости, обе хорошие.
1) Найден квадрат из смитов 5-го порядка с минимальной константой 1636.

355  576  4  319  382  
454  85  391  648  58  
27  535  346  526  202  
706  166  378  121  265  
94  274  517  22  729  

2) Есть программа, которая находит все магические квадраты 5-го порядка из смитов с заданной магической константой. Чтоб она работала, надо в папку с программой положить файлик smith.txt с массивом смитов. В файле magic.txt будет список магических квадратов.
Программа

[Mathusic]

12d3 в сообщении #257980 писал(а):

Есть 2 новости, обе хорошие.
1) Найден квадрат из смитов 5-го порядка с минимальной константой 1636.

355  576  4  319  382  
454  85  391  648  58  
27  535  346  526  202  
706  166  378  121  265  
94  274  517  22  729  

2) Есть программа, которая находит все магические квадраты 5-го порядка из смитов с заданной магической константой. Чтоб она работала, надо в папку с программой положить файлик smith.txt с массивом смитов. В файле magic.txt будет список магических квадратов.
Программа

То есть, получается, квадрат Бодигрима не минимален?

[maxal]

Mathusic в сообщении #256330 писал(а):

Хотелось бы узнать какие диапозоны уже проверены на минимальные квадраты порядка $3,4,5,6$ из последовательных смитов?

Закончил поиск квадрата $3\times 3$ в интервале до $3\cdot 10^{10}$. Безуспешно.

[Mathusic]

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

Mathusic в сообщении #256330 писал(а):

Хотелось бы узнать какие диапозоны уже проверены на минимальные квадраты порядка $3,4,5,6$ из последовательных смитов?

Закончил поиск квадрата $3\times 3$ в интервале до $3\cdot 10^{10}$. Безуспешно.

Спасибо за информацию!
Ps. Трудный квадрат, однако... Может быть он найдётся в следующем миллиарде, а может не найдётся и в квадратильоне, или не существует вообще...

[Nataly-Mak]

12d3 в сообщении #257980 писал(а):

Есть 2 новости, обе хорошие.
1) Найден квадрат из смитов 5-го порядка с минимальной константой 1636.

Отличный результат! А наименьший магический квадрат 5-го порядка из последовательных смитов можно найти по вашей программе?
Можете рассказать, какой алгоритм в вашей программе? Этот алгоритм можно применить для построения наименьшего магического квадрата порядка 6 из смитов?

[Nataly-Mak]

12d3
Хотела проверить по вашей программе первые 9 кандидатов в наименьшие магические квадраты 5-го порядка из последовательных смитов, но программа у меня почему-то не скачалась.
Вот эти кандидаты:

 454, …, 861  S = 3269
535, …, 922  S = 3602
861, …, 1776  S = 6522
915, …, 1842  S = 7080
1086, …, 1894  S = 7825
1219, …, 1921  S = 8299
1376, …, 1966  S = 8854
1507, …, 2067  S = 9110
1872, … , 2409  S = 10544

Самый первый кандидат с магической константой 1516 отпадает автоматически, если минимальная константа квадрата 5-го порядка из смитов равна 1636.
Как я уже сообщала, моя программа не построила магический квадрат ни из одного приведённого массива. Однако моя программа не даёт точного ответа, возможна ошибка хотя и с малой вероятностью. А что “говорит” об этих квадратах ваша программа?

[12d3]

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

А наименьший магический квадрат 5-го порядка из последовательных смитов можно найти по вашей программе?

Можно, только пока не находится. Проверял числа до миллиона. Если не скачалась, то вот на народе.

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

Можете рассказать, какой алгоритм в вашей программе?

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

Nataly-M[quote="Nataly-Mak в сообщении #258127 писал(а):

Этот алгоритм можно применить для построения наименьшего магического квадрата порядка 6 из смитов?

Можно, только шибко долго работает. Пока что вообще ни одного квадрата не выдало. Авось, вам повезет больше. Вот программа. Кстати, вы можете давать во входном массиве не обязательно 36 чисел, а сколько угодно.

[Nataly-Mak]

12d3 в сообщении #258247 писал(а):

Nataly-M[quote="Nataly-Mak в сообщении #258127 писал(а):

Этот алгоритм можно применить для построения наименьшего магического квадрата порядка 6 из смитов?

Можно, только шибко долго работает. Пока что вообще ни одного квадрата не выдало. Авось, вам повезет больше.

Насколько я поняла из описания вашего алгоритма, в нём отсутствует элемент "везения"
Вот в моём первоначальном алгоритме (с генерацией набора из $n$ строк случайным образом) такой элемент действительно присутствует. Может повезти, а может - и нет. И мне много раз повезло - магический квадрат был найден. Самое большое везение было, когда мне удалось построить магический квадрат 10-го порядка из последовательных смитов. Правда, потом выяснилось, что он не наименьший. Совместными с ice00 усилиями удалось получить подобный магический квадрат и из первого кандидата.
Спасибо, что выложили программы. Но теперь, после вашего сообщения, мне уже они вряд ли понадобятся. У меня маленький массив смитов, а вы уже проверили квадрат 5-го порядка из последовательных смитов до миллиона. Да, похоже, что с квадратами из последовательных смитов порядков 3 - 9 придётся помучиться
Другие участники могут попробовать по вашим программам искать квадраты порядков 5 и 6 из смитов.

[dezdlisa]

Nataly, выложите пожалуйста, все 833 строки, полученные вами для шестого квадрата и все наборы по четыре строки. Интересно взглянуть. Может быть нужно искать не все строки, а достаточно только строк с неповторяющимися элементами?

[Nataly-Mak]

Напоминаю, что для тестирования своего алгоритма я взяла массив смитов, из которого магический квадрат 6-го порядка уже построен:

 22 94 346 382 562 778 1822 1966 2326 2362 2578 2902 20362 20506 20542 20974 21226 21262 681817 682177 682393 682609 682681 682897 1446106 1446142 1446178 1446538 1446574 1446934 3003898 3004186 3004402 3004618 3004654 3004762

Ваше предложение брать не все оригинальные строки, а только строки с неповторяющимися числами, неверно. Надо брать именно все оригинальные строки, иначе мы не получим всех возможных наборов по 4 строки.
В этом файле лежат 833 оригинальных строк, полученных по моей программе. Сумма чисел в строках равна магической константе квадрата – $5156763$. Числа в строках следуют в порядке возрастания. Вот начало этого файла:

 22  1822  20542  682681  1446934  3004762 
 22  1822  20974  682393  1446934  3004618 
 22  1822  20974  682609  1446574  3004762 
 22  1822  20974  682609  1446934  3004402 
 22  1822  21226  682393  1446538  3004762 
 22  1822  21226  682897  1446142  3004654 
 22  1822  21226  682897  1446178  3004618 
 22  1822  21262  682681  1446574  3004402 
 22  1822  21262  682897  1446106  3004654 
 22  1822  21262  682897  1446142  3004618 
 22  1822  21262  682897  1446574  3004186 
 22  1966  20506  682681  1446934  3004654 
 22  1966  20542  682681  1446934  3004618

В этом файле лежат 340 наборов из 4 строк. Как я уже говорила, это не все возможные наборы, их будет больше на самом деле. Не хочется исправлять ошибку в программе, хотя вижу её (технически довольно канительно исправлять программу, а смысла нет). Но не намного больше (не в разы).
Вот начало файла с наборами:

 22  1822  20542  682681  1446934  3004762 
 94  1966  20974  682897  1446178  3004654 
 346  2326  20506  682393  1446574  3004618 
 382  2362  21262  681817  1446538  3004402 

 22  1822  20974  682393  1446934  3004618 
 94  1966  20506  682897  1446538  3004762 
 346  2362  20542  682681  1446178  3004654 
 382  2326  21262  681817  1446574  3004402 

 22  1822  20974  682609  1446574  3004762 
 94  1966  21226  682681  1446142  3004654 
 346  2326  20362  682177  1446934  3004618 
 382  2362  20542  682897  1446178  3004402

Будет очень интересно, если кто-нибудь получит из этих 833 строк все возможные оригинальные наборы из 4 строк и сообщит, сколько же их на самом деле. Далее по формуле $n*24*720^4$ можно посчитать, сколько будет всех вариантов наборов по 4 строки (здесь $n$ – количество оригинальных наборов).
Среди всех вариантов наборов обязательно должен быть такой набор:

1822 21226 682897 1446538 3003898 382
3004762 681817 778 2326 1446574 20506
1446142 2902 3004654 20542 346 682177
21262 1446178 1966 562 682393 3004402

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

[12d3]

Есть магический квадрат 6-го порядка с константой 2787.

22  4  895  526  1255  85  
355  728  27  1165  391  121  
382  778  454  517  94  562  
576  634  654  319  166  438  
690  378  274  58  535  852  
762  265  483  202  346  729  

Получен с помощью исправленной версии программы из массива

562, 690, 483, 27, 391, 634, 852, 378, 438, 382, 202, 535, 121, 517, 274, 166, 1255, 454, 22, 94, 85, 1165, 526, 895, 576, 346, 778, 728, 355, 4, 654, 762, 729, 319, 58, 265

[Nataly-Mak]

Есть совершенный магический квадрат 4-го порядка из простых чисел! Известен ли такой квадрат? Если кто встречал, дайте, пожалуйста, ссылку.
***
Разобралась в общей алгебраической формуле Бергхольта магического квадрата 4-го порядка (приведена выше). Интересно использование этой формулы для построения пандиагонального (для квадрата 4-го порядка это значит также – совершенного) квадрата. Для пандиагонального квадрата общая формула имеет такой вид (получается из формулы, приведённой в книге с использованием указанных условий):

 A-a C+a+c B+a-c D-a
D-c   B   C   A+c
C+c  A   D   B-c
B+a   D-a-c  A-a+c  C+a

при этом должно выполняться ещё условие: 2a = A – B – C + D. Здесь $A$, $B$, $C$, $D$ – натуральные числа, $a$ и $c$ – целые числа не равные нулю.
Составила программу для этой схемы. Для простых чисел получила совершенный квадрат мгновенно:

11 157 41 199
167 73 137 31
163 5 193 47
67 173 37 131

Если учесть внутреннюю логику этой схемы и составленной по этой схеме программы, вроде бы это наименьший пандиагональный квадрат 4-го порядка из простых чисел (магическая константа квадрата, построенного по данной схеме равна: $A+B+C+D$). Магическая константа этого квадрата равна 408.
А вот совершенный квадрат из смитов не получился! Надо расширять массив смитов, я использовала в своей программе массив из 50 чисел.

В этой ветке показан пандиагональный квадрат 6-го порядка из простых чисел. Известны ли пандиагональные квадраты других порядков из простых чисел? Предлагаю создать новую серию магических квадратов – пандиагональные квадраты из простых чисел (а также из смитов). Из простых чисел у нас уже есть пандиагональные квадраты порядков 4 и 6. Из смитов пока вроде бы неизвестно ни одного пандиагонального квадрата.

-- Чт ноя 05, 2009 15:48:24 --

12d3 в сообщении #258561 писал(а):

Есть магический квадрат 6-го порядка с константой 2787.

22  4  895  526  1255  85  
355  728  27  1165  391  121  
382  778  454  517  94  562  
576  634  654  319  166  438  
690  378  274  58  535  852  
762  265  483  202  346  729  

Получен с помощью исправленной версии программы из массива

562, 690, 483, 27, 391, 634, 852, 378, 438, 382, 202, 535, 121, 517, 274, 166, 1255, 454, 22, 94, 85, 1165, 526, 895, 576, 346, 778, 728, 355, 4, 654, 762, 729, 319, 58, 265

Ура!!!
Значит, я не зря ожидала, что магический квадрат с такой константой будет. И массив вроде тот же самый, который я приводила.
Но это ведь ещё не наименьший квадрат?

-- Чт ноя 05, 2009 16:16:21 --

12d3
Вот нашла в черновиках ещё один полумагический квадрат с константой $2787$. Он построен из другого массива. Проверьте, пожалуйста, если это нетрудно, получится ли из этого массива магический квадрат.
Вообще я получила море полумагических квадратов с константой $2787$ из разных массивов, но все эти квадраты уже, конечно, давно удалила. Хорошо, что вот в записях остались два квадратика.
Вот полумагический квадрат:

588 378 985 27 454 355
265 895 121 706 274 526
22 636 166 825 576 562
535 346 922 517 85 382
648 438 202 58 483 958
729 94 391 654 915 4

[Mathusic]

Как сообщил нам товарищ maxal, он проверил $30 \cdot 10^9$ натуральных чисел на квадрат $3 \times 3$ из смитов. Я проверил затем следующие $\ge 682 \cdot 1000000$. Результата нет.
$\operatorname{maxal}$, а Вы начали проверку дальше?

[Nataly-Mak]

12d3
Программа супер! Проверила сейчас, работает, выдаёт много магических квадратов (пишет: найден магический квадрат), прервала программу, так как не знаю, сколько времени она будет выполняться. В выходном файле имею море магических квдаратов. Вот самый первый:

4  958  706  22  895  202  
576  58  588  355  562  648  
483  166  729  636  382  391  
274  526  378  825  346  438  
535  94  265  922  517  454  
915  985  121  27  85  654 

Это из того полумагического квадрата, который я только что привела.

-- Чт ноя 05, 2009 17:21:14 --

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

861  958  346  915  355  438  
654  378  690  636  663  852  
778  634  645  728  706  382  
535  729  913  576  666  454  
562  648  762  391  588  922  
483  526  517  627  895  825

Магическая константа равна $3873$.

-- Чт ноя 05, 2009 17:37:30 --

И ещё один из произвольных смитов, с магической константой $2472$:

729  4  636  762  22  319  
27  663  654  526  85  517  
391  645  58  378  438  562  
382  346  454  121  634  535  
355  648  94  483  627  265  
588  166  576  202  666  274

Сейчас ещё попытаюсь уменьшить.