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

[Nataly-Mak]

Здорово!

А я поднимаюсь потихоньку вверх; начала с константы 3966, сейчас проверила константу 4452, это константа проверялась 12 часов.
Завтра начну проверять константу 4506; проверяю с шагом 54 и, конечно, с фильтром пока.

Вполне возможно, что alexBlack все эти константы уже проверил, но молчит
На форуме ПЕН он сообщал, что проверил константы 4884 и 4992, на третьей константе - 5100 - квадрат у него построился. Получается, что он проверял с шагом 108.

[Nataly-Mak]

Итак, пока у нас 9 различных пандиагональных квадратов 6-го порядка из смитов с магической константой 5964.
Проверила массивы во всех квадратах, все они различны. То есть ни один массив из 36 чисел не даёт хотя бы двух неизоморфных квадратов. Вот насколько мало таких пандиагональных квадратов! Поэтому и поиск их идёт очень долго.

Вчера решила попробовать продолжить построение пандиагональных квадратов 6-го порядка из простых чисел (по-прежнему работаю по программе svb, поскольку она работает намного быстрее имеющейся у меня версии программы alexBlack).

Из простых чисел квадраты строятся очень хорошо; правда, если это произвольный набор простых, а не последовательные простые. Как я сообщала, остановилась раньше на константе 990. Начала теперь с константы 1002, до константы 1050 (с шагом 12) уже построила квадраты. Конечно, все не строю, прерываю программу, как только найдётся несколько первых квадратов.
Удивительный факт - квадраты составляются для всех магических констант с шагом 12.

-- Чт май 03, 2012 07:14:21 --

Ещё о новом алгоритме построения пандиагональных квадратов 7-го порядка

Выше показана схема пандиагонального квадрата 7-го порядка с отклонениями от комплементарности, отклонений всего два - p1 и p2, но они жёстко связаны (формула приведена).

Старую программу не стала искать, может быть, она и не сохранена со старого винта; написала новую.
Проделала эксперимент, квадрат строила из произвольных натуральных чисел. Исходные данные:
K = 1590, S = 5565, p1 = -4, p2 = 10.

Группа с отклонением p1:

715 853 1369 643 577 583 271 709 1291 1501 907 949 649 787 667 1585 607 979 1 919 799 937 637 679 85 295 877 1315 1003 1009 943 217 733 871

17 пар, 34 числа

Группа с отклонением p2:

1001 407 233 977 1019 587 1163 437 1013 581 623 1367 1193 599

7 пар, 14 чисел

Здесь выбрано точно необходимое количество пар, в первой группе пар должно быть не меньше 17, во второй группе - не меньше 7.
С этими исходными данными квадрат строится очень быстро:

715  853  1369  1001  643  407  577 
 233  583  271  709  1291  977  1501 
 1019  907  587  949  649  787  667 
 1585  607  1163  793  437  979  1 
 919  799  937  637  1013  679  581 
 85  623  295  877  1315  1003  1367 
 1009  1193  943  599  217  733  871

Итак, тест программа прошла. Можно пробовать построение пандиагональных квадратов из смитов.
Такой эксперимент тоже провела; я его ещё и тогда провела, о чём сообщала на форуме ПЕН. Сейчас повторила эксперимент с этими же исходными данными и ещё один - с другими данными. Программа работает, 35 чисел ставит на место моментально, например (во втором эксперименте):
K = 17540, p1 = 1152, p2 = -2880, S = 61390,
в группе с отклонением p1 27 пар, в группе с отклонением p2 31 пара.

0  14386  8914  12442  9094  0  85 
 1678  274  1966  8023  0  0  0 
 9274  18346  4765  14566  7627  2614  4198 
 0  7726  0  9346  0  10966  0 
 14494  16078  11065  4126  9895  346  5386 
 0  0  0  10669  16726  18418  12982 
 18607  0  9598  2218  9778  4306  0

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

Программу можно использовать и для построения идеальных квадратов 7-го порядка. Ведь идеальный квадрат - это пандиагональный квадрат, в котором есть свойство ассоциативности. Это означает, что все отклонения от комплементарности в предложенном алгоритме будут равны нулю: p1 = p2 = 0.

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

[svb]

Цитата:

8:
3091 202 517 58 1642 454
265 391 1633 1111 2218 346
922 1255 2182 274 166 1165
706 913 778 121 1219 2227
22 1282 319 2578 85 1678
958 1921 535 1822 634 94
Time: 39822.34 sec+1сут.
9:
3091 391 346 265 913 958
4 922 1642 2911 166 319
1111 1921 58 454 562 1858
535 94 1507 85 2578 1165
706 2362 1633 355 526 382
517 274 778 1894 1219 1282
Time: 2сут.-30743.82 sec
10:
2965 526 535 85 958 895
319 346 1894 2218 202 985
1219 517 94 2434 22 1678
922 2038 913 4 454 1633
274 1255 706 1165 2173 391
265 1282 1822 58 2155 382
Time: 2сут.-14494.66 sec
11:
2965 346 958 94 1219 382
58 1894 1111 1921 895 85
391 535 517 121 1822 2578
913 1633 2362 4 778 274
355 922 454 1642 265 2326
1282 634 562 2182 985 319
Time: 2сут.-12104.60 sec

[Nataly-Mak]

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

(Оффтоп)

Summa=1062
1:
113 311 67 89 211 271
167 179 223 127 193 173
181 131 257 191 199 103
229 107 101 277 79 269
263 197 163 151 139 149
109 137 251 227 241 97
Time: 0.97 sec
2:
113 311 131 89 239 179
151 79 269 263 101 199
251 197 109 163 193 149
229 97 157 277 61 241
127 271 173 167 257 67
191 107 223 103 211 227
Time: 6.76 sec
3:
113 311 131 89 137 281
127 227 163 167 271 107
197 73 269 97 233 193
229 199 139 277 61 157
223 101 181 191 109 257
173 151 179 241 251 67
Time: 8.32 sec
Time: 15.13 sec

Summa=1074
1:
31 107 277 83 349 227
271 157 307 13 199 127
193 167 139 233 73 269
229 79 151 373 181 61
283 197 103 149 163 179
67 367 97 223 109 211
Time: 9.33 sec
2:
31 107 349 83 367 137
271 163 139 277 127 97
313 167 109 179 43 263
229 61 151 373 181 79
19 269 223 149 157 257
211 307 103 13 199 241
Time: 9.93 sec
3:
31 107 313 83 367 173
79 337 151 139 19 349
157 233 127 149 211 197
229 61 163 373 181 67
271 263 37 227 97 179
307 73 283 103 199 109
Time: 10.82 sec
4:
31 107 277 83 349 227
283 73 271 157 67 223
61 239 241 137 127 269
229 181 13 373 79 199
103 263 109 173 313 113
367 211 163 151 139 43
Time: 12.99 sec
Time: 13.55 sec

Summa=1086
1:
41 311 191 59 227 257
211 17 193 269 163 233
263 137 317 107 83 179
277 89 127 347 97 149
113 251 101 131 293 197
181 281 157 173 223 71
Time: 21.25 sec
Time: 47.41 sec

Summa=1098
1:
331 73 127 59 269 239
79 241 223 293 113 149
167 173 257 181 109 211
281 83 137 61 307 229
89 277 197 271 101 163
151 251 157 233 199 107
Time: 1.45 sec
2:
331 73 239 59 269 127
89 173 233 313 97 193
181 229 113 191 107 277
281 83 263 61 307 103
79 283 149 251 179 157
137 257 101 223 139 241
Time: 4.02 sec
Time: 5.32 sec

Summa=1110
1:
7 373 37 313 151 229
199 137 211 257 139 167
223 67 277 73 307 163
337 173 241 83 43 233
13 97 283 271 367 79
331 263 61 113 103 239
Time: 21.47 sec
Time: 34.18 sec

Summa=1122
1:
7 73 181 307 241 313
263 269 167 137 47 239
157 107 283 257 229 89
331 211 61 103 223 193
71 151 233 277 281 109
293 311 197 41 101 179
Time: 21.59 sec
2:
7 73 181 307 241 313
269 257 263 131 11 191
137 151 179 229 317 109
331 211 61 103 223 193
67 197 271 281 283 23
311 233 167 71 47 293
Time: 21.61 sec
3:
7 73 181 307 241 313
263 227 179 149 11 293
199 107 277 239 271 29
331 211 97 103 223 157
53 193 137 283 317 139
269 311 251 41 59 191
Time: 21.70 sec
4:
7 73 181 307 241 313
281 317 227 5 53 239
71 61 293 277 269 151
331 211 97 103 223 157
199 149 193 263 229 89
233 311 131 167 107 173
Time: 21.72 sec
5:
7 73 193 307 313 229
263 283 197 31 71 277
113 149 269 257 251 83
331 139 127 103 223 199
137 167 173 317 227 101
271 311 163 107 37 233
Time: 21.84 sec
6:
7 73 181 307 313 241
257 263 239 137 29 197
149 157 191 229 233 163
331 139 127 103 223 199
61 179 271 293 277 41
317 311 113 53 47 281
Time: 22.33 sec
7:
7 73 151 307 271 313
263 281 113 197 11 257
193 137 241 233 277 41
331 181 157 103 223 127
59 139 167 229 317 211
269 311 293 53 23 173
Time: 23.65 sec
Time: 23.70 sec

Summa=1134
1:
53 317 131 79 271 283
239 149 293 157 199 97
107 193 251 127 233 223
313 101 73 311 67 269
181 211 277 179 197 89
241 163 109 281 167 173
Time: 0.32 sec
2:
53 317 107 79 271 307
277 193 211 149 137 167
127 181 223 257 263 83
313 101 73 311 67 269
233 229 227 97 197 151
131 113 293 241 199 157
Time: 1.23 sec
Time: 3.04 sec

Summa=1146
1:
179 293 191 83 227 173
97 263 109 317 193 167
241 103 283 43 199 277
233 107 251 269 137 149
139 229 181 211 79 307
257 151 131 223 311 73
Time: 0.72 sec
2:
179 293 191 83 251 149
193 139 331 79 181 223
151 197 157 227 241 173
233 107 167 269 113 257
281 313 137 211 131 73
109 97 163 277 229 271
Time: 1.83 sec
3:
179 293 191 83 251 149
331 139 193 223 181 79
157 197 151 227 241 173
233 107 167 269 113 257
137 313 281 73 131 211
109 97 163 271 229 277
Time: 1.83 sec
4:
179 293 167 83 227 197
73 107 277 317 61 311
241 223 151 67 271 193
233 131 251 269 113 149
163 313 37 211 283 139
257 79 263 199 191 157
Time: 2.55 sec
Time: 3.33 sec

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

[svb]

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

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

И зачем вы меня спровоцировали на построение этих квадратов?

Цитата:

Возникает вопрос: сколько существует различных квадратов с магической константой 5964?
Это наш тестовый пример. В моей статье, помнится, я привела несколько разных квадратов, но все ли?

А сейчас и бросить жалко

12:
 2965  895   85  166 1795   58
 1282  202 2902  706  778   94
  382 1219  265  958 2218  922
  526 1165 1255  319  121 2578
  355 2461  346 1633  535  634
  454   22 1111 2182  517 1678
Time: 2 сут.-9392.43 sec
13:
 2965  562  265  166  895 1111
  346   22 1894 2362  958  382
 1678 2155  634  922  121  454
  526   85  274  319 2434 2326
  355 2605 1642  913  391   58
   94  535 1255 1282 1165 1633
Time: 2 сут.-9012.80 sec

Всего несколько суток осталось

[Nataly-Mak]

Эх, вы единственный коллега, поддающийся на мои провокации
Раньше были ещё, но... больше не желают поддаваться на провокации

Ведь пандиагональные квадраты с магической константой 5964 - это у нас своего рода эталон. Так что будет замечательно, если мы будем знать полный комплект различных квадратов с этой магической константой.

А я протестировала программу построения пандиагональных квадратов 7-го порядка по новому алгоритму (с отклонениями от комплементарности) на примере построения идеального квадрата. Всё прекрасно выполнилось.
Квадрат взяла из своей статьи "Нетрадиционные пандиагональные квадраты (часть II)", это идеальный квадрат из простых чисел (построен по другому алгоритму).

Исходные данные:
K=5554, S = 19439, p1 = p2 = 0.

Квадрат построился минут за 10:

4643  2141  1301  5501  5153  677  23 
4463  281  1427  5297  2543  167  5261 
3833  761  3491  4373  1217  383  5381 
503  821  5471  2777  83  4733  5051 
173  5171  4337  1181  2063  4793  1721 
293  5387  3011  257  4127  5273  1091 
5531  4877  401  53  4253  3413  911

***
Ещё построила несколько пандиагональных квадратов 6-го порядка из простых чисел, до константы 1230 включительно. Решила пока остановиться. Квадраты строятся и очень быстро. Но это всё же только экспериментальные данные.

Кто сможет доказать, что для любой следующей магической константы в этой арифметической прогрессии с разностью 12 пандиагональный квадрат 6-го порядка из простых чисел существует?

Хорошая задача!

[Nataly-Mak]

svb
а помните, как лихо вы строили пандиагональные квадраты 7-го порядка методом Россера (с использованием примитивных квадратов)?

Вот сейчас решила посмотреть, что мы имеем с пандиагональными квадратами 7-го порядка из простых чисел. Благо, файл с квадратами сохранился.

Это магические константы квадратов, которые у нас есть:

2477, 2435, 2363, 2279, 2047, 1895, 1649, 1597

Пока не вижу никакой закономерности в этой последовательности магических констант.

Квадрат с магической константой 1649 построил Pavlovsky; этот квадрат некоторое время был у нас наименьшим. Потом я улучшила этот результат, построив квадрат с магической константой 1597:

191 89 397 409 43 157 311
379 103 101 491 17 313 193
317 241 109 163 439 47 281
223 383 227 107 541 37 79
331 337 7 139 167 563 53
83 347 389 277 127 307 67
73 97 367 11 263 173 613

Я тоже строила квадрат методом Россера (это было в апреле 2011 г.).

Пока этот квадрат является наименьшим. Однако не доказано, что он действительно наименьший, и я сильно подозреваю, что это совсем не так.

Задачу, к сожалению, все забросили.
А в последовательности OEIS (A179440) так и стоят одиноко три наименьшие константы - для квадратов порядков 4 - 6; дальше указаны только верхние границы для констант.
Обидно, что не довели хотя бы квадраты 7-го порядка до логического конца

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

[svb]

Summa=5964
Осталось совсем немного, но я выключаю комп. Справа число квадратов для соответствующего N. Можете продолжить

N=76(3865) - 0
N=75(3802) - 0
N=74(3694) - 0
N=73(3649) - 0
N=72(3622) - 0
N=71(3595) - 1
N=70(3505) - 1
N=69(3442) - 0
N=68(3226) - 3
N=67(3091) - 4
N=66(2965) - 10
N=65(2839) - ?
N=64(3046) - ?
N=63(2911) - ?
N=62(2785) - 6
N=61(2902) - ?
N=60(2515) - ?
N=59(2227) - ?
N=58(2974) - ?
N=57(2461) - ?
N=56(2722) - ?
N=55(2605) - ?
N=54(2173) - ?
N=53(4) - ?
N=52(2326) - ?
N=51..36     - 0

[Nataly-Mak]

Насколько я понимаю, совсем не обязательно выполнять программу без перерыва?...

Я всегда на ночь прерываю, а утром продолжаю с прерванного места.
Сейчас проверяю константу 4938, вчера работала 14 часов; сейчас продолжу, осталось ещё 52 числа прверить.

[Nataly-Mak]

svb
вы...навсегда выключили комп?
Значит, и вы больше не поддаётесь на провокации, связанные с квадратами?

Вот, к примеру, примитивный квадрат 7х7 из простых чисел, соответствующий приведённому выше пандиагональному квадрату с магической константой 1597:

7   11   17   37   67   191   241
43   47   53   73   103   227   277
79   83   89   109   139   263   313
97   101   107   127   157   281   331
163   167   173   193   223   347   397
307   311   317   337   367   491   541
379   383   389   409   439   563   613

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

11 - 7 = 4
47 - 43 = 4
83 - 79 = 4
........

277 - 241 = 36
227 - 191 = 36
103 - 67 = 36
.......

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

Задачу до конца так и не решили. Pavlovsky решал, svb решал, я решала... А где наименьший квадрат?

Нет, друзья мои, так задачи не решают
Там начали, бросили, там начали, бросили... Понимаю: скучно гнать программу 10 суток. Мне, однако, совсем не скучно! Потому что программа у меня работает сама по себе, а я
тем временем работаю сама по себе. И никакой скуки и тоски!

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

У меня, к сожалению, программа построения примитивных квадратов 7х7 не сохранилась (сдохла вместе со старым компом). Сейчас буду писать новую программу.

-- Пт май 04, 2012 07:58:38 --

Просмотрела свой давнишний файл о построении пандиагональных квадратов 7-го порядка из простых чисел. Вот, например, такой ещё есть примитивный квадрат:

13 23 43 73 83 113 293
31 41 61 91 101 131 311
37 47 67 97 107 137 317
79 89 109 139 149 179 359
163 173 193 223 233 263 443
181 191 211 241 251 281 461
379 389 409 439 449 479 659

Хороший квадратик, он даёт пандиагональный квадрат с магической константой 1433.
Но! В нём есть одно не простое число - 91.

Это ещё образец примитивного квадрата для тех, кто вдруг (!) захочет попробовать поиск примитивных квадратов 7х7 из простых чисел.

Замечу, что наименьший обычный магический квадрат 7-го порядка из простых чисел имеет магическую константу 733 (см. A164843).

[Nataly-Mak]

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

2477, 2435, 2363, 2279, 2125, 2047, 1895, 1649, 1597

Это то, что есть у меня в файле; может быть, не всё скопировала в этой теме, но было это очень давно, искать не хочется.

Сейчас задала в программе ограничение на магическую константу S - не больше 1895, мгновенно получила примитивный квадрат с константой 1739:

11  13  23  41  151  263  331 
17  19  29  47  157  269  337 
59  61  71  89  199  311  379 
101  103  113  131  241  353  421 
137  139  149  167  277  389  457 
227  229  239  257  367  479  547 
431  433  443  461  571  683  751

Превращаю этот примитивный квадрат в пандиагональный с помощью преобразования Россера:

263 71 457 461 17 241 229
431 157 103 479 23 379 167
239 331 89 137 571 19 353
277 433 269 113 547 41 59
421 257 11 199 139 683 29
61 389 443 337 131 227 151
47 101 367 13 311 149 751

Тест программа прошла замечательно. Однако полученная константа больше 1597, а надо искать с меньшей константой.

Далее запускаю программу с ограничением на константу не больше 1595, всё! программа уходит в глубокую задумчивость
Вот и попробуйте найти примитивный квадрат с константой меньше 1597! Если он существует, то найти его очень сложно.
Я задействовала в программе массив из 150 простых чисел, это довольно большой массив.

В общем, задача остаётся открытой.

[Nataly-Mak]

В голове вертятся идеи оптимизации программы.

Например, первое: можно задавать в программе магическую константу, для которой делается проверка; это сократит количество перебираемых элементов на 1. Сейчас у меня в программе конкретная константа не задаётся, а задаётся только верхняя граница.
Второе: попробовать минимизировать массив чисел для конкретной магической константы. Массив из 150 чисел может оказаться избыточным. Можно ещё проверить каждое число массива на принадлежность не менее чем трём цепочкам из 7 чисел с суммой равной магической константе.

Берём, скажем, следующую константу для проверки - 1595. Вот всё надо сделать под эту константу. Возможно, оптимизация позволит проверить массив чисел полностью.

[Nataly-Mak]

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

Summa=5964
Осталось совсем немного, но я выключаю комп. Справа число квадратов для соответствующего N. Можете продолжить

Могу

Summa=5964
1:
 2839  265  319   22 2434   85
   94  922 3046  985  526  391
 1282  121  778  895  562 2326
  202 1219 1111  913   58 2461
  382 2182    4 2515  346  535
 1165 1255  706  634 2038  166
Time: 6142.49 sec

С утра запустила программу, до сих пор проверяется число 2839.
Но у меня работает ещё программа проверки магической константы 4830, плюс программа поиска примитивных квадратов 7х7, правда, последнюю сейчас прервала.

[Nataly-Mak]

Ещё один квадратик появился

2:
 2839  526 1219   94 1282    4
  895 1165 2461  274 1111   58
   85  391  166  922 2218 2182
  778 1822 1795  265  346  958
  913 1678  202 1894   22 1255
  454  382  121 2515  985 1507
Time: 34365.02 sec

[svb]

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

Ещё один квадратик появился

Ох, сколько их еще будет!