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

[svb]

В Вашем конкретном случае $ H=100 $, $V=186$, $p=-66$. Получаем $x=(186+100-162-66)/2=29$

[Nataly-Mak]

Да! Всё правильно.

Но теперь будет легче. Сейчас 13-ый цикл уберу и посмотрю, что мне программа скажет

[maxal]

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

1 1 3 1 1 5
5 1 5 5 1 1
5 1 5 1 5 1
5 5 5 5 5 5
1 5 1 1 5 5
1 5 5 5 1 1

Вы писали, что это единственный шаблон с точностью до изоморфизма и умножения на -1.
Но вот мой шаблон № 2:

1 1 3 1 1 5
1 5 5 1 5 1
5 1 5 1 5 1
5 5 5 5 5 5
5 1 1 5 1 5
1 5 5 5 1 1

Разве мои шаблоны № 1 и № 2 изоморфны?

Циклически сдвиньте шаблон № 2 на один столбец вправо и зеркально отразите результат относительно центральной вертикальной оси - получите шаблон № 1.

[svb]

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

Используя статистику и программу поиска отклонений, нашла замечательный комплект отклонений:

-12 -84 -6 18 78 12 -72 -24 -66

Ну, насколько он замечательный, покажет проверка по программе построения пандиагонального квадрата 6-го порядка из 9 квадратов 2х2 с такими отклонениями.
Количества пар для этих отклонений хорошие, самое меньшее - 6 пар (для отклонения -84), наибольшее - 17 пар (для отклонения 78).
Всё это для магической константы 486.

Только что прочитал. Но, кажется, Вы немного ошибаетесь - у меня пар получилось больше:

-6: (5,151) (7,149) (17,139) (19,137) (29,127) (43,113) (47,109) (53,103) (59,97) (67,89) (73,83) : 11
6: (5,163) (11,157) (17,151) (19,149) (29,139) (31,137) (37,131) (41,127) (59,109) (61,107) (67,101) (71,97) (79,89) : 13
-12: (11,139) (13,137) (19,131) (23,127) (37,113) (41,109) (43,107) (47,103) (53,97) (61,89) (67,83) (71,79) : 12
12: (7,167) (11,163) (17,157) (23,151) (37,137) (43,131) (47,127) (61,113) (67,107) (71,103) (73,101) : 11
-18: (5,139) (7,137) (13,131) (17,127) (31,113) (37,107) (41,103) (43,101) (47,97) (61,83) (71,73) : 11
18: (7,173) (13,167) (17,163) (23,157) (29,151) (31,149) (41,139) (43,137) (53,127) (67,113) (71,109) (73,107) (79,101) (83,97) : 14
-24: (7,131) (11,127) (29,109) (31,107) (37,101) (41,97) (59,79) (67,71) : 8
24: (5,181) (7,179) (13,173) (19,167) (23,163) (29,157) (37,149) (47,139) (59,127) (73,113) (79,107) (83,103) (89,97) : 13
-66: (7,89) (13,83) (17,79) (23,73) (29,67) (37,59) (43,53) : 7
66: (5,223) (17,211) (29,199) (31,197) (37,191) (47,181) (61,167) (71,157) (79,149) (89,139) (97,131) (101,127) : 12
-72: (7,83) (11,79) (17,73) (19,71) (23,67) (29,61) (31,59) (37,53) (43,47) : 9
72: (5,229) (7,227) (11,223) (23,211) (37,197) (41,193) (43,191) (53,181) (61,173) (67,167) (71,163) (83,151) (97,137) (103,131) (107,127) : 15
-78: (5,79) (11,73) (13,71) (17,67) (23,61) (31,53) (37,47) (41,43) : 8
78: (7,233) (11,229) (13,227) (17,223) (29,211) (41,199) (43,197) (47,193) (59,181) (61,179) (67,173) (73,167) (83,157) (89,151) (101,139) (103,137) (109,131) (113,127) : 18
-84: (5,73) (7,71) (11,67) (17,61) (19,59) (31,47) (37,41) : 7
84: (5,241) (7,239) (13,233) (17,229) (19,227) (23,223) (47,199) (53,193) (67,179) (73,173) (79,167) (83,163) (89,157) (97,149) (107,139) (109,137) : 16

Перебор действительно очень большой и будет странно, если не найдется решение

[svb]

Имеется еще одно полезное соотношение, которое использовалось раньше. Посмотрим на 4 квадрата, каждый из 9 элементов:

A  B
B' A'

и пусть этими же буквами обозначаются суммы входящих в них элементов. Но по условиям магичности $B'+A=B'+A'$, т.е. $A=A'$. Но с другой стороны $A+A'=9Sc+p1+...+p9$, откуда $A=(9Sc+p1+...+p9)/2$. Для рассматриваемого набора отклонений $A=651$. Получается, что 9-й элемент можно отсечь раньше, как и в предыдущей программе (в той программе прохождение 9-го элемента отмечалось значком "!").

[buba987]

А что вы ищете на 130 страницах? Уайлс доказал ВТФ кажется на 100 стр. Перельман - на 39 стр.

Предупреждение за оффтопик и разжигание флейма!

[Nataly-Mak]

maxal
спасибо, поняла.

svb
это, между прочим, ваша программа дала мне неверные результаты (например, для $Sb = 240$, отклонение 78, она выдала мне 17 пар; и ещё во многих случаях почему-то количество пар по вашей программе на 1 меньше).
Но я потом всё по своей программе пересчитала, потому что мне надо было все пары получить, а ваша программа мне дала только количества.
У меня получилось всё точно так же, как у вас. Так что тут никаких ошибок нет.

Однако легче не стало после того, как я убрала 13-ый цикл.
Программа шла 3 часа, за это время прошли полностью 2 круга всех 12 циклов (для I = 1, 2). Прервала. Можно продолжить с I=3. Но долго работает Переменная I пробегает 24 значения, вот представьте. Если на один полный цикл ушло в среднем полтора часа, то на 24 полных цикла надо 36 часов.

И всё это только для одного комплекта отклонений. А таких комплектов море!
Это надо для каждого комплекта прокрутить программу.
А вот такой вопрос на засыпку: если, к примеру, для одного комплекта отклонений квадрат не будет найден, не значит ли это, что он не будет найден ни для каких других комплектов отклонений? Скорее всего, не значит.
Вы говорите, что перебор большой. Да, пар достаточно. Но... я попробовала вручную понабирать по 18 пар из разных групп, пока программа крутилась. Что-то это плохо получается: слишком много повторяющихся чисел в разных группах и набрать все пары из различных чисел не очень-то получается.

В ваше последнее соотношение пока не вникла. Оно может чем-то помочь ускорить выполнение программы?

[svb]

Глядя на верхнюю половинку квадрата:

a1 a2 a3 b1 b2 b3
a4 a5 a6 b4 b5 b6
a7 a8 a9 b7 b8 b9

мы видим, что первая проверка идет только после назначения значений 5 независимым переменным, например $a1, a2, a3, b1, b2, (b3)$ - значение в скобках проверяется. Далее достаточно назначить значения 3-м элементам, например $a4, b4, a7, (b7)$. Следом еще 3 значения: $a5, a6, b5, (b6)$, затем 1 элемент: a8, (a9), (b8), (b9). Не знаю, как maxal находил лучший вариант, но мне кажется, что остальные эквивалентны этому.

[Nataly-Mak]

Ну так всё равно получается 12 элементов (циклов), только другой порядок назначения, что, наверное, поможет немного ускорить выполнение.
Я сначала беру 5 элементов первой строки (шестой проверяется), затем 5 элементов второй строки (шестой проверяется) и наконец два элемента третьей строки.

У maxal'а, как я понимаю, вообще 16 свободных переменных (по общей формуле), а не 12, как в вашем алгоритме.

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

[svb]

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

это, между прочим, ваша программа дала мне неверные результаты

Знаю такой баг, я в выложенном варианте допустил ошибку при выводе общей статистики, но выводимые значения перед началом перебора там правильные и на дальнейший перебор это не влияет, поэтому я и не стал об этом говорить. Когда я проверял программу, то при выводе значений $Sa, Sc, Sb$ программу поправил, а про общую статистику я вспомнил после выкладывания программы на народ - в общей статистике поэтому встречаются значения (не всегда) на 1 меньше . С большим объемом перебора я столкнулся на простых числах раньше, когда смотрел большие магические суммы, даже применял вероятностный выбор и другие способы. Мне просто памяти не хватало в TP7, но перед выкладыванием программы я откомпилировал в FPC, где память меня не ограничивает, и убрал все "штучки" - меня и так ругают за непонятный интерфейс . Для малых значений магических сумм выложенный вариант был "съедобным", но где-то я говорил об этой проблеме. Сейчас, когда я увидел Ваш вариант, то и без вычислений увидел этот большой объем. Нужно его как-то обходить, например искусственно урезать пары, хотя бы случайным образом, но ... если решения сразу не найдется, то всегда будут оставаться сомнения. Худший вариант это топтаться в одной зоне перебора, что происходит при попытке тотального перебора - лучше уж выкинуть некоторые пары, а по остальным производить полный перебор. Но как? Случайный выбор, изменяемый от запуска программы (randomize), не худший вариант и часто помогал раньше. Но наверняка возможны и другие критерии, пока не известные.

Может быть, вы поробуете прокрутить программу с этим комплектом отклонений? 

Обязательно, комплект хороший, но ... "как только", да и подумать не мешает прежде, чем пускаться в плавание. Вашу программу, за которую Вы на меня обиделись, я сначала ускорил в 20 раз за счет новенькой великолепной версии power basic (5.01 кажется), при этом даже не менял Вашего текста, пару строчек добавил только в начале. Эта версия на тестах уже обходит мой любимый TP7 и работает в Win32 - я в восторге. После ускорения программы я ее несколько часов погонял и заведомо перекрыл то, что Вы от меня требовали, но ... вот у Garik2 должно было по времени пройти.

-- Вт сен 07, 2010 18:23:23 --

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

Я сначала беру 5 элементов первой строки (шестой проверяется), затем 5 элементов второй строки (шестой проверяется) и наконец два элемента третьей строки.

На самом деле 5 и 3 - разница очень большая при переборе, тут потеря по времени не просто в разы, а может быть очень большой.

[Nataly-Mak]

svb
хотела сейчас изменить программу по вашим инструкциям о порядке назначения свободных элементов, но, к сожалению, не поняла зависимость между элементами.
1. этот пункт понятен, он совпадает с моими назначениями - 5 элементов первой строки, шестой определяется с помощью магической константы.

Далее вы пишете:
2. достаточно задать три элемента - a_4, b_4, a_7, по этим трём элементам определяется элемент b_7. Как определяется?
У меня ничего не получается. Из чего этот элемент определяется? Из каких зависимостей?

Интересно, что в построенном мной квадрате сумма этих 4-х элементов равна 324 = 2S_c, но это случайное совпадение. В известном пандиагональном квадрате из последовательных простых чисел с магической константой 930 (S_c = 310) эти 4 элемента равны соответственно: 139, 181, 241, 89 и сумма их равна 650, что не равно 2S_c.
А для следующих 4-х элементов - a_5, a_6, b_5, b_6 в построенном мной квадрате сумма равна 312, а в известном квадрате сумма этих 4-х элементов равна 610. Тут уже в обоих квадратах эта сумма не равна 2S_c.

Может быть, какая-то другая зависимость между этими четырьмя элементами?

[Nataly-Mak]

Дошло! Как до утки, на третьи сутки
b_7 = (S_1 - S_2 + p + S_c)/2
где S_1 и S_2 - известные суммы в столбцах квадрата 6х6.

Уже прогнала третий проход, прошёл за час и 20 минут.

Сейчас изменю программу и снова погоняю.

[svb]

$\left( {\begin{array}{*{20}c} {a1} \\ {a4} \\ {a7} \\ {Sc - p1 - b1} \\ {Sc - p4 - b4} \\ {Sc - p7 - b7} \\ \end{array}} \right)$
Откуда:
$b1 + b4 + b7 + p1 + p4 + p7 = a1 + a4 + a7$

[svb]

Пожалуй стоит изложить основные соотношения для пандиагональных квадратов 6-го порядка, о которых в последнее время идет речь на форуме. Боюсь, что вновь читающие оказываются в очень неудобном положении, встречая загадочные обозначения.

S - магическая сумма квадрата, сумма элементов в каждой строке, столбце и в любой из обобщенных диагоналей квадрата.

Sc - вспомогательная величина, равная S/3 для рассматриваемых квадратов 6-го порядка. Свои истоки берет от так называемых комплементарных пар и равная сумме элементов этих пар.

p1, p2, p3, p4, p5, p6, p7, p8, p9 - так называемые отклонения от комплементарности, величины, позволяющие обобщить понятие комплементарности на общий случай пандиагонального квадрата. С использованием некоторых свойств этих квадратов, которые были изложены в статье Россера, этот общий вид оказалось возможным представить в виде:
$\left( {\begin{array}{*{20}c} {a1} & {a2} & {a3} & {b1} & {b2} & {b3} \\ {a4} & {a5} & {a6} & {b4} & {b5} & {b6} \\ {a7} & {a8} & {a9} & {b7} & {b8} & {b9} \\ {Sc - p1 - b1} & {Sc - p2 - b2} & {Sc - p3 - b3} & {Sc + p1 - a1} & {Sc + p2 - a2} & {Sc + p3 - a3} \\ {Sc - p4 - b4} & {Sc - p5 - b5} & {Sc - p6 - b6} & {Sc + p4 - a4} & {Sc + p5 - a5} & {Sc + p6 - a6} \\ {Sc - p7 - b7} & {Sc - p8 - b8} & {Sc - p9 - b9} & {Sc + p7 - a7} & {Sc + p8 - a8} & {Sc + p9 - a9} \\ \end{array}} \right)$
Можно обратить внимание, что при таком представлении квадрат как бы состоит из 9 квадратов 2x2 вида
$\left( {\begin{array}{*{20}c} a & b \\ {b'} & {a'} \\ \end{array}} \right)$
при этом $a+a'=Sc+p$ и $b+b'=Sc-p$, откуда, в общем то, и возникли слова псевдокомплементарнось и отклонение от комплементарности. Оказалось, что 9 величин отклонений p не являются независимыми, а подчиняются простым соотношениям:
$p1+p5+p9=0$
$p3+p5+p7=0$
$p1-p6-p8=0$
$p9-p2-p4=0$
$p3-p4-p8=0$
$p7-p2-p6=0$
Среди этих соотношений только 5 независимы, т.е. среди 9 величин p независимыми оказываются 4, в чем легко убедиться, если взять величины p2, p4, p6, p8, через которые легко вычисляются остальные по приведенным соотношениям.

Вот и вся "теория".

[svb]

Небольшое, но важное дополнение.

Для того, чтобы представленный квадрат стал пандиагональным величины a и b должны просто обеспечить равенство сумм в каждой строке и в каждом столбце магической сумме S. Для этого достаточно выполнения условий:
$a1+a2+a3+b1+b2+b3=S$
$a4+a5+a6+b4+b5+b6=S$
$a7+a8+a9+b7+b8+b9=S$
$b1+b4+b7+p1+p4+p7=a1+a4+a7$
$b2+b5+b8+p2+p5+p8=a2+a5+a8$
$a1+a2+...+a9=(9Sc+p1+p2+...+p9)/2=3S/2-p5$