Программирование и магические квадраты

[Nataly-Mak]

Много лет занимаюсь исследованиями магических квадратов.
Эта интересная область даёт очень богатую почву для приложения программистских знаний и навыков.
Каждый алгоритм - это новая программа. От того, как она будет составлена, зависит, удастся ли построить магический квадрат с теми или иными свойствами.

О магических квадратах можно посмотреть в Википедии, а также на
моём сайте.

Приведу один пример.
Как построить идеальный магический квадрат 9-го порядка из простых чисел?
Это классический идеальный квадрат 9-го порядка, то есть квадрат, составленный из
первых 81 натуральных чисел:

Код: [Выделить]

3 15 68 76 61 36 44 47 19
34 45 53 20 1 12 69 77 58
10 66 78 59 31 43 54 26 2
40 52 27 8 11 64 75 60 32
65 73 57 33 41 49 25 9 17
50 22 7 18 71 74 55 30 42
80 56 28 39 51 23 4 16 72
24 5 13 70 81 62 29 37 48
63 35 38 46 21 6 14 67 79
Разработано несколько алгоритмов такого построения. Однако пока идеальный квадрат из простых чисел не найден.
Один из алгоритмов основан на общей формуле идеального квадрата.
Автор приведённой ниже общей формулы А. Чернов.

Код: [Выделить]

m0 = -m80+2/9*S
m1 = -m79+2/9*S
m2 = -m78+2/9*S
m3 = -m77+2/9*S
m4 = -m76+2/9*S
m5 = -m75+2/9*S
m6 = -m74+2/9*S
m7 = -m73+2/9*S
m8 = +m73+m74+m75+m76+m77+m78+m79+m80-7/9*S
m9 = -m71+2/9*S
m10 = -m70+2/9*S
m11 = -m69+2/9*S
m12 = -m68+2/9*S
m13 = -m67+2/9*S
m14 = -m66+2/9*S
m15 = -m65+2/9*S
m16 = -m64+2/9*S
m17 = +m64+m65+m66+m67+m68+m69+m70+m71-7/9*S
m18 = -m62+2/9*S
m19 = -m61+2/9*S
m20 = -m60+2/9*S
m21 = -m59+2/9*S
m22 = -m58+2/9*S
m23 = -m57+2/9*S
m24 = -m56+2/9*S
m25 = -m55+2/9*S
m26 = +m55+m56+m57+m58+m59+m60+m61+m62-7/9*S
m27 = -m28-m29-m30-m31-m32-m33-m34-m35+S
m28 = -m55+m60+m61+m62-m64-m65+m68+m69+2*m70+m71-m73-m74-m75+m76+m77+2*m78+2*m79+m80-8/9*S
m29 = -m56+m59+m60+m61-m64-m65-m66+m67+m68+2*m69+m70+m71-m73-2*m74+2*m77+2*m78+2*m79+m80-8/9*S
m30 = -m57+m58+m59+m60-m65+2*m68+m69+m70-m73-m75+m76+m77+2*m78+m79+m80-8/9*S
m31 = +m57+m59+m65+m67+m69+m73+m75+m77+m79-8/9*S
m32 = +m56+m57+m58-m59+m64+m65+2*m66-m69+m74-2*m77-m78-2*m79-m80+1/9*S
m33 = +m55+m56+m57-m60+m65-2*m68-2*m69-2*m70-m71+m73+m74+m75-m76-m77-3*m78-2*m79-m80+10/9*S
m34 = -m57-m58-m59-m60-2*m61-m62+m64-m67-m68-2*m69-2*m70-m71+m73+m74-2*m77-2*m78-2*m79-m80+19/9*S
m35 = -m56-m57-m58-m59-m60-m61-m62-m66-m67-m68-m69-m70-m71-m76-m77-m78-m79-m80+19/9*S
m36 = -m37-m38-m39-m40-m41-m42-m43-m44+S
m37 = -m57-m58-m59-2*m60-2*m61-2*m62+m64+m65-m67-2*m68-3*m69-3*m70-2*m71+m73+2*m74+m75-m76-3*m77-4*m78-3*m79-2*m80+28/9*S
m38 = +m55+m56+m57-m59-m60-m61+m64+m65+m66-m67-3*m68-3*m69-3*m70-2*m71+2*m73+2*m74+m75-m76-3*m77-4*m78-4*m79-2*m80+19/9*S
m39 = +m56+m57-m59-m60+m64+2*m65+m66-m68-2*m69-m70+m73+m74-m76-2*m77-3*m78-3*m79-2*m80+10/9*S
m40 = +1/9*S
m41 = -m56-m57+m59+m60-m64-2*m65-m66+m68+2*m69+m70-m73-m74+m76+2*m77+3*m78+3*m79+2*m80-8/9*S
m42 = -m55-m56-m57+m59+m60+m61-m64-m65-m66+m67+3*m68+3*m69+3*m70+2*m71-2*m73-2*m74-m75+m76+3*m77+4*m78+4*m79+2*m80-17/9*S
m43 = +m57+m58+m59+2*m60+2*m61+2*m62-m64-m65+m67+2*m68+3*m69+3*m70+2*m71-m73-2*m74-m75+m76+3*m77+4*m78+3*m79+2*m80-26/9*S
m44 = -m55+m61-m64-m65+m69+m70-m73-m74-m75+m77+m78+m79+1/9*S
m45 = +m56+m57+m58+m59+m60+m61+m62+m66+m67+m68+m69+m70+m71+m76+m77+m78+m79+m80-17/9*S
m46 = +m57+m58+m59+m60+2*m61+m62-m64+m67+m68+2*m69+2*m70+m71-m73-m74+2*m77+2*m78+2*m79+m80-17/9*S
m47 = -m55-m56-m57+m60-m65+2*m68+2*m69+2*m70+m71-m73-m74-m75+m76+m77+3*m78+2*m79+m80-8/9*S
m48 = -m56-m57-m58+m59-m64-m65-2*m66+m69-m74+2*m77+m78+2*m79+m80+1/9*S
m49 = -m57-m59-m65-m67-m69-m73-m75-m77-m79+10/9*S
m50 = +m57-m58-m59-m60+m65-2*m68-m69-m70+m73+m75-m76-m77-2*m78-m79-m80+10/9*S
m51 = +m56-m59-m60-m61+m64+m65+m66-m67-m68-2*m69-m70-m71+m73+2*m74-2*m77-2*m78-2*m79-m80+10/9*S
m52 = +m55-m60-m61-m62+m64+m65-m68-m69-2*m70-m71+m73+m74+m75-m76-m77-2*m78-2*m79-m80+10/9*S
m53 = -m61-m62-m69-m70-m71-m77-m78-m79-m80+10/9*S
m54 = -m55-m56-m57-m58-m59-m60-m61-m62+S
m63 = -m64-m65-m66-m67-m68-m69-m70-m71+S
m72 = -m73-m74-m75-m76-m77-m78-m79-m80+S
В формуле всё просто, mi (i = 0, 1, 80) - это обозначения элементов квадрата, S - магическая константа квадрата.
Если магическая константа задана, то в формуле 24 независимых переменных.

Осталось по этой формуле написать программу, взять подходящий массив простых чисел и построить идеальный магический квадрат 9-го порядка из простых чисел.
Однако всё не так просто. Имеем 24 вложенных цикла, которые выполняются очень долго. Нужны оптимизации, какие-то идеи, позволяющие уменьшить время выполнения программы.
Хорошая задача для программистов!

[Nataly-Mak]

Сложная задача?

Я сейчас решаю задачу построения идеального квадрата 7-го порядка из простых чисел. Вчера удалось получить такой идеальный квадрат:

Код: [Выделить]

23 677 5153 5501 1301 2141 4643
5261 167 2543 5297 1427 281 4463
5381 383 1217 4373 3491 761 3833
5051 4733 83 2777 5471 821 503
1721 4793 2063 1181 4337 5171 173
1091 5273 4127 257 3011 5387 293
911 3413 4253 53 401 4877 5531
Магическая константа квадрата равна 19439.
Но пока не уверена в том, что это наименьший квадрат. Нижняя граница магической константы для идеального квадрата 7-го порядка из простых чисел равна 4487. Осталось проверить ещё несколько потенциальных массивов.
Квадрат построен по общей формуле А. Чернова.

[Данила]

а каково практическое применение этих квадратов?

[Nataly-Mak]

Математику-экстрасенсу могут пригодиться  

Если серьёзно: я не задаюсь вопросом практического применения. Есть сложные задачи, которые в изобилии возникают при исследовании магических квадратов. Решаю эти задачи, мне интересно, узнаю что-то новое, получаю результаты, которые ещё никто не получил (несколько моих авторских квадратов есть в OEIS). Разве это так уж мало?

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

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

[Nataly-Mak]

Моему коллеге А. Чернову удалось решить задачу построения идеального квадрата 9-го порядка из простых чисел. Это наименьший из найденных им квадратов:

Код: [Выделить]

5381 5189 5273 149 107 89 83 2633 5333 
977 449 443 419 5003 5039 5147 5153 1607 
1583 4787 3413 4877 653 1373 3089 2909 1553 
2699 3863 743 4127 2027 3767 1979 2609 2423 
2969 1709 3119 3389 2693 1997 2267 3677 2417 
2963 2777 3407 1619 3359 1259 4643 1523 2687 
3833 2477 2297 4013 4733 509 1973 599 3803 
3779 233 239 347 383 4967 4943 4937 4409 
53 2753 5303 5297 5279 5237 113 197 5Минимальность квадрата не доказана. Но результат, конечно, замечательный!
 
Смотрите страничку А. Чернова: