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

[Nataly-Mak]

Загрузила на сайт файл с упорядоченными семёрками для константы 3719.
Как уже говорила, их всего 26723.

Сейчас проделала эксперимент: взяла первую семёрку:

4 22 166 588 895 958 1086

и к ней по шагам добавляла следующие упорядоченные семёрки по программе.
Удивительно, но вчера при визуальном составлении набора я не ошиблась. По программе получился тот же самый набор из 5 строк! А шестую и седьмую строки уже не удалось прибавить: числа повторяются.

Теперь надо брать вторую семёрку массива и проделать то же самое по шагам. Пока не соображу, как полностью автоматизировать эту процедуру.
Для маленьких порядков всё просто было: вводила весь массив в программу и формировала нужные наборы. А массив всех семёрок у меня не лезет в программу, слишком большой.

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

Да, значит, пакет программ для построения ПМК 8-го порядка с константой 5856 никто не попробовал?

[12d3]

Я вроде доказал, что квадрат с константой 3719 получить нельзя. В доказательстве рассматривал остатки чисел по модулю 9, и варианты, как эти остатки могут стоять в квадрате. Сегодня вечером, наверно, напишу полное доказательство.

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

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

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

[Nataly-Mak]

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

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

Много их? Очень хотелось бы на них глянуть.

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

Думаю, что таких наборов не очень много, ибо случайная генерация у меня ещё не "поймала" ни одного такого набора. Пять строк формирует - и всё! Мёртво встаёт. Я через определённое количество попыток снова программу на начало отправляю и опять точно такой же результат. То есть программа зациклена, я её довольно долго гоняла - ничего.

[12d3]

Даже сейчас наверно успею написать.
Итак, очевидно приведенный набор с константой 3719 единственен. Если мы рассмотрим остатки чисел по модулю 9 в данном наборе, то увидим такое распределение остатков:
0 - 6 штук.
3 - 1 штука.
4 - 27 штук.
6 - 8 штук.
8 - 1 штука.
Остаток от нашей константы 3719 равен 2.
Теперь нам надо найти, какие наборы из 7 остатков могут давать в сумме остаток 2. Тут небольшой перебор, его можно провести ручками, можно на компьютере перебрать, я приведу сразу результат:

4 4 6 6 6 6 6
4 4 4 6 6 6 8
3 4 4 4 4 4 6
0 6 6 6 6 6 8
0 3 4 4 6 6 6
0 3 4 4 4 6 8
0 0 3 6 6 6 8
0 0 4 4 4 4 4
0 0 0 4 4 6 6
0 0 0 4 4 4 8
0 0 0 0 6 6 8
0 0 0 0 3 4 4
0 0 0 0 0 3 8

Всего получается 13 вариантов строчек.
Теперь надо выбрать 7 строчек так, чтобы суммарное кол-во остатков каждого типа в этих строчках было равно кол-ву остатков во всем наборе(указанному выше).
Я тут перебирал ручками, используя тот факт, что остатков 4 в наборе очень много. Получил всего один вариант набора из 7 строк.
4 4 6 6 6 6 6 - 2 штуки
0 0 4 4 4 4 4- 3 штуки
4 4 4 6 6 6 8- 1 штука
3 4 4 4 4 4 6 - 1 штука

(Оффтоп)

Небольшое отступление. Тут видно, что генерировать наборы из 7 строк надо, выбирая строчки из этих групп. А если делать перебор по всем строкам, это будет намного дольше. у меня сгенерировалось не менее 10000 наборов из 7 строк. Один из них:

4 22 438 483 825 861 1086 
58 85 627 645 690 762 852 
27 94 265 648 778 922 985 
121 166 274 576 729 895 958 
346 378 454 535 634 666 706 
202 319 517 636 654 663 728 
355 382 391 526 562 588 915 

Очевидно, такое же распределение должно быть для столбцов.
У нас должно быть три строки с нулями. и три столбца с нулями. Рассмотрим клетки, которые находятся в строках без нулей, но в столбцах с нулями. В этих клетках могут быть только четверки, ибо в столбцах с нулями, кроме нулей находятся только четверки. То есть получаем, что в каждой строке без нулей находится минимум 3 четверки, что противоречит найденному распределению остатков. То есть, даже ПМК построить из данного набора нельзя.

[Nataly-Mak]

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

Итак, очевидно приведенный набор с константой 3719 единственен...

Какой приведённый набор? Я что-то просмотрела?

[12d3]

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

Напомню, какой берётся массив: берём первые 49 смитов 4, ..., 985 и заменяем число 913 на число 1086.

[Nataly-Mak]

Основная идея доказательства понятна, в детали не вникала.
Итак, получается, что квадрата с константой 3719 не существует, следовательно, построенный мной квдарат с константой 3720 является наименьшим.

А можете аналогично попробовать доказать для теоретической минимальной константы квадрата из последовательных смитов? Она равна 4167. Массив последовательных смитов: 58, ..., 1165.
Существует ли такой квадрат?

[12d3]

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

А можете аналогично попробовать доказать для теоретической минимальной константы квадрата из последовательных смитов? Она равна 4167. Массив последовательных смитов: 58, ..., 1165.
Существует ли такой квадрат?

Проверил массивы с константами 4167 и 4500. С точки зрения остатков, ситуация абсолютно идентичная (массивы дают совершенно одинаковые наборы остатков, и константы тоже дают одинаковые остатки, что весьма удивительно). Так вот, получается, что для таких массивов даже набор из 7 строк построить нельзя, не говоря уже о ПМК.

[Nataly-Mak]

Да, это очень удивительные и интересные результаты.
Значит, задачу с квадратами 7-го порядка можно закрывать

Теперь остаются две задачи: наименьший квадрат порядка 4 из последовательных смитов и наименьший квадрат порядка 8 из произвольных смитов с константой 5856 (или же с константой 5858).

Для квадратов порядка 8 с константой 5856 есть не только наборы из 8 строк, но и ПМК строятся, хотя и очень мало.
Так что тут надо внимательно исследовать ПМК. Выяснять, почему они никак не хотят превращаться в магические квадраты. Все "хромые" на одну диагональ у меня получаются

[12d3]

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

Для квадратов порядка 8 с константой 5856 есть не только наборы из 8 строк, но и ПМК строятся, хотя и очень мало.
Так что тут надо внимательно исследовать ПМК. Выяснять, почему они никак не хотят превращаться в магические квадраты. Все "хромые" на одну диагональ у меня получаются

Я попробую с другого бока подойти - придумать, как эффективно генерировать побольше ПМК, и надеяться, что один из них превратится в магический квадрат.
Я чего-то тут не нашел(плохо искал наверно) наименьший найденный квадрат 8х8 из произвольных смитов. Можете привести его?

[ice00]

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

ice00
извините моё нетерпение: очень хочется узнать, что же получается с наборами из 7 упорядоченных семёрок для константы 3719. Имееются ли такие? Сколько их?

Sorry, don't see the forum yesterday.
It is not more necessary, but here is the confirmation:

[ice@localhost cpp3]$ ./out/pms7 -me1 -i/tmp/seq7
Method E1:
ORDER=7  MAGIC=3719
Found: 26723 combinations (0.0311092%)

time taken: <2sec

[Nataly-Mak]

12d3
Вот магический квадрат порядка 8 из произвольных смитов с магической константой 5861:

454  121  728 1219  517  535 1633  654
1581  438  265  852  666 1086   58  915
588  274  166 1111 1449  645  346 1282
913 1507  778  706  355  378  648  576
94  319 1626  825  729 1376  202  690
526 1284  391  762  895  958  562  483
27 1255  985    4 1165   22 1776  627
1678  663  922  382   85  861  636  634

Пропущены две константы: 5856 и 5858.
Далее с ходу построился квадрат с константой 5866, пропущена ещё константа 5863.

Да, я тоже пытаюсь с той же стороны действовать: настроить как можно больше ПМК в надежде, что какой-нибудь превратится в магический.
Вот даже выложила здесь пакет программ для построения ПМК

Как я уже писала, самое сложное в этом процессе - генерация набора из 8 строк. Иногда такой набор генерируется с первой попытки, но чаще его приходится ждать минут 15-20.
Может быть, вы придумаете более эффективный способ генерации наборов по 8 строк? Я пыталась это сделать закономерным способом (как для наборов из 7 строк), то есть опираясь на упорядоченные восьмёрки, программку написала вчера, но всё равно ещё дольше получается, потому что 8 переменных и 64 числа в массиве, циклы выполняются долго. Так что опять сейчас буду крутить случайную генерацию наборов и построение из них ПМК. Ещё не из всякого набора ПМК получается. Тут тоже нужна более эффективная программа, чтобы из набора строила ПМК наверняка, если такое вообще возможно. Я вот сделала прогон той же программы для отражённых наборов и ещё несколько ПМК получила. Всего у меня на сегодня 17 ПМК. Все они оригинальные, то есть получающиеся друг из друга перестановкой строк я отбрасываю, такие неинтересны, потому что дальше при превращении в магический квадрат всё равно строки будут переставляться.

ice00
вы не совсем поняли, о каких наборах из 7 упорядоченных семёрок я спрашивала. Вот о таких:

4 22 438 483 825 861 1086 
58 85 627 645 690 762 852 
27 94 265 648 778 922 985 
121 166 274 576 729 895 958 
346 378 454 535 634 666 706 
202 319 517 636 654 663 728 
355 382 391 526 562 588 915

Все упорядоченные семёрки я сама получила (они выложены на моём сайте, здесь есть ссылка). А затем надо было составить из этих упорядоченных семёрок набор из 7 штук, так чтобы все числа в наборе были различны.
Показанный набор вчера привёл 12d3. Он сообщает, что таких наборов получается много, более 10000.
Однако теперь задача составления таких наборов уже не актуальна, потому что 12d3 доказал, что магический квадрат с константой 3719 построить невозможно.

Теперь нужны аналогичные наборы из упорядоченных восьмёрок с константой 5856, много-много

[Nataly-Mak]

12d3
Кстати, я тут давала ссылку на файл, содержащий все найденные мной ПМК с константой 5856. Сейчас добавила в файл новые ПМК, всего их у меня уже 19 оказалось.
Файл тут.

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

[Nataly-Mak]

12d3
Я проанализировала вашим методом массив смитов для квадрата 8х8 с константой 5856.
Вот что у меня получилось:
остаток 0 (по модулю 9) дают 7 чисел, остаток 3 – 1 число, остаток 4 – 36 чисел, остаток 6 – 17 чисел, остаток 8 – 3 числа.
Магическая константа 5856 даёт остаток 6.

Далее я брала готовые ПМК и записывала их в виде остатков.
Обнаружила пока два вида ПМК.

Первый вид составляется из строк:

4 4 4 4 6 6 6 8 – 3 шт.
0 0 4 4 4 4 4 4 – 2 шт.
3 4 4 4 4 4 4 6 – 1 шт.
0 0 0 4 4 4 6 6 – 1 шт.
4 4 4 6 6 6 6 6 - 1 шт.

Второй вид составляется из строк:

4 4 4 4 6 6 6 8 – 2 шт.
0 0 4 4 4 4 4 4 – 2 шт.
3 4 4 4 4 4 4 6 – 1 шт.
4 4 4 6 6 6 6 6 – 2 шт.
0 0 0 4 4 4 4 8 – 1 шт.

Точно такое же распределение по столбцам. В одном ПМК строки формируются по первому виду, а столбцы - по второму.

Я ещё не все ПМК рассмотрела. Может быть, есть и другие виды.
Если продолжить анализ ПМК данным методом, может быть, удастся выяснить: возможно или невозможно получить из них магические квадраты.

Теперь, наверное, можно сделать программу быстрой генерации наборов из 8 строк или даже быстрой генерации ПМК. Сейчас подумаю над этим вопросом.

[svb]

Мне понравился подход 12d3. Для квадрата 8х8 с константой 5856, если я не ошибаюсь, существует всего 3 вида:

a   4 4 4 6 6 6 6 6
b   4 4 4 4 6 6 6 8
c   4 4 4 4 4 6 8 8
d   3 4 4 4 4 4 4 6
e   0 6 6 6 6 6 6 6
f    0 0 4 4 4 4 4 4
g   0 0 0 4 4 4 6 6

 6 3 4 4 4 4 4 4    3 4 4 4 6 4 4 4     3 4 4 4 4 6 4 4
 6 4 4 4 6 6 8 4    4 4 4 4 6 6 6 8     4 4 4 4 6 6 6 8
 4 4 4 4 6 6 6 8    4 4 4 4 6 8 8 4     4 4 4 4 6 4 8 8
 4 4 4 4 6 6 6 8    4 0 0 4 4 4 4 4     4 0 0 0 6 6 4 4
 4 6 4 4 6 6 6 6    4 0 0 4 4 4 4 4     4 0 0 4 4 4 4 4
 0 4 0 0 6 6 4 4    4 0 0 4 4 4 4 4     4 4 0 0 4 4 4 4
 0 4 4 0 4 4 4 4    6 6 6 0 6 6 6 6     4 4 6 4 6 6 6 6
 0 4 0 4 4 4 4 4    4 6 6 4 6 6 6 4     6 4 6 4 6 6 6 4
  d+3b+a+g+2f      d+b+c+3f+e+a        d+b+c+g+2f+2a

Для одного из видов я попробовал получить наборы строк, и это далеко не все наборы.

-- Сб апр 10, 2010 09:40:52 --

Ошибаюсь , вариант d+b+c+3f+e+a не проходит из-за столбцов.