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

[maxal]

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

Называя формулу Бергхольта более совершенной, я имела в виду то, что она даёт возможность строить также ассоциативные и пандиагональные квадраты (что я и сделала в своей статье). Ермаков в своей формуле построение таких квадратов не предусматривал.

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

[Nataly-Mak]

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

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

Это как раз очень важно!
Конечно, если по той и по другой формуле построить из данного массива абсолютно все магические квадраты, то они окажутся одинаковыми.
Но если ставить конкретно задачу построения пандиагонального квадрата (как, например, сейчас я решаю такую задачу для пандиагональных квадратов из последовательных простых чисел), то нужна специальная формула именно для построения пандиагональных квадратов. Формула Ермакова таковой не является.

Даже и формулой Бергхольта для пандиагональных квадратов пользоваться не совсем удобно для решения моей задачи, указанной выше. Поэтому я написала новую программу специально для проверки массива из 16 чисел на предмет построения пандиагонального квадрата. Сначала я нахожу обычные квадраты из последовательных простых (пока у меня их всего 5), а затем проверяю найденный массив по программе для пандиагонального квадрата.

Обе программы представлены выше. Программу для пандиагональных квадратов собираюсь модифицировать, уменьшить количество свободных переменных с 6 до 4.

[Nataly-Mak]

Программу модифицировать удалось. Теперь в схеме всего 4 свободных параметра, остальные 12 параметров вычисляются по этим 4 и магической константе квадрата. Программа работает очень быстро.
Теперь дело за массивами-кандидатами. Понятно, что такими кандидатами являются прежде всего обычные магические квадраты. Если из заданного массива даже обычный квадрат не строится, то понятно, что и пандиагональный не построится.

Если кого-то интересует схема построения пандиагонального квадрата 4-го порядка из массива, состоящего точно из 16 чисел, пишите, выложу.

[svb]

О пандиагональных квадратах 4 порядка

s+a+b+c+d  s-a-b+c-d  s+a-b-c+d  s-a+b-c-d
s-a-b-c+d  s+a+b-c-d  s-a+b+c+d  s+a-b+c-d
s-a+b+c-d  s+a-b+c+d  s-a-b-c-d  s+a+b-c+d
s+a-b-c-d  s-a+b-c+d  s+a+b+c-d  s-a-b+c+d

если s=17/2, (a,b,c,d)=любая перестановка из (1/2, 2/2, 2/4, 8/2) с любыми знаками то получаем 24*16=384 обычных пандиагональных квадратов, с точность до поворотов и симметрии 48

-- Сб фев 20, 2010 20:12:19 --

Аналогично, ассоциативные квадраты 4 порядка:

s+a+b+c+d  s-a-b-c+d  s+a-b-c-d  s-a+b+c-d
s-a-b+c-d  s+a+b-c-d  s-a+b-c+d  s+a-b+c+d
s-a+b-c-d  s+a-b+c-d  s-a-b+c+d  s+a+b-c+d
s+a-b-c+d  s-a+b+c+d  s+a+b+c-d  s-a-b-c-d

если s=17/2, (a,b,c,d)=любая перестановка из (1/2, 2/2, 2/4, 8/2) с любыми знаками то получаем 24*16=384 обычных ассоциативных квадрата, с точность до поворотов и симметрии 48

[Nataly-Mak]

svb
результаты тестирования небогатые, потому что проверка одного массива из последовательных простых выбила меня из рабочего режима на 6 часов (в 4 часа запустила программу, в 10 она выкарабкалась).
Но всё по порядку. Я хотела дать вам для сравнения результаты работы программ mak5 и mag5x5, но сравнение получилось только в одном случае, во всех остальных у меня не хватило вдохновения проверить

Начала с массива из последовательных простых:

127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257

И начала с программы mak5. Программа работала 21349.61 сек. Найдено 4035 оригинальных квадратов.

Далее проверила только что построенный наименьший квадрат из последовательных смитов. Этот квадрат проверила по обеим программам. Найден 1 квадрат и там, и там. Прогрмма mak5 работала 368.79 сек., а программа mag5x5 - 225.6 сек. Налицо уменьшение времени. Однако сравнение с вашим результатом показывает, что мой компьютер по сравнению с вашим тихоход.

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

627 4619515 4653553 6633256 11989264
6633265 11989273 636 4619479 4653562
4619488 4653526 6633274 11989282 645
11989291 654 4619497 4653535 6633238
4653544 6633247 11989255 663 4619506

(см. статью "Нетрадиционные магические квадраты из чисел Смита".
Этот квадрат тоже проверила только по программе mak5. Программа работала 5340.49 сек. Найдено 12840 оригинальных квадратов! Невероятно. Видимо сыграло свою роль то, что числа образуют арифметические прогрессии.

Вот пока и всё у меня. А время уже почти обед

[svb]

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

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

Досовские программы плохо проспособлены к XP. Я запускаю их в FAR - при полностью открытом окне они работают значительно медленнее, чем в случае окна виндовоза (alt+enter).

У меня маленький вопрос о пандиагональных квадратах 6 порядка. Их должно быть много, но не факт, что из чисел 1,..,36. Примеры имеются?

[Nataly-Mak]

svb в сообщении #290922 писал(а):

У меня маленький вопрос о пандиагональных квадратах 6 порядка. Их должно быть много, но не факт, что из чисел 1,..,36. Примеры имеются?

Из чисел 1, ..., 36 пандиагональных квадратов 6-го порядка не существует. Это факт
Что касается нетрадиционных пандиагональных квадратов 6х6, примеров много. Например, тут пандиагональный квадрат из последовательных простых чисел:

Есть даже идеальный нетрадиционный квадрат 6-го порядка (то есть одновременно пандиагональный и ассоциативный).
См. мою статью "Нетрадиционные магические квадраты".

[Nataly-Mak]

Вот какие результаты у меня по магическим квадратам 4-го порядка из последовательных простых чисел.

$S = 258$

37 83 97 41
53 61 71 73
89 67 59 43
79 47 31 101

Количество оригинальных квадратов 4. Это наименьший квадрат 4-го порядка из последовательных простых (см. A073520 и A073521).

$S = 276$

41 37 97 101
103 83 47 43
71 67 79 59
61 89 53 73

Количество оригинальных квадратов 8.

$S = 5118$

1229 1249 1321 1319
1301 1303 1231 1283
1297 1277 1307 1237
1291 1289 1259 1279

Количество оригинальных квадратов 12.

$S = 19896$

4943 4933 5011 5009
4999 4973 4967 4957
5003 4969 4987 4937
4951 5021 4931 4993

Количество оригинальных квадратов 4.

$S = 50478$

12553 12583 12689 12653
12641 12647 12601 12589
12671 12611 12619 12577
12613 12637 12569 12659

Количество оригинальных квадратов 4.

Эти квадраты я нашла по своей программе ( в том числе и все варианты квадратов).

А вчера svb по моей просьбе прислал мне специальную программу для поиска таких квадратов.
(Кстати, maxal, это очень эффективная программа для поиска наименьшего магического квадрата 4х4 из последовательных смитов. Работает гораздо быстрее моей программы.)

По этой программе я проверила простые числа до 100000. Магических квадратов 4-го порядка из последовательных простых в этом интервале больше не найдено.
Надо проверять дальше, но сначала надо сгенерировать простые числа больше 100000. У меня есть свой генератор простых чисел, но, как и все мои программы, он очень медленный.

Предлагаю всем желающим продолжить представленную последовательность магических констант квадратов 4-го порядка из последовательных простых чисел.

[svb]

До простого 1299791 больше квадратов нет.

[Nataly-Mak]

Вот какой интересный результат получается. Есть 5 счастливых массивов из последовательных простых (да и те не все следуют подряд), которые складываются в магические квадраты 4-го порядка. А дальше разрыв непонятно какого размера. Так что и простые числа иногда не очень-то благополучно складываются в квадраты, хотя, конечно, лучше смитов.

То же самое я решила проверить для квадратов 5-го порядка из последовательных простых чисел.
Первые 7 массивов (подряд) оказались счастливыми, квадраты из них складываются. Но уже массив

167, 173, 179, ..., 293, 307

похоже, даёт осечку. Хотя пока ничего конкретного сказать не могу.
Три часа работала программа mag5x5, на экране 0 квадратов, при этом

I J K L   2, 9, 12, 23

Я не выдержала и прервала программу. Это ведь ещё неизвестно сколько времени ей осталось работать.

svb
если можно, помогите проверить этот массив
Скорее всего, квадрат из него не составится. Но почему так медленно работает программа? Ну, я понимаю, если бы квадраты составлялись, но ведь их нет! У меня такой тяжёлый случай впервые попался. Раньше было так: если квадраты не складываются, то программа очень быстро выполняется.

Следующие массивы пока не проверяла.

[svb]

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

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

Запустил.

[Nataly-Mak]

Спасибо!
Ждём...

[svb]

Time : 2796.15 s
квадратов нет

[maxal]

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

В моей программе реализована общая формула для квадрата 4-го порядка (приведённая в моей статье "Общие формулы магических квадратов", см. конец статьи).

Эта формула составлена в предположении, что квадрат строится из массива, состоящего точно из 16 чисел. Формула в таком случае зависит всего от 7 параметров и проверка выполняется очень быстро.

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

Занумеруем элементы квадрата $4\times 4$ так:

$$ \begin{bmatrix} x_1 & x_5 & x_{10} & x_2\\ x_{13} & x_8 & x_6 & x_{14} \\ x_{15} & x_{11} & x_7 & x_{16} \\ x_9 & x_3 & x_4 & x_{12} \end{bmatrix} $$

Элементы $x_1$, $x_2$, $x_3$, $x_5$, $x_6$, $x_8$, $x_{10}$, $x_{13}$ назовем независимыми, а остальные элементы - зависимыми, и укажем явные зависимости:

$$\begin{cases} x_4 = x_1 + x_2 - x_3\\ x_7 = x_3 + x_5 - x_6\\ x_9 = -x_2 + x_3 + x_5 - x_6 + x_8\\ x_{11} = x_1 + x_2 - x_3 - x_8 + x_{10}\\ x_{12} = x_2 - x_3 + x_6 - x_8 + x_{10}\\ x_{14} = x_1 + x_2 + x_5 - x_6 - x_8 + x_{10} - x_{13}\\ x_{15} = 2x_2 - x_3 + x_6 - x_8 + x_{10} - x_{13}\\ x_{16} = -2x_2 + x_3 + 2x_8 - x_{10} + x_{13} \end{cases} $$

Важным свойством этих зависимостей является то, что каждый элемент зависит лишь от элементов с меньшими номерами и сам при этом имеет минимально возможный номер.

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

На любом шаге алгоритма свободными числами назовем ранее неиспользованные числа. Изначально все данные числа свободны.

Начинаем определение элементов $x_i$ в их естественном порядке (т.е. для $i=1,2,\dots,16$):
* если $x_i$ независимый элемент, перебираем все свободные числа в качестве его значения (текущее выбранное значение перестает быть свободным), и переходим к следующему элементу;
* если $x_i$ зависимый элемент, вычисляем его значение по вышеуказанным формулам и проверяем является ли это значение свободным. Если да, то число становится несвободным, а мы переходим к следующему элементу; если нет - то возвращаемся к предыдущему элементу.

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

Важно отметить, что для отбрасывания заведомо прохих вариантов, здесь не всегда нужно знать значения всех независимых элементов. Например, элемент $x_4$ зависит лишь от $x_1$, $x_2$ и $x_3$ и проверить его значение можно, зная лишь значения этих трех элементов (совершенно неважно, чему равны остальные). Именно поэтому этот элемент имеет номер $4$ и проверяется сразу после того, как становятся известны значения $x_1$, $x_2$ и $x_3$. Именно эта идея делает алгоритм эффективным. Причем в своём классе этот алгоритм является самым эффективным (то есть, большего ускорения выжать из этой идеи не получится).

Теперь можно приступать к дальнейшему поиску квадрата $4\times 4$ из смитов.

P. S. Дальнейшая оптимизация возможна с учётом того, что если массив содержит элемент 0, то можно считать, что либо $x_1$, либо $x_3$ равен нулю.

[12d3]

Вот несколько квадратиков. В теге offtop, чтобы много места не занимали.

(Оффтоп)

101  31  47  79  
43  59  67  89  
73  71  61  53  
41  97  83  37  

1229  1321  1249  1319  
1303  1301  1283  1231  
1307  1237  1297  1277  
1279  1259  1289  1291  

4993  4931  5021  4951  
4937  4987  4969  5003  
4957  4967  4973  4999  
5009  5011  4933  4943  

12553  12689  12583  12653  
12671  12619  12611  12577  
12641  12601  12647  12589  
12613  12569  12637  12659  

3259909  3260021  3259999  3260051  
3260003  3260029  3259931  3260017  
3260027  3259957  3260063  3259933  
3260041  3259973  3259987  3259979  

3324457  3324521  3324329  3324371  
3324353  3324389  3324437  3324499  
3324359  3324361  3324491  3324467  
3324509  3324407  3324421  3324341  

9291749  9291649  9291521  9291613  
9291691  9291523  9291647  9291671  
9291539  9291719  9291643  9291631  
9291553  9291641  9291721  9291617  

24066733  24066683  24066643  24066719  
24066701  24066649  24066689  24066739  
24066677  24066703  24066737  24066661  
24066667  24066743  24066709  24066659  

26025257  26025253  26025107  26025217  
26025127  26025199  26025227  26025281  
26025239  26025179  26025229  26025187  
26025211  26025203  26025271  26025149  

46330187  46330133  46330021  46330177  
46330201  46330057  46330169  46330091  
46330069  46330111  46330181  46330157  
46330061  46330217  46330147  46330093  

95979629  95979511  95979613  95979551  
95979523  95979557  95979581  95979643  
95979599  95979619  95979547  95979539  
95979553  95979617  95979563  95979571  

99268847  99268783  99268649  99268879  
99268861  99268781  99268837  99268679  
99268699  99268691  99268849  99268919  
99268751  99268903  99268823  99268681 

116923199  116923193  116923057  116923129  
116923123  116923087  116923181  116923187  
116923097  116923109  116923201  116923171  
116923159  116923189  116923139  116923091  

170995151  170995267  170995361  170995399  
170995387  170995381  170995199  170995211  
170995289  170995229  170995369  170995291  
170995351  170995301  170995249  170995277  

204041471  204041623  204041417  204041689  
204041641  204041587  204041549  204041423  
204041609  204041483  204041581  204041527  
204041479  204041507  204041653  204041561  

213085007  213085003  213084871  213084899  
213084983  213084877  213085039  213084881  
213084889  213084941  213084923  213085027  
213084901  213084959  213084947  213084973  

218568971  218569157  218569079  218569147  
218569111  218569163  218569031  218569049  
218569133  218569037  218569123  218569061  
218569139  218568997  218569121  218569097  

229981441  229981613  229981399  229981601  
229981517  229981573  229981547  229981417  
229981637  229981447  229981487  229981483  
229981459  229981421  229981621  229981553  

232850557  232850621  232850741  232850743  
232850729  232850701  232850623  232850609  
232850707  232850627  232850711  232850617  
232850669  232850713  232850587  232850693  

254042641  254042681  254042837  254042881  
254042821  254042801  254042771  254042647  
254042879  254042689  254042779  254042693  
254042699  254042869  254042653  254042819  

255432869  255432953  255433033  255433051  
255433021  255433069  255432887  255432929  
255433049  255433001  255432949  255432907  
255432967  255432883  255433037  255433019  

256714391  256714349  256714219  256714327  
256714223  256714303  256714373  256714387  
256714363  256714277  256714333  256714313  
256714309  256714357  256714361  256714259