Дьявольские магические квадраты из простых чисел

[Nataly-Mak]

dmd
большое спасибо.

[dimkadimon]

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

Я уже перевела 4 отрывка из этой темы (перевожу наиболее важные сообщения).

А какой смысл переводить Google Translate когда тему уже можно читать с переводом от Google? Например вот перевод последней страницы этого форума:
http://www.google.com/translate?hl=en&i ... 7-210.html

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

По Россеру, квадрат порядка 10 можно разбить на 4 множества чисел, которые будут иметь одинаковую сумму. Но не откуда не следует, что эти группы чисел должны составлять пандиагональный квадрат 5х5.

Не вижу как это помогает. Ведь надо не только найти 4 группы чисел с одинаковой суммой, но ещё поставить их так чтобы получился 10х10 пан-диагональный квадрат. Гораздо проще использовать 5х5 пан-диагональные квадраты с одинаковой суммой.

-- 18.07.2013, 09:33 --

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

Россер лемма 4.2
Число определяющих, независимых переменных в обобщенном квадрате Sp простого порядка, допускающих r наборов путей равно p^2-(p-1)r.
p - порядок квдарата; r - в случае пандиагональных квадратов равно 4.

Спасибо, то что надо! Значит если мы возмём любой NxN и S и заполним первые 4 строчки до колонки (N-1) тогда все остальные числа можно вычислить по формуле.

[Nataly-Mak]

dimkadimon в сообщении #747022 писал(а):

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

Я уже перевела 4 отрывка из этой темы (перевожу наиболее важные сообщения).

А какой смысл переводить Google Translate когда тему уже можно читать с переводом от Google? Например вот перевод последней страницы этого форума:
http://www.google.com/translate?hl=en&i ... 7-210.html

Я перевожу не всё подряд, а выборочно, самые важные сообщения.

Помню, был случай, когда mertz жаловался, что не мог перевести в Google одну из страниц темы. Видимо, проблемы с перводом целой страницы иногда возникают. Я это не пробовала, не в курсе.

Когда я предложила AZ выложить всю тему в удобном для чтения формате pdf, он ответил, что надо сделать перевод на английский язык, тогда он может это выложить в дискуссионной группе.
И я приняла решение переводить самые важные сообщения. AZ это одобрил. В дискуссионной группе был задан вопрос: имеет ли смысл делать такие отрывки. Высказался только один участник группы. Мне этого достаточно. Значит, переводы кому-то нужны.

И ещё такой нюанс: при переводе фрагментов в Google я обнаружила, что пропускаются некоторые изображения (а изображения - это не только картинки, это и многие формулы, записанные в TeX. Я переведённый фрагмент просматриваю и пропущенные изображения вставляю. Думаю, что это немаловажно.

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

По Россеру, квадрат порядка 10 можно разбить на 4 множества чисел, которые будут иметь одинаковую сумму. Но не откуда не следует, что эти группы чисел должны составлять пандиагональный квадрат 5х5.

Цитата:

Не вижу как это помогает. Ведь надо не только найти 4 группы чисел с одинаковой суммой, но ещё поставить их так чтобы получился 10х10 пан-диагональный квадрат. Гораздо проще использовать 5х5 пан-диагональные квадраты с одинаковой суммой.

Ну да, гораздо проще, когда числа этих 4-х групп образуют пандиагональные квадраты 5х5. Никто с этим не спорит. Однако, как уже сказано, с таким методом дальше решения S=3594 вряд ли удастся продвинуться.
Я уже привела здесь ссылку на тему, где показывала работу этого алгоритма для N=6.
Использовать 4 группы чисел, которые имеют одинаковую сумму, но не образуют пандиагональные квадраты, - это более общий метод. Не утверждаю, что он может дать лучшие решения, но... ведь никто ещё не попробовал.
Можно и для N=8 этот метод пробовать. 4 решётки по 16 чисел.

-- 18.07.2013, 09:33 --

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

Россер лемма 4.2
Число определяющих, независимых переменных в обобщенном квадрате Sp простого порядка, допускающих r наборов путей равно p^2-(p-1)r.
p - порядок квдарата; r - в случае пандиагональных квадратов равно 4.

Цитата:

Спасибо, то что надо! Значит если мы возмём любой NxN и S и заполним первые 4 строчки до колонки (N-1) тогда все остальные числа можно вычислить по формуле.

Как я поняла, приведённая Pavlovsky формула работает только для случаев, когда порядок пандиагонального квадрата N - простое число.

[Pavlovsky]

dimkadimon в сообщении #747022 писал(а):

Значит если мы возмём любой NxN и S и заполним первые 4 строчки до колонки (N-1) тогда все остальные числа можно вычислить по формуле.

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

-- Чт июл 18, 2013 07:57:05 --

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

формула работает только для случаев, когда порядок пандиагонального квадрата N - простое число.

Именно так. Для составных порядков, количество независимых переменных будет меньше чем вычисленное по формуле. Не помню точно где, в какой то теме посвященной пандиагональным квадратам, кто то пытался вывести формулу и для составных чисел. Так что эта тема открытая и интересная.

-- Чт июл 18, 2013 08:08:25 --

Цитата:

Россер лемма 4.2
Число определяющих, независимых переменных в обобщенном квадрате Sp простого порядка, допускающих r наборов путей равно p^2-(p-1)r.
p - порядок квдарата; r - в случае пандиагональных квадратов равно 4.

Если r=2, то это получается полумагический квадрат.
Чем хороша статья Россера, что она содержит максимально обобщенные результаты.
Вот хорошая тема на будущее. Построение супер пандиагональных квадратов. Скажем в которых допускается 5 (можно и больше) наборов путей. То есть одинаковую сумму должны иметь строки, колонки, разорванные диагонали, обратные разорванные диагонали. И плюс наборы линий, полученные ходом коня. Из статьи Россера следует супер пандиагонального квадрата 4х4 не существует. А вот квадраты 5х5 и более вполне возможны.

-- Чт июл 18, 2013 08:15:31 --

Благодря Горбачеву английский язык поплнился словом "perestroika"
Благодаря Наталии появилось слово "dostraivaniya"

[Nataly-Mak]

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

Чем хороша статья Россера, что она содержит максимально обобщенные результаты.

Не-а... не всё максимально обобщает
Например, Теорема 5.5 в статье рассмотрена только для классических пандиагональных квадратов и не обобщена на нетрадиционные пандиагональные квадраты.
Где алгоритм построения нетрадиционных пандиагональных квадратов 6-го порядка?
Ничего не сказано про ассоциативные примитивные квадраты, которые очень хороши для построения идеальных и совершенных магических квадратов, а это ведь тоже дьявольские квадраты!

-- Чт июл 18, 2013 07:32:53 --

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

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

формула работает только для случаев, когда порядок пандиагонального квадрата N - простое число.

Именно так. Для составных чисел, количество независимых переменных будет меньше чем вычисленное по формуле. Не помню точно где, в какой то теме посвященной пандиагональным квадратам, кто то пытался вывести формулу и для составных чисел. Так что эта тема открытая и интересная.

Возможно, это есть в теме "Магические квадраты". Этим вопросом занимался maxal. И формулы вроде были приведены.

[Pavlovsky]

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

И формулы вроде были приведены.

Если бы была приведена формула, я бы ее запомнил. А так запомилось, что пытались вывести формулу. Так что вроде проблема до сих пор открытая.

[Nataly-Mak]

Э-э-э...
Вот для идеальных квадратов maxal точно формулу приводил. Кажется, что и для пандиагональных тоже. Надо поискать в теме "Магические квадраты".

[Nataly-Mak]

Ой, залезла в тему "Магические квадраты", еле вылезла
Пока нашла только вот это:

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

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

Ради интереса посчитал ранги систем уравнений (то есть, по сути максимальное количество линейно независимых уравнений в системе) описывающих нетрадиционные идеальные квадраты. Для $n$ от 1 до 10 они получились равны:
1, 4, 9, 14, 21, 28, 37, 46, 57, 68

Для рангов справедлива формула:

$$\left\lfloor\frac{n^2 + 4n - 3}{2}\right\rfloor$$

[Pavlovsky]

Причем тут идеальные (или ассоциативные) квадраты? Ведь там вводятся дополнительные условия, что уменьшает количество независимых переменных.

[Nataly-Mak]

Чего вы возмущаетесь?
То, что вы говорите, и ежу понятно.
Пока нашла формулу только для идеальных квадратов. Надо дальше искать, как я помню, maxal приводил формулу и для пандиагональных квадратов.

P.S. Дополнительные условия не мешают идеальным квадратам быть пандиагональными
alexBlack построил именно идеальный квадрат 9-го прядка из различных простых чисел с более-менее приличной магической константой.
Идеальные квадраты строить намного проще именно из-за свойства ассоциативности, которым они обладают.

-- Чт июл 18, 2013 10:49:01 --

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

Россер лемма 4.2
Число определяющих, независимых переменных в обобщенном квадрате Sp простого порядка, допускающих r наборов путей равно p^2-(p-1)r.
p - порядок квдарата; r - в случае пандиагональных квадратов равно 4.

Для пандиагональных квадратов набор путей r равен 4 (строки, столбцы, диагонали двух направлений).
Но ведь в идеальном квадрате те же 4 набора путей, ибо он является пандиагональным.
А для идеальных квадратов эта формула не верна. Опять Россер недоработал

[svb]

Странно, разве с размерностью пространства пандиагональных квадратов еще остались неясности?
\dim \left( D \right) = \left\{ {\begin{array}{{20}c} {\left( {N - 2} \right)^2, {\rm }N = 2k} \\ {\left( {N - 3} \right)\left( {N - 1} \right),{\rm }N = 2k + 1} \\ \end{array}} \right. \

статья о дьявольских квадратах

[Nataly-Mak]

О, кто к нам пришёл!
svb
очень рада вас видеть.
Ну, вот и сразу внесли ясность в спорный вопрос
Я хорошо помню, что в теме "Магические квадраты" формула была. Кажется, она была и от maxal.
Вы свою формулу тоже выкладывали в теме, сейчас вспоминаю. Давно это было...

Надеюсь, что вы примете участие в конкурсе.
Стартовый капитал в 6.06 баллов доступен всем
Но хотелось бы увидеть новые решения проблемы, новые алгоритмы.

-- Чт июл 18, 2013 11:37:05 --

dmd в сообщении #746906 писал(а):

x16 = -x17 - x2 + x24 + x25 + x3 - x32 - x4 - x5 + x6 - x7 + 2 x8 + x9
x15 = x2 - x20 + x22 - x25 - x27 + 2 x31 + x4 - 2 x6 + x9
x14 = -x17 - x21 + x23 + x24 + x25 - x28 + x30 - x32 - x7 + x8 + x9
x13 = x2 - x20 + x24 - x27 + x31 - x6 + x9
x12 = -x2 - x21 + x24 + x25 + x26 - x30 - x32 - x4 - x5 + x6 + 2 x8 + x9
x11 = x18 - x2 - x20 + x27 - x29 + x8 + x9
x10 = -x17 + x19 - x2 - x21 + x24 + x25 + 2 x26 - x3 - x30 - 2 x32 - x4 + x6 + 2 x8 + x9
x1 = x2 - x3 + x4 + x5 - x6 + x7 - x8

А это общая формула ассоциативного квадрата Сенли 8-го порядка, который должен превратиться в совершенный магический квадрат с помощью моего преобразования.
Здесь вы видите только 32 переменных: x1, x2, x3, ..., x32. Остальные 32 переменные вычисляются по свойству ассоциативности:
$x_i=K-x_{65-i}$, 32<i<=64,
где K - константа ассоциативности квадрата Стенли.

Меня удивил тот факт, что в формуле вообще отсутсвует индекс квадрата Стенли (будущая магическая константа совершенного квадрата).
Формулу проверила для единственного известного мне ассоциативного квадрата Стенли 8-го порядка, который превращается в совершенный квадрат (индекс квадрата равен 24024):

19 83 1019 1583 3229 3793 4729 4793
103 167 1103 1667 3313 3877 4813 4877
499 563 1499 2063 3709 4273 5209 5273
523 587 1523 2087 3733 4297 5233 5297
709 773 1709 2273 3919 4483 5419 5483
733 797 1733 2297 3943 4507 5443 5507
1129 1193 2129 2693 4339 4903 5839 5903
1213 1277 2213 2777 4423 4987 5923 5987

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

Конечно, ассоциативный квадрат Стенли можно строить в лоб, основываясь только на определении квадрата Стенли. При этом, конечно, дополнительное условие для этого квадрата надо преверять.
Не знаю, какой из путей более эффективный. Надо проверить оба пути.
Найти совершенный магический квадрат 8-го порядка из различных простых чисел с магической константой S<24024 пока не удаётся.

[Nataly-Mak]

Jarek работает

Цитата:

1 15.00 Jarek Wroblewski Wroclaw, Poland 18 Jul 2013 12:30

Почти целый месяц непрерывно улучшает решения. Невероятно, но факт.

-- Чт июл 18, 2013 17:32:23 --

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

Не знаю, какой из путей более эффективный. Надо проверить оба пути.
Найти совершенный магический квадрат 8-го порядка из различных простых чисел с магической константой S<24024 пока не удаётся.

Написала программу по приведённой формуле.
По заданному массиву ровно из 64 чисел (известный) квадрат построился за несколько секунд:

 19  83  1019  1583  3229  3793  4729  4793 
 103  167  1103  1667  3313  3877  4813  4877 
 499  563  1499  2063  3709  4273  5209  5273 
 523  587  1523  2087  3733  4297  5233  5297 
 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  0 
 S=24024 

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

Теперь надо попробовать выполнение программы для массива, содержащего все пары комплементарных чисел для заданной константы ассоциативности (а не точно 32 пары). Пар может быть и намного больше 32, что как раз чаще всего и бывает. Например, для константы ассоциативности K=6006 имеем 195 пар комплементарных простых чисел.
Если и для полного массива программа будет работать сносно, тогда можно поискать решение с индексом S<24024.

[Nataly-Mak]

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

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

Россер лемма 4.2
Число определяющих, независимых переменных в обобщенном квадрате Sp простого порядка, допускающих r наборов путей равно p^2-(p-1)r.
p - порядок квдарата; r - в случае пандиагональных квадратов равно 4.

Для пандиагональных квадратов набор путей r равен 4 (строки, столбцы, диагонали двух направлений).
Но ведь в идеальном квадрате те же 4 набора путей, ибо он является пандиагональным.
А для идеальных квадратов эта формула не верна.

Тут, наверное, не так.
В идеальном квадрате будет не 4 набора путей, их будет больше. Сколько?
Предположу, что их будет 6 (4 набора в пандиагональном квадрате плюс суммы центральносимметричных элементов; только сомневаюсь - это добавляет один набор или два набора путей). Тогда формула, пожалуй, будет верна.

[dmd]

Т.к. пандиагональный квадрат абсолютно симметричный относительно своих исходных формул сумм строк, столбцов и диагоналей, то формулы "24+25" для квадрата 7х7 должны выполняться при любом повороте и любом отражении квадрата относительно матрицы формул или наоборот формул относительно квадрата. Тогда выполнив три поворота и собрав четыре набора формул "24+25" в одну переопределённую систему линейных уравнений, её решением должна получиться схема "1+48". Т.е. независимой переменной должна остаться единственная ячейка в центре квадрата. Верна ли эта гипотеза?

Попробовал сделать один поворот. По моим первоначальным прикидкам в результате должны были остаться 12 независимых переменных. Но так не получилось - либо где-то запутался, либо исходно предположение ошибочно.