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

[Nataly-Mak]

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

У меня наименьший квадрат такого вида получился с магической константой 307:

1 67 149 19 71
139 17 61 37 53
97 23 43 137 7
41 127 43 83 13
29 73 11 31 163

Эх, как жаль, что все коллеги ушли из темы, и проверить результат некому

Radko отправила этот квадрат, он сразу увидел ошибку - два одинаковых числа 43.
Ошибка в программе была из разряда "подводных камней". Искала по этой программе квадраты Стенли из простых чисел близнецов, и решение было найдено правильное, ошибка себя не проявила никак. Так бывает!
Спасибо Radko; ошибку исправила, нашла новое решение (пандиагональный квадрат 5-го порядка из различных простых чисел плюс число 1); этот квадрат с магической константой 337, вроде правильно теперь:

1 89 157 43 47
127 19 41 67 83
107 61 53 103 13
29 97 79 101 31
73 71 7 23 163

Отправила квадрат Radko, он проверит сейчас
Зову, зову его в тему, но он пока почему-то не приходит. Возможно, сложности с регистрацией.

[Nataly-Mak]

В OEIS есть последовательность наименьших магических констант МК из чисел Смита - A170928.
Нет последовательности наименьших магических констант пандиагональных квадратов из чисел Смита. А ведь над этими квадратами мы работали очень и очень много! Особенно хлопотным оказался пандиагональный квадрат 6-го порядка.

Итак, что мы имеем для такой статьи.

1. Наименьший пандиагональный квадрат 4-го порядка (автор maxal):

1282   5458   5242   2578
5602   2218   1642   5098
2038   4702   5998   1822
5638   2182   1678   5062

Магическая константа равна 14560.

2. Наименьший пандиагональный квадрат 5-го порядка (автор Pavlovsky):

58 1507 4306 526 1921
4126 265 1858 1111 958
2911 562 778 3865 202
517 3802 1255 2362 382
706 2182 121 454 4855

Магическая константа равна 8318.

3. Наименьший пандиагональный квадрат 6-го порядка.
Здесь было очень интересно: квадрат одновременно нашли alexBlack и svb.
Первым сообщил о найденном квадрате на форуме ПЕН alexBlack:
http://e-science.ru/forum/index.php?s=& ... t&p=286985

355,1633,1642, 958, 166, 346,
1255, 85, 535, 778,2182, 265,
1822,1858, 58, 562, 526, 274,
121, 319, 517,1966,1282, 895,
1165,1111,1894, 202, 22, 706,
382, 94, 454, 634, 922, 2614

Через 10 минут появилось сообщение svb:
http://e-science.ru/forum/index.php?s=& ... t&p=286987

2362 895 121 166 1165 391
85 706 2155 454 778 922
94 913 1255 526 634 1678
355 382 985 517 958 1903
1642 1858 319 1219 58 4
562 346 265 2218 1507 202

Такое вот совпадение. Магическая константа квадрата равна 5100.
Однако ни один из автор не доказал минимальность этой константы.
Позже мы с svb начали проверку всех меньших потенциальных магических констант.
svb быстро устал от этого занятия
и проверку я завершила одна. Если нигде не ошиблась, то выходит, что магическая константа 5100 действительно минимальная.
[Как уже не раз отмечалось, нужна независимая проверка для подтверждения данного результата. Ошибки возможны у всех.]

Для пандиагональных квадратов 7-го порядка пока имеем немного.
Давно мной был построен такой квадрат с очень большой магической константой 696745:

37678 778 70582 381802 202 25618 180085
381298 23962 1921 217642 382 54814 16726
180346 54418 958 16222 405058 265 39478
39982 381361 37822 2182 234382 562 454
56218 180526 58 24214 16285 418918 526
517 53842 381622 54562 2362 180022 23818
706 1858 203782 121 38074 16546 435658

(см. статью «Нетрадиционные пандиагональные квадраты (часть II)»)

Совсем недавно был получен новый результат.
J. K. Andersen решал мою головоломку о квадратах Стенли, причём решал её не только для простых чисел, но и для чисел Смита. Он нашёл наименьший квадрат Стенли 7-го порядка из чисел Смита:

Цитата:

Minimal (7,87643)
(0,180,1404,2160,3600,3960,16020)

454   634   1858   2614   4054   4414   16474
1642   1822   3046   3802   5242   5602   17662
2038   2218   3442   4198   5638   5998   18058
5674   5854   7078   7834   9274   9634   21694
5935   6115   7339   8095   9535   9895   21955
20362   20542   21766   22522   23962   24322   36382
24214   24394   25618   26374   27814   28174   40234

Осталось применить к этому квадрату Стенли преобразование Россера и готов пандиагональный квадрат 7-го порядка из чисел Смита с магической константой 87643:

4414 3442 21955 26374 1642 9274 20542
24214 5242 5854 24322 1858 18058 8095
21766 16474 4198 5935 27814 1822 9634
9535 24394 5602 7078 36382 2614 2038
21694 22522 454 5638 6115 28174 3046
2218 9895 25618 17662 7834 20362 4054
3802 5674 23962 634 5998 7339 40234

Это наименьший регулярный пандиагональный (по Россеру) квадрат 7-го порядка из чисел Смита. Однако ничего нельзя сказать о том, является ли этот квадрат наименьшим из всех пандиагональных квадратов 7-го порядка из чисел Смита - регулярных и нерегулярных.
Всё та же "задача века"

Таким образом, для пандиагональных квадратов 7-го порядка магическая константа 87643 может быть приведена только как верхняя граница.

И последовательность в будущей статье OEIS пока выглядит так:

14560, 8318, 5100, 87643 (?)

[Nataly-Mak]

Идём дальше.
В статье показано построение пандиагональных квадратов 8-го и 12-го порядков из чисел Смита. Для этого построения использован набор комплементарных пар чисел Смита, который нашёл maxal.
Конечно, эти квадраты, скорее всего, не наименьшие.

n=8

391 778 677101 675058 498514 637474 184018 46714
958 2578 674914 663934 629194 412078 54958 281434
514597 657274 167935 26914 16474 20578 661018 655258
633694 490558 50458 202954 5458 81058 670414 585454
181498 42538 495994 633298 679621 679234 2911 4954
50818 267934 625054 398578 679054 677434 5098 16078
663538 659434 18994 24754 165415 22738 512077 653098
674554 598954 9598 94558 46318 189454 629554 477058

S=2720048

n=12

391 778 3694 677101 675058 659938 498514 637474 454873 184018 46714 241519
958 2578 4198 674914 663934 674194 629194 412078 405274 54958 281434 276358
8014 19678 26014 655618 650974 633838 402214 429214 409594 294178 260158 290578
514597 657274 521446 167935 26914 174946 16474 20578 70267 661018 655258 593365
633694 490558 459094 50458 202954 222538 5458 81058 58018 670414 585454 620374
519466 438934 457078 176926 250438 243094 125266 29398 73498 538366 641254 586354
181498 42538 225139 495994 633298 438493 679621 679234 676318 2911 4954 20074
50818 267934 274738 625054 398578 403654 679054 677434 675814 5098 16078 5818
277798 250798 270418 385834 419854 389434 671998 660334 653998 24394 29038 46174
663538 659434 609745 18994 24754 86647 165415 22738 158566 512077 653098 505066
674554 598954 621994 9598 94558 59638 46318 189454 220918 629554 477058 457474
554746 650614 606514 141646 38758 93658 160546 241078 222934 503086 429574 436918

S=4080072

Для порядков 9,10,11 мне не известны пандиагональные квадраты из чисел Смита.
Построить такие квадраты довольно сложно.

[Nataly-Mak]

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

Отправила квадрат Radko, он проверит сейчас

Radko мой квадрат проверил, нашёл, что этот квадрат правильный
Далее он попросил меня построить подобные квадраты (из простых чисел плюс число 1) для порядков 6 и 7, желательно, конечно, наименьшие.
Для порядка 7 нашла один такой квадрат:

1 229 79 419 179 443 227
167 521 191 97 211 31 359
307 13 311 107 509 269 61
449 257 139 271 109 293 59
73 389 41 401 197 127 349
149 67 337 151 353 137 383
431 101 479 131 19 277 139
S=1577

По алгоритму Россера строила квадрат (с помощью квадрата Стенли); в минимальности квадрата не уверена. Среди регулярных квадратов (по Россеру) этот квадрат является наименьшим.

А вот с квадратами порядка 6 всё очень плохо
Я уже рассказала о попытке проверки минимальной потенциальной магической константы 438 для пандиагонального квадрата 6-го порядка из простых чисел.
Ничего не получилось из этой попытки!
Даже когда задаю массив не из 43 чисел (объединённый), а только из 36 чисел, программы (и alexBlack, и svb) работают очень долго и ничего не находят; однако они не выходят в конец с выводом, что решения не существует.
Сегодня решила добавить к массиву из 43 простых чисел число 1 и попытаться построить пандиагональный квадрат с магической константой 438 по программе alexBlack.
Запустила программу утром, программа написала на экране:

|43.

Это всё!
Программа работает целый день, по-прежнему одна точка, курсор мигает.

К сожалению, автор не захотел прокомментировать работу программы (писала ему ЛС, когда пробовала построить квадрат с магической константой 438 из набора простых чисел без числа 1; ответ вообще не получила).

Так вот и не оправдала надежды Radko
квадрат порядка 7 нашла, но, возможно, не наименьший; квадрата порядка 6 нет никакого.

[svb]

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

К тому же, проверка по программе svb будет неправильной, так как он не использует число 3.

Ну, почему же? Вот сейчас попробовал, см. картинку. На ней видны используемые простые числа, число 3 имеется.
Возможно вы не отключили Filter, который, кажется, нужен был для смитов?

[Nataly-Mak]

Ну, насчёт фильтра... нет, невозможно, что я его не отключила
Я уже столько решений нашла из простых чисел близнецов!

Странно, у меня число 3 не появляется ни в одном примере (я искала очень много решений из простых чисел близнецов, а в этом массиве число 3 присутствует). Специально очень внимательно рассматривала каждый массив (он же выводится на экран), числа 3 не было ни разу!!
Может быть, вы позже убрали запрет на число 3?
Впрочем, я ничего не утверждала точно, а высказала предположение, что вы не используете число 3.

Цитата:

К тому же, в программе svb есть один нюанс: по-моему, он не использует число 3.

Ну, так и что же? Вы проверили до конца магическую константу 438?
Мне это не удалось ни по вашей программе, ни по программе alexBlack.

Сейчас ещё раз посмотрела на массив для магической константы 438. Действительно число 3 есть. Запустила программу ещё раз, попытка №3
Тогда почему у меня это число ни разу не появлялось при поиске квадратов из простых чисел близнецов? В массиве оно точно есть (во входном файле inp.txt).

-- Пн июн 03, 2013 15:17:12 --

svb
кстати, у вас в массиве 58 чисел. По-моему, это избыточно.
Выше я приводила объединённый массив для проверки константы 438, который нашёл maxal. Этот массив содержит 43 числа.
Я запускала программу именно с таким массивом, и даже в этом случае результата не дождалась.

-- Пн июн 03, 2013 15:30:01 --

И версия у меня такая по поводу числа 3 при поиске квадратов из простых чисел близнецов:
может быть, в этом случае число 3 не входит ни в одну пару псевдокомплементарных чисел

Но что оно выбрасывается --- это точно.

-- Пн июн 03, 2013 15:42:59 --

Вот все решения, найденные для простых чисел близнецов:

(Оффтоп)

Summa=4206
1:
 2381  461  431   41  881   11
  197   17 2027  809 1049  107
  599 1481   29  239  827 1031
  281  311 1061  101 1151 1301
  569 1667  521 1229   71  149
  179  269  137 1787  227 1607
Summa=4134
1:
 2657   29  431   17  809  191
  821  269 1607  659  179  599
  107  197 1151 1301  347 1031
   71 1091  137   11  827 1997
  419 2267  239  857   41  311
   59  281  569 1289 1931    5
Summa=4062
1:
 2657  239   71   17  881  197
  617  281 2111  569  137  347
  101  149  521 1319  821 1151
   29 1481  311    5  107 2129
  431 1871  191 1091  419   59
  227   41  857 1061 1697  179
Summa=3954
1:
 2381   41  197   17  461  857
    5  101 1427 1931   71  419
  881 1319  569   29  347  809
  179  107  521   59 2027 1061
  269 2237  599  431  227  191
  239  149  641 1487  821  617
Summa=3774
1:
 2339  347   71   11  809  197
  149  311  857 1667  191  599
  659  827  821  269  137 1061
  107   41 1229   59 1319 1019
  419 1787  179  281  227  881
  101  461  617 1487 1091   17
Summa=3594
1:
 2129  419  179   11  617  239
  881   29 1667  521  269  227
  101   17  827  821 1019  809
  149 1301  281  107   59 1697
  137 1787   71  857  311  431
  197   41  569 1277 1319  191
Summa=3414
1:
 2081    5  431   59  641  197
  149  239  419 1487  101 1019
  617 1151  659  569  227  191
  107  311  599   29 1319 1049
  179 1667   17  461  269  821
  281   41 1289  809  857  137

Нет ни одного решения с числом 3. Его просто не было в стартовом массиве чисел, подготовленном программой.
Это и привело меня к мысли, что вы не используете число 3.

[svb]

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

кстати, у вас в массиве 58 чисел. По-моему, это избыточно.

Конечно избыточно. Это только для пробы. В программе предусмотрено либо задавать N, либо постепенно откусывать старшие числа с помощью нажатия на [2] -Del. Обычно удается для конкретного N довести расчет до конца. Хорошим ориентиром является высвечиваемое число простых чисел, которые удалось достичь. Если для конкретного N не достигается 35, то мало шансов на решение и для близких N.

Нужно будет при случае программу проверить. Сейчас я о ней почти ничего не помню. Помню только, что CP=1 это полная проверка.

На многоядерных процессорах разумно запускать несколько процессов для различных N для ускорения поиска. Вот некоторые проверенные (?) N:

s=438
n=54 257 35
n=50 229 35
n=39 163 35  

Увы, я умудрился даже не записать, была ли полная проверка для этих N?
Но видно, что 35 достигается для N=39..54 - шансы на решение велики.

[Nataly-Mak]

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

На многоядерных процессорах разумно запускать несколько процессов для различных N для ускорения поиска.

Нет, разумно сделать многопоточную программу.
Прошедший конкурс показал, что многие программисты сейчас пишут многопоточные программы. В частности, mertz мне прислал такую программу.
Vovka17 писал, что тоже попробовал в этом конкурсе эту штуку, пришёл к выводу, что ничего страшного нет. Я тоже так думаю Не боги горшки обжигают. Однако сама уже вряд ли возьмусь за это дело, стара уж для таких новшеств

Сейчас перезапустила программу с массивом из 43 чисел. Надо проверить этот массив.
Да, шансы велики: 35 элементов уже на месте при первом же N. Но будет ли решение

[svb]

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

Нет, разумно сделать многопоточную программу.

Спорить не буду , хотя у меня больше надежд на оптимизацию алгоритма поиска.

[Nataly-Mak]

Ох, этот алгоритм уже столько оптимизировали!
И вы, и alexBlack.
Однако время работы программы по-прежнему очень большое, увы.

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

[Nataly-Mak]

svb
это окно программы после нескольких часов работы. Не проверилось даже N=43 (массив введён из 43 чисел).
Похоже, тут работы на несколько суток. Прерываю.
Впору открывать проект распределённых вычислений
Но боюсь, что участников проекта будет максимум двое - вы и я.

[Nataly-Mak]

7 часов утра.
Запустила программу проверки магической константы 438 для массива, состоящего из 43 различных простых чисел (по программе svb).
Теперь начинаю проверку с N=42 (хотя N=43 у меня вчера не проверилось полностью; ладно, вернусь тогда к этому варианту).
Через несколько секунд 34 элемента на месте, 35 элементов пока не найдены.

Проверится ли за день этот вариант
Если в день уложится проверка, тогда можно проверить все числа --- в день по числу.
Не так уж много, если учесть, что надо проверить всего следующие варианты:
N=43,42,41,...,36.
Восемь дней

Кто хочет посмотреть данную программу в работе, можно скачать программу здесь:
http://svb.hut.ru/ALG/mag6.htm
[заодно прочитать описание алгоритма; на странице дана ссылка для скачивания программы]

А здесь алгоритм и программа alexBlack:
http://alex-black.ru/article.php?content=121

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

Ну, тем и интереснее задача!
Я вот предлагаю сделать многопоточную программу.
svb возлагает надежды на оптимизацию алгоритма поиска.
alexBlack предпочёл уйти от этой задачи. Надоела

Я в своё время тоже к этому алгоритму приложилась
Была написана статья. Времени потратила очень много, но ничего путного так и не добилась

-- Вт июн 04, 2013 08:01:26 --

Эх, мысль хорошая пришла в голову
Начинать проверку надо с N=36 (а не с N=43): чем меньше чисел в массиве, тем быстрее выполнится проверка.
Ладно, сегодня уж не буду заново запускать программу, пусть проверяет N=42.
35 элементов уже давно на месте. Да, шансы велики, но решение никак не находится.

[Nataly-Mak]

Прервала программу в 22:00.
Увы, N=42 не проверилось до конца. Решение не найдено.



Сегодня попробую проверить N=36 (в массиве будет ровно 36 чисел). Может быть, повезёт.
Надеюсь, что этот вариант проверится до конца.

-- Ср июн 05, 2013 05:10:53 --

Ага, при N=36,37 программа сразу вылетает в конец с сообщением, что решений нет.
Уже хорошо
При N=38 проверка началась, пока 33 элемента на месте.
Значит, осталось проверить всего 6 вариантов. Варианты N=42,43 тяжёлые, за день проверка не выполняется.

svb, наверное, ушёл заниматься оптимизацией алгоритма поиска
Опять я осталась один на один с задачей.

[Nataly-Mak]

Сижу смотрю на завораживающее мигание курсора в программе svb
А мысли в голове бегут, бегут...
И вот, кажется, неплохая мысль:
если массив из 36 чисел программа проверяет мгновенно, то надо просто проверить все потенциальные массивы из 36 чисел.

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

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

Вот первый потенциальный массив простых чисел:

3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 163 191

сумма всех чисел массива равна 2628. Массив даёт МК с магической константой 438.

Таких наборов несколько:

[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 157, 197]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 163, 191]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 173, 181]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 151, 173, 179]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 157, 167, 179]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 163, 167, 173]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 149, 151, 163, 179]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 149, 157, 163, 173]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 139, 149, 151, 167, 173]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 131, 137, 139, 149, 151, 157, 173]
[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 131, 137, 139, 149, 151, 163, 167]

Поэтому имеет смысл строить квадрат из их объединения (содержащего 43 элемента):

[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 197]

А ведь я в своей статье такой сценарий рассматривала --- проверку каждого потенциального массива из 36 чисел. У меня и программа была сделана именно для такого массива (проверка в этом случае выполняется довольно быстро). Но беда в том, что в большинстве случаев потенциальных массивов из 36 чисел очень много и проверить их все по одному сложно.
Но в данном случае массивов не так много.
Правда, здесь вопрос возникает к maxal: действительно ли это все потенциальные массивы для магической константы 438

Ещё нюанс: это уже по программе alexBlack. Я уже пыталась в этой программе проверить массив из 36 чисел (о чём писала выше). Странно, но и в этом случае программа работает очень долго; результата не дождалась.

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

Версия такая: массив, который подготовила программа svb при введении N=36 - плохой массив, в том смысле, что из него квадрат не может быть построен и это программа устанавливает с ходу. Надо будет глянуть на этот массив внимательнее. Именно поэтому проверка завершилась мгновенно с отрицательным результатом.

-- Ср июн 05, 2013 07:32:55 --

Проверку с N=38 не прерываю.
Запускаю параллельно проверку первого потенциального массива из приведённых maxal:

3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 157 197

Интересно: программа сама определяет магическую константу по введённому массиву, вводить её уже не надо. Ещё момент: программа перегруппировывает числа в массиве.

Итак, проверка первого потенциального массива из 36 чисел в программе svb началась



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

[Nataly-Mak]

И вот первый результат:

Summa=438
Time: 12424.34 sec

Массив из 36 чисел проверялся 3 ч. 45 мин.!
Решение не найдено.

Отлично! Теперь проверю остальные 10 потенциальных массивов из 36 чисел. Надеюсь, что они тоже проверятся за приемлемое время.

svb
а-у-у-у, где вы
вот вам первая оптимизация алгоритма поиска --- старая-престарая.
Идея maxal, что имеет смысл сразу проверять объединённый массив из 43 чисел, в данном случае не эффективна.

А проверка для N=38 всё ещё выполняется и до конца далеко.