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

[veestrib]

Наталья, здравствуйте - у вас очень интересные работы.

У меня очень узкая практическая задача - построение квадратов 4 на 4 (5 и 6), из чисел от 1 до 24 при том что числа могут повторяться! Условие разных чисел не вводится.

Могли бы Вы посоветовать программу если такие есть или литературу если встречали по решению таких задач?

Задачи постоянно такие - что есть набор 14-ти любых чисел от 1 до 24 в том числе повторяющихся, при этом 2 числа неизвестно (до 16ти полных) нужно подобрать 2 числа таким образом, чтобы составить из набора магический квадрат или максимальное приближение - полумагический, четверть магический.

Самые в лоб - это конечно перебор, но возможно есть какие то математические приближения, предпосылки - помогающие решать такие задачи. Предпроверки и отсев вариантов по четности, чтобы не проверять заведомо ложные и др.

[Nataly-Mak]

veestrib в сообщении #751385 писал(а):

У меня очень узкая практическая задача - построение квадратов 4 на 4 (5 и 6), из чисел от 1 до 24 при том что числа могут повторяться! Условие разных чисел не вводится.

Вам требуется строить нетрадиционные магические квадраты, ибо классические магические квадраты порядка $n$ составляются из различных натуральных чисел от 1 до $n^2$.
Существуют общие формулы магических квадратов (на моём сайте есть серия статей на эту тему). Вы можете воспользоваться такими формулами.
Специальных программ (или литературы) для такой задачи я не встречала.

[Jarek]

Regarding problem of finding a pandiagonal magic square of size 4x4, with consecutive primes as entries, I have determined the following:

There exist exactly 3 numbers n below 192*47# such that all the 16 numbers n+d, where d = 0, 10, 12, 18, 22, 28, 30, 40, 42, 52, 54, 60, 64, 70, 72, 82, are prime:

78830573871633653539 (20 digits)
94505039351105832919 (20 digits)
110732011215202177249 (21 digits)

In all 3 cases the 16 primes are in fact consecutive primes.

Each of those 16-element sets of primes can be used to construct a pandiagonal magic square.

A smaller example can be constructed using
n=7410890552945019583 (19 digits), where n+d (d = 0, 6, 10, 16, 18, 24, 28, 34, 60, 66, 70, 76, 78, 84, 88, 94) are consecutive primes.

[Nataly-Mak]

Jarek
грандиозно!
А вы уверены, что последний квадрат действительно наименьший?

[Jarek]

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

Jarek
грандиозно!
А вы уверены, что последний квадрат действительно наименьший?

I have just found a smaller one:

n = 320572022166380880 (18 digits)
d = 0, 6, 10, 16, 18, 24, 28, 34, 60, 66, 70, 76, 78, 84, 88, 94

No, I cannot claim it is the smallest. But soon I may be able to determine whether it is the smallest with this particular set of d's.

-- Вс авг 04, 2013 19:03:55 --

I have verified: for this set of d's this is the only n below 64*43# = 837296725226881920 = 8.37*10^17, for which all n+d are prime.

[Deggial]

Jarek, замечание за неоформление формул $\TeX$ом.
Убедительная просьба оформлять формулы $\TeX$ом, в противном случае посты будут снесены в Карантин.

[Nataly-Mak]

Jarek
я составила пандиагональный квадрат из последнего нормализованного массива:

0 88 16 84
76 24 60 28
78 10 94 6
34 66 18 70

Осталось ко всем элементам прибавить первое простое число в этом массиве.

[Jarek]

Jarek в сообщении #751885 писал(а):

$n = 320572022166380880$ (18 digits)

Sorry, I copied the central number instead of the lowest one. Should be 320572022166380833.

[Nataly-Mak]

Ага, и тогда получается такой пандиагональный квадрат 4-го порядка из последовательных простых чисел:

320572022166380833 320572022166380921 320572022166380849 320572022166380917
320572022166380909 320572022166380857 320572022166380893 320572022166380861
320572022166380911 320572022166380843 320572022166380927 320572022166380839
320572022166380867 320572022166380899 320572022166380851 320572022166380903

Может быть, это ещё не наименьший

[maxal]

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

Моя программка дошла уже до 7.5 триллионов, но пандиагонального МК 4х4 из последовательных простых так и не нашла.

С подачи Nataly-Mak продолжил поиск минимального пандиагонального МК 4x4 из последовательных простых чисел - и он нашёлся:

170693941183817 170693941183933 170693941183949 170693941183981
170693941183979 170693941183951 170693941183847 170693941183903
170693941183891 170693941183859 170693941184023 170693941183907
170693941183993 170693941183937 170693941183861 170693941183889

Этот МК составлен из 16 последовательных простых чисел, начиная с 170693941183817 (см. A245721). Если его вычесть из остальных, то квадрат приобретает вид:

0, 116, 132, 164, 
162, 134, 30, 86, 
74, 42, 206, 90, 
176, 120, 44, 72

[Nataly-Mak]

Ради такого случая сделаю сообщение

Прежде всего,
maxal
примите мои поздравления!

Далее, интересно, что мы с коллегой на форуме ПЕН тоже сегодня нашли решение.

Это наименьший ассоциативный квадрат Стенли 4-го порядка из последовательных простых чисел, полученный из набора, найденного коллегой:

0  30  44  74  
42  72  86  116  
90  120  134  164  
132  162  176  206
 
K= 206, S= 412 

Это сам набор простых:

170693941183817: 0 30 42 44 72 74 86 90 116 120 132 134 162 164 176 206

И наименьший пандиагональный квадрат 4-го порядка, полученный из этого квадрата Стенли:

170693941183817 +
0 176 74 162
116 120 42 134
132 44 206 30
164 72 90 86

S=2731103058942720

Попрошу вас отправить ваше решение в две головоломки:

http://www.primepuzzles.net/puzzles/puzz_723.htm - пандиагональные квадраты из последовательных простых чисел
http://www.primepuzzles.net/puzzles/puzz_736.htm - ассоциативные квадраты Стенли из последовательных простых чисел

Спасибо, что приняли участие в решении задачи!

Да, коллега проверил числа в интервале до 200 \cdot 10^{12}. Второго решения в этом инервале не найдено.
Тема на форуме ПЕН
http://e-science.ru/forum/index.php?sho ... 45280&st=0

[Nataly-Mak]

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

И наименьший пандиагональный квадрат 4-го порядка, полученный из этого квадрата Стенли:

170693941183817 +
0 176 74 162
116 120 42 134
132 44 206 30
164 72 90 86

S=2731103058942720

Исправляюсь...
Почему-то нашла не магическую константу квадрата, а сумму всех составляющих его чисел, от радости
Магическая константа $S=682775764735680$.

Ну, и скажу пару слов о следующей проблеме - поиске пандиагонального квадрата 5-го порядка из последовательных простых чисел.
Я писала об этой проблеме довольно много в теме "Антимагические квадраты". Пыталась искать решение. Проверила все простые числа в интервале [$3, 2\cdot10^9$].
Решение не найдено.
В теме "Антимагические квадраты" Jens K Andersen весьма пессимистически высказался о возможности построения такого квадрата. Такое же мнение высказал и Jarek в личной переписке.
Ну, трудно не значит невозможно.

Пандиагональный квадрат 4-го порядка из последовательных простых чисел тоже казалось очень трудно найти. Сначала был найден такой квадрат с очень большой магической константой. Задача минимизации решения надолго забуксовала, но её всё же решили. Решается то, что решается.

[Nataly-Mak]

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

Попрошу вас отправить ваше решение в две головоломки:

http://www.primepuzzles.net/puzzles/puzz_723.htm - пандиагональные квадраты из последовательных простых чисел
http://www.primepuzzles.net/puzzles/puzz_736.htm - ассоциативные квадраты Стенли из последовательных простых чисел

Решение в головоломках появилось.
Спасибо, maxal

[maxal]

Если кому-то интересно, то вот слайды моего сегодняшнего доклада на конференции MathFest 2014:
An efficient backtracking method for solving a system of linear equations over a finite set with application for construction of magic squares

[Nataly-Mak]

maxal
А почему вы переселили меня в Томск? (если я правильно прочитала английский текст)

Как я поняла, пандиагональный квадрат 5-го порядка из последовательных простых чисел так и не найден. Вы уже выполнили проверку до $10^{14}$?