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

[Pavlovsky]

Хочешь обмануть законы алгебры? Пандиагональный квадрат описывается 4N уравнениями с N^2 переменными. Как не крути эти равенства, количество независимых переменных останется одним и тем же.

[dmd]

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

Хочешь обмануть законы алгебры? Пандиагональный квадрат описывается 4N уравнениями с N^2 переменными. Как не крути эти равенства, количество независимых переменных останется одним и тем же.

В том то и дело, что это первоначальное описание квадрата переопределённой нерешённой системой. Решение показывает, что реальное количество степеней свободы квадрата меньше N^2, а именно 24 для квадрата 7х7. Вот и возникла мысль - может система всё еще не дорешена и количество степеней свободы еще меньше?

[tolstopuz]

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

Вот и возникла мысль - может система всё еще не дорешена и количество степеней свободы еще меньше?

Если систему еще "дорешать", степеней свободы может стать только больше, так как выяснится, что некоторые уравнения следуют из других. А вообще достаточно посчитать ранг одной конкретной матрицы 49x49, чтобы дальшейшие вопросы отпали.

[Nataly-Mak]

tolstopuz в сообщении #747550 писал(а):

А вообще достаточно посчитать ранг одной конкретной матрицы 49x49, чтобы дальшейшие вопросы отпали.

Вообще-то, для N=7 всё давно посчитано. Выше приведена и система линейных уравнений, описывающая пандиагональный квадрат
7-го порядка, и её решение, сделанное вполне корректно в каком-то пакете математических программ (систему решал 12d3).
В решении 24 независимых переменных при заданной магической константе и 25 - в случае, когда магическая константа тоже неизвестна.
Ничего здесь перерешать уже невозможно.

Кроме того, чуть выше svb привёл формулу размерности пространства пандиагональных квадратов для различных N.

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

[Nataly-Mak]

Интересен такой момент.
Для классических пандиагональных квадратов 7-го порядка формула может иметь не 24 независимых переменных, а всего 12, по той причине, что классический квадрат составляется из пар комплементарных чисел.
Пример классического пандиагонального квадрата 7-го порядка нерегулярного по Россеру я приводила выше (из статьи Россера).
Ещё пример - пандиагональный квадрат, построенный мной:

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

Идея такая: из пар комплементарных чисел можно строить не только идеальные магические квадраты, можно строить и просто пандиагональные.
В применении к простым числам можно ли что-то получить из этой идеи?
Другими словами, вопрос звучит так: можно ли из пар комплементарных простых чисел построить не идельный, а просто пандиагональный магический квадрат
Если ответ на этот вопрос положительный, тогда следующий вопрос:
может быть, построение не идеального, а просто пандиагонального квадрата из пар комплементарных простых чисел даст лучшие решения, нежели то решение, которое удалось найти alexBlack для идеального квадрата 7-го порядка (S=5411)
Я эту идею ещё не пробовала, она только что пришла мне в голову.
Можно это попробовать не только для N=7.
Ближайший кандидат - квадрат порядка N=9.
По формуле svb получаем, что для N=9 будет 48 независимых переменных.
Если строить квадрат из пар комплементарных чисел, независимых переменных будет всего 24.
Чтобы знать, какие переменные будут составлять пары комплементарных чисел, надо взять для образца любой классический пандиагональный (но не идеальный) квадрат 9-го порядка.

Вспомним, что идеальный квадрат 9-го порядка alexBlack удалось построить по общей формуле (здесь приводилась ссылка на его статью о построении этого квадрата). Значит, это реально. Однако магическая константа в решении alexBlack S=24237. Нам надо улучшить это решение для пандиагонального (не идеального) квадрата.

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

[Nataly-Mak]

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

Цитата:

27 .48 Michael Marchenko Jakarta, Indonesia 20 Jul 2013 09:09

Молодец, ни одного конкурса не пропускает

Jarek, как всегда на месте...
Это действительно на грани фантастики. Неужели никто больше не может додуматься до его супералгоритма?

[Nataly-Mak]

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

Идея такая: из пар комплементарных чисел можно строить не только идеальные магические квадраты, можно строить и просто пандиагональные.

Решила попробовать реализовать эту идею, ну очень интересно
Классические пандиагональные квадраты 7-го порядка, конечно, строила раньше; для этого существует много разных методов. Но вот по общей формуле не строила ещё.

Легко ли построить нерегулярный классический пандиагональный квадрат 7-го порядка подобный тому, который приведён в статье Россера? Вот этот квадрат:

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

Написала программу, запустила. С волнением ждала результат. Ждать пришлось довольно долго. Но он построился! Это надо показать



Чем этот пандиагональный квадрат подобен квадрату из статьи Россера? Тем, что в нём пары комплементарных чисел расположены точно так, как в этом квадрате.
Много ли будет таких подобных квадратов? Не знаю, прервала программу, полный перебор будет выполняться очень долго.

[Тут следует отметить один нюанс: когда мы строим классический магический квадрат и выполняем перебор по некоторой схеме, он выполняется намного дольше, чем из простых чисел (по той же схеме); а из простых чисел перебор выполняется намного дольше, чем из чисел Смита. Это уже много раз подтверждено экспериментально.]

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

[Nataly-Mak]

Хотя в моей программе пандиагональность квадрата проверяется, на всякий случай проверяю построенный квадрат в программе mertz, вдруг что-то не проверила, пропустила.
Для классических квадратов "проверялка" очень хорошая, так как все числа изображаются.



Да, забыла сказать: квадрат я строила по общей формуле пандиагонального квадрата 7-го порядка, которая приведена выше. Однако независимых переменных у меня получилось не 24, а всего 14 (засчёт комплементарных пар чисел). Почему 14, а не 12? Наверное, это зависит от того порядка, в котором вычисляются зависимые переменные. При выбранном мной порядке получилось 14 независимых переменных. Интересно, можно ли выбрать такой порядок, чтобы независимых переменных было 12?
Поскольку мы строим квадрат из набора комплементарных пар чисел, нам известна константа комплементарности $K$ и известна магическая константа квадрата $S$.
для квадратов 7-го порядка имеем:
$S=7K/2$

P.S. Так как обе иллюстрации не очень чёткие, покажу построенный мной квадрат:

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

-- Вс июл 21, 2013 06:29:52 --

В OEIS есть последовательность A073523.

Цитата:

A set of 36 consecutive primes that form a 6 X 6 pandiagonal magic square with the smallest magic constant (930).

Классный квадратик! Найден давно.
По конкурсу этот квадратик тянет на 0,48 балла
Трое конкурсантов, видимо, ввели это решение.

А вот пандиагональные квадраты порядков 4 и 5 из последовательных простых чисел не найдены (насколько мне известно).

Задача века!

В теме "Магические квадраты" были попытки построить такие квадраты.
Для квадрата 4-го порядка maxal проверил простые числа до какого-то огромного значения (не помню уж). Не складывается квадрат и всё тут.

Можно к этой задаче века прибавить ещё построение пандиагонального квадрата 7-го порядка из последовательных простых чисел. Может быть, с квадратом 7-го порядка удачнее будет. Вот же для порядка 6 квадрат составился.
Надо попробовать. Тут потенциальные массивы из 49 чисел найти несложно. Далее берём общую формулу и вперёд. Можно привлечь построение по шаблону.

-- Вс июл 21, 2013 06:43:37 --

В конкурсе, проведённом на этом форуме, была задача о построении наименьших пандиагональных квадратов 4-го и 5-го порядков из последовательных простых чисел:

Цитата:

Задача №1

Известен наименьший пандиагональный квадрат 6-го порядка из последовательных простых чисел
(смотрите последовательность A073523).
Построить наименьшие пандиагональные квадраты из последовательных простых чисел порядков 4 и/или 5.

Примечание: магический квадрат называется наименьшим, если он имеет минимальную константу из всех подобных магических квадратов. Поиск пандиагонального квадрата порядка 4 из последовательных простых чисел выполнял М. Алексеев. Проверены простые числа в интервале до 7,5 триллионов натуральных чисел. Квадрат не найден.

Задача не решена.

[Nataly-Mak]

На конкурсе сегодня выходной?

Не даёт покоя вопрос: сколько будет независимых переменных, если пандиагональный квадрат 7-го порядка строить из пар комплементарных чисел
Почему у меня получилось 14 независимых переменных? Так ли это на самом деле или это зависит от порядка вычислений?
Хочу описать квадрат, построенный из комплементарных пар чисел, и решить эту систему уравнений. Тогда будет всё ясно.
Квадрат взяла тот же самый - из статьи Россера.
$k$ - константа комплементарности (сумма чисел в комплементарной паре). Для классического квадрата $k=50$.

Элементы в квадрате расположила:

x1 x2 x3 x4 x5 x6 x7
k-x5 x8 x9 x10 x11 k-x9 x12
x13 x14 x15 x16 k-x4 k-x3 k-x11
k-x12 k-x14 x17 x18 k-x7 k-x6 x19
x20 x21 k-x16 k-x15 x22 k-x2 k-x1
x23 k-x18 k-x10 k-x22 k-x8 k/2 k-x21
x24 k-x19 k-x24 k-x20 k-x13 k-x17 k-x23

Tеперь надо написать систему уравнений, описывающую этот пандиагональный квадрат и решить её.
Напомню:
$k=2S/7$
где $S$ - магическая константа квадрата.

dmd
Вольфраматика, в которой вы решаете системы уравнений, - это у вас установленная программа? Или это тоже онлайн, как и Вольфрамальфа?
У меня ещё одна система намечается для решения

[Nataly-Mak]

Система уравнений, описывающая пандиагональный квадрат 7-го порядка, построенный из пар комплементарных чисел (по образцу классического квадрата из статьи Россера):

x1+x2+x3+x4+x5+x6+x7=7k/2
x8-x5+x10+x11+x12=3k/2
x13+x14+x15+x16-x4-x3-x11=k/2
x12+x14-x17-x18+x7+x6-x19=k/2
x1+x2-x20-x21+x16+x15-x22=k/2
x10-x23+x18+x22+x8+x21=2k
x13+x19+x20+x17+x23=5k/2
x1-x5+x13-x12+x20+x23+x24=3k/2
x2+x8+x21-x18-x19=k/2
x3+x9+x15+x17-x16-x10-x24=k/2
x4+x10+x16+x18-x15-x22-x20=k/2
x4-x5-x11+x7-x22+x8+x13=k/2
x2+x3+x9+x17=2k
x1-x7-x12+x11-x19+x21+x23=k/2
x1+x8+x15+x18+x22-x23=2k
x4-x7+x9+x16-x24=k/2
x3-x1-x12+x7+x15+x10+x19=3k/2
x6-x2+x5+x11+x24=3k/2
x3+x13+x19-x2-x20=k/2
x4+x9+x14-x12-x1-x13=0
x5+x10+x15-x14+x20-x21-x17=k/2
x6+x11+x16+x17+x21=5k/2
x5-x7-x14+x15+x8=k/2
x14-x6-x12+x16+x22=k/2
x9-x5+x11+x12-x21+x10+x20=3k/2
x4+x11-x3+x19+x20-x18-x24=k/2
x1-x3-x10+x4+x6-x23+x19=k/2
x9+x16-x7-x21+x24=k/2

Помогите, пожалуйста, решить, у кого есть возможность.
Очень интересно: сколько будет независимых переменных.

[dmd]

 k = 2 x5 + 2 x7 - 2 x9
 x6 = 4 x7 + x8 - 4 x9
 x4 = 2 x5 + 3 x7 - x8 - 3 x9
 x3 = 2 x5 - 2 x7 + x9
 x24 = 2 x5 - x8
 x23 = 2 x7 - x9
 x22 = 6 x7 - 5 x9
 x21 = 2 x5 - 3 x7 - x8 + 3 x9
 x20 = 2 x5 - 3 x7 + 2 x9
 x19 = x5 - 2 x7 + 2 x9
 x18 = x2 - 2 x7 + 2 x9
 x17 = -x2 + 2 x5 + 6 x7 - 6 x9
 x16 = x5 - x7 + x9
 x15 = 2 x5 + x7 - x8 - x9
 x14 = 2 x5 - x7
 x13 = x2 + 2 x7 - 2 x9
 x12 = 2 x5 - x7 - x8 + x9
 x11 = x2 - x7 + x9
 x10 = -x2 + 2 x5 + 5 x7 - 5 x9
 x1 = -x2 + 2 x5 + x7 - x9

Если $k$ задано, то 4. Если не задано, то 5.

[Nataly-Mak]

Невероятно!
Всего 4 независимых переменных при заданном $k$?!
Это же грандиозно! Программа будет мухой летать. А у меня сейчас в программе 14 независимых переменных. 4 и 14 - это же небо и земля.
Даже не верится, что так мало независимых переменных. Сейчас буду проверять, не вкралась ли где ошибка...

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

P.S. И уже сразу мысли побежали к квадрату порядка 9. Но сначала надо до конца разобраться с квадратом порядка 7. Если полученная формула верная, то:
1. мы имеем отличную формулу для построения классических пандиагональных квадратов, побобных квадрату и статьи Россера;
2. возможно, по этой формуле можно строить и нетрадиционные пандиагональные квадраты 7-го порядка (в том числе и из простых чисел). Это надо проверить. Но, как мне кажется, ничто этому не мешает.

-- Пн июл 22, 2013 09:01:42 --

На квадрате из статьи Россера формулу проверила, всё получилось.
Сейчас ещё проверю на построенном мной квадрате, но сомнений в правильности формулы уже почти не осталось.

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

[Nataly-Mak]

Фантастика!
dmd хотел, чтобы осталась одна независимая переменная.
Ну, одна не получилась, зато 4 получилось
Программу написала, запустила. Если вчера первого квадрата мне пришлось ждать несколько часов, по этой программе квадрат построился мгновенно! Есть разница между 14 и 4 независимыми переменными. Ёжик это понимает

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

Этот квадрат не такой, как квадрат в статье Россера, и не такой, как у меня построился вчера.
Пока вот только классический пандиагональный квадрат. Сейчас буду пробовать строить по этой программе квадраты из простых чисел.

Никак не могу понять, почему так мало независимых переменных. Квадрат что ли у Россера какой-то особенный?

-- Пн июл 22, 2013 12:45:59 --

Попробовала построить несколько квадратов, поставила счётчик.
Первые 6 квадратов построились тоже мгновенно

(Оффтоп)

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

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

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

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

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

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

Итак, с пунктом 1 разобралась полностью: имеем отличную формулу для построения классических пандиагональных квадратов 7-го порядка.

[Nataly-Mak]

Начала пробовать построение квадрата из простых чисел.
Интересные эксперименты, однако.

Да-а-а-а...чтобы из простых чисел всё сложилось по такому гениальному (в своей простоте) сценарию - это надо, чтобы очень крупно повезло.

Пока только такой полуфабрикат:

 0  0  3251  0  2657  0  1583 
 3617  0  1103  0  0  5171  0 
 0  0  0  0  0  3023  0 
 0  0  0  0  4691  0  0 
 0  0  0  0  0  0  0 
 2063  0  0  0  0  3137  0 
 0  0  0  0  0  0  4211 
S=21959 

Но программа работает очень быстро. В показанном примере имеется 70 пар комплементарных чисел ($k=6274$), проверяется за несколько секунд. Полного решения не находит.

Сейчас попробую из произвольных натуральных чисел построить по этой формуле.

-- Пн июл 22, 2013 14:33:41 --

Из произвольных натуральных чисел строится запросто. Ввела массив натуральных чисел, задала константу комплементарности $k=150$, квадрат построился мгновенно:

130  19  145  142  74  13  2 
 76  9  1  134  18  149  138 
 21  146  140  73  8  5  132 
 12  4  135  17  148  137  72 
 144  136  77  10  7  131  20 
 3  133  16  143  141  75  14 
 139  78  11  6  129  15  147
S=525

Вот вам и разница в аддитивных свойствах у произвольных натуральных чисел и у простых чисел!
Продолжать эксперименты для N=7, или попробовать получить аналогичную формулу для N=9?
Коллеги, ау! Куда все пропали?

Тут ещё такой важный момент имеется: с ростом порядка квадрата недостаточно хорошие аддитивные свойства чисел немного компенсируются увеличением количества слагаемых. Это я в своё время очень хорошо прочувствовала.
Смотрите: в квадрате 7-го порядка цепочки складываются из 7 чисел, а в квадрате 9-го порядка они складываются из 9 чисел, а в квадрате 19-го порядка цепочки составляются аж из 19 чисел.

[Nataly-Mak]

Проанализировала ситуацию с N=7. Если даже квадрат из простых чисел по данной формуле и существует в природе, то его магическая константа никак не может быть меньше 1597. Значит, здесь нечего ловить.
Надо переходить сразу к N=17 Поскольку мы имеем пока в наличии квадрат порядка 17 с очень огромной магической константой, возможно, здесь что-то и можно будет получить.