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

[Nataly-Mak]

Пока проверка при N=38 ещё продолжается, анализирую массивы.

svb
пожалуйста, посмотрите картинку (если вы вообще смотрите в тему, в чём я сильно сомневаюсь ):



Итак, на картинке мы видим массив чисел, сформированный программой при введении N=38. Этот массив содержит 38 чисел.
По логике вашей программы при введении N=37 из массива удалится число 151, а при введении N=36 удалятся первые два числа - 151 и 179. Верно?
Проверила массивы из остающихся 37 чисел и 36 чисел. Нетрудно убедиться простыми вычислениями, что квадрат с магической констнтой 438 из этих наборов чисел построить невозможно. Поэтому программа мгновенно завершает работу с отрицательным результатом.

А вот массив из 38 чисел проверяется целый день; ну, вроде уже немного осталось, надеюсь догрызть до конца

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

Тем временем закончилась проверка второго потенциального массива из 36 чисел:

Summa=438
Time: 22818.92 sec

Решение не найдено.
Этот массив проверялся намного дольше первого массива.
Ну, всё-таки два массива за рабочий день проверены. Это уже хорошо.
Осталось проверить всего 9 массивов.

Если maxal представил все потенциальные массивы из 36 чисел, задача будет решена.

[Nataly-Mak]

Догрызла проверку при N=38.
Поскольку уже заполночь, время отрицательное получилось:
Time: -12941.49 sec
Время отрицательное, результат отрицательный...
Всё плохо, пошла спать

[Nataly-Mak]

Эх, ничего не понимаю по-английски
Похоже, английский у Radko плоховат, потому что Гугл вообще переводит его чёрт знает как
Вот, например, я спросила его:

Цитата:

Swen tests your squares?
What he has to say about pandiagonal square 7x7 of prime numbers?

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
S=1597

Поясню. Он пишет, что сотрудничает с неким товарищем по имени Sven (из Швеции).
Radko отвечает:

Цитата:

It's far from the minimal for the same reason I told you about the one with prime 1.
Sven, as I, believes that the sub-case of the minimal PDL 7x7 P should be of single digit number of primes above 227.

Единственное, что поняла из этого ответа: они оба считают, что приведённый мной квадрат далеко не минимальный. Почему они так считают, совсем не поняла.
Да, что-то такое он писал мне и о пандиагональном квадрате 7-го порядка, составленном из простых чисел плюс число 1 (магическая константа 1577). Но и это тоже не поняла.

Вот так переписываемся... Но кое-что всё-таки понимаем

Radko строит самые разные магические квадраты. Вчера прислал очень симпатичный квадрат 6-го порядка, составленный из простых чисел плюс число 1; при этом все простые числа заканчиваются единицей.

[svb]

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

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

Увы, пока от меня толку мало
В отношении своей программы я уверен, что она очень далека от "лучшего" варианта. Фактически в ней реализован перебор "в лоб", а такой перебор всегда плох. Применение ее для простых чисел тем более плох, т.к. не используются свойства этих чисел. Пандиагональные квадраты 6-го порядка, как мы знаем, накладывают серьезные ограничения на используемые наборы из 36 чисел. Об этом, вроде, и известно, но пока это не используется. Например, последовательные 36 чисел не могут дать решения, но программа будет тупо это решение искать. Явно требуется более глубокое теоретическое проникновение в задачу. Возможно, что это и сложно, но, тем более, интересно.

Замечание Radko "The 450 is indeed the lowest of primes from 3" достаточно сильное, но мы мало знаем, что за ним лежит. Аналогично и с шаблонами maxal.

Я вам присылал 2 решения для 450:

 179  23  29   5  47 167
  71  11 181 109  59  19
  43  61  89  53 131  73
 113 151  37   3  79  67
  13 103  17 107 127  83
  31 101  97 173   7  41

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

-1 -1 -1 -1 -1 -1
-1 -1  1  1  -1  1 
 1  1 -1 -1  -1  1
-1  1  1  3   1   1
 1  1 -1 -1   1 -1
 1 -1  1 -1  1  -1

Попробовал еще раз запустить свою программу, получил еще один квадрат с суммой 450:

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

Для суммы 414, которая невозможна, также попробовал поиск. На 35 чисел быстро выходит для N=40 и N=44. Что мешает найти решение?

[Nataly-Mak]

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

Для суммы 414, которая невозможна, также попробовал поиск. На 35 чисел быстро выходит для N=40 и N=44. Что мешает найти решение?

Мешает то, что магический квадрат 6-го порядка из (различных) простых чисел с такой константой не существует
35 элементов могут быть найдены, но полного решения быть не может.
Наименьший магический квадрат 6-го порядка из простых чисел имеет магическую константу 432, если мне не изменяет память. Поэтому для пандиагонального квадрата минимальная возможная магическая константа 438. Если для этой константы решения нет, тогда наименьшим будет квадрат, найденный Radko, с магической константой 450.

Я сейчас проверяю потенциальные массивы из 36 чисел (для константы 438) по вашей программе; они проверяются довольно быстро.

P.S. Немного забыла константу наименьшего магического квадрата 6-го порядка из (различных) простых чисел - не 434, а 432. Последовательность в OEIS A164843.

[svb]

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

Мешает то, что магический квадрат 6-го порядка из (различных) простых чисел с такой константой не существует

Да, уж ... Сумма первых 36 простых чисел $3+5+...+157=2582$, откуда и следует, что минимальная сумма не менее 432

Отсюда же следует, что для 438 максимальное простое число в наборе не превышает 199.

[svb]

Еще один квадрат с суммой 450:

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

[Nataly-Mak]

svb
Я писала в своём решении головоломки, что пандиагональные квадраты 6-го порядка найдены по вашей программе.
Radko уже не в первый раз просит проверить пандиагональный квадрат 6-го порядка из простых чисел плюс число 1 с магической константой 438. Вот цитата из только что полученного письма:

Цитата:

Can you, please, ask Belyaev to run constant 438 about PDL 6x6 including prime 1? I believe this might be the lowest PDL 6x6 P.

Теперь просьба адресуется вам

Как я уже писала, он уверен в минимальности магической константы 450 для пандиагонального квадрата 6-го порядка из (различных) простых чисел без использования числа 1. Не знаю, откуда у него такая уверенность. Однако он предполагает, что пандиагональный квадрат с магической константой 438 может существовать, если использовать число 1.

Уже давно пыталась это проверить: добавила число 1 к объединённому массиву из 43 простых чисел и запустила программу alexBlack. Программа работала с утра до вечера, не проверила даже первое число массива, на экране было написано только:

|43.

[svb]

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

Теперь просьба адресуется вам

Попытаюсь сейчас поискать.

Цитата:

Как я уже писала, он уверен в минимальности магической константы 450 для пандиагонального квадрата 6-го порядка из (различных) простых чисел без использования числа 1.

Предыдущий наш диалог открыл мне немного глаза на примерное направление рассуждений. Стало не так темно

[Nataly-Mak]

Отлично! Свет - это всегда хорошо

[Nataly-Mak]

Сделала программку для формирования потенциальных массивов из простых чисел (по 36) для магической константы 438.
Как и у maxal, у меня получилось 11 потенциальных массивов.

Но... перечитываю свою статью; там приведены ещё два необходимых условия, которым должны удовлетворять потенциальные массивы по 36 чисел.
Первое необходимое условие - сумма всех чисел массива должна быть равна 6S, S - магическая константа квадрата. Это понятно, все найденные массивы этому условию удовлетворяют, они и ищутся на основании этого условия.

Ещё два необходимых условия (копирую из статьи):

Цитата:

С. все числа массива можно разбить (хотя бы одним способом) на 9 групп по 4 числа так, что сумма чисел в каждой группе равна 2S/3;
D. все числа массива можно разбить (хотя бы одним способом) на 4 группы по 9 чисел так, что сумма чисел в каждой группе равна 3S/2.

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

Условия C и D следуют из теории пандиагональных квадратов Россера и были отмечены в этой теме Pavlovsky.

[Nataly-Mak]

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

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

Мешает то, что магический квадрат 6-го порядка из (различных) простых чисел с такой константой не существует

Да, уж ... Сумма первых 36 простых чисел $3+5+...+157=2582$, откуда и следует, что минимальная сумма не менее 432

Да, что-то мы запутались в трёх соснах...
Если не использовать число 3, что у нас получается?
Сумма первых 36 простых чисел в этом случае: $2582-3+163=2742$.
Откуда сразу следует, что в этом случае минимальная магическая константа пандиагонального квадрата не может быть меньше 462. И не надо делать вообще никакую проверку для магических констант 438 и 450!
Но maxal сообщил тогда, что и для константы 462 пандиагональный квадрат построить невозможно.

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

[svb]

Nataly-Mak
В квадратах 450 число 3 присутствует...

[Nataly-Mak]

Это мне известно
Проследите ещё раз за моими рассуждениями в последнем посте.

Потому maxal и не нашёл квадрат с константой 450, что он не использовал шаблоны с числом 3 (так он сам написал недавно). Только проверять-то в этом случае вообще было нечего
И так понятно, что в этом случае (без числа 3) квадрат с константой 450 не может быть построен.
Но вот почему у него получилось, что и квадраты с константами 462 и 474 не могут быть построены, - это не понятно.
Квадрат с константой 462 Radko нашёл. О квадрате с константой 474 пока ничего не известно, но думаю, что он тоже существует. И можно предположить, что оба эти квадрата можно построить без числа 3.
Сейчас найду квадрат Radko с константой 462, посмотрю, есть или нет в нём число 3.

Вот пандиагональный квадрат Radko 6-го порядка из (различных) простых чисел с магической константой 462:



Как я и предположила, в этом квадрате нет числа 3.
Возникает вопрос: почему maxal получил по своей программе, что такой квадрат невозможен
На этот вопрос может ответить только maxal, а он, увы, где-то далеко от данной темы.

[Nataly-Mak]

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

О квадрате с константой 474 пока ничего не известно, но думаю, что он тоже существует.

Уже известно
Эти два квадрата программа нашла очень быстро и продолжала дальше искать. Похоже, их много.

Summa=474
1:
 181  47 101   7 127  11
  79  23 103 157 107   5
 139  71  29  37  31 167
  19  89 163 109  53  41
  13 113  17  67  73 191
  43 131  61  97  83  59
Time: 805.31 sec
2:
 181  11  29   7 109 137
  13  83 163 139  17  59
  67 131  71  19  73 113
  31  47  43  97 149 107
 103 179  41  61  37  53
  79  23 127 151  89   5
Time: 1584.64 sec

В этих квадратах тоже нет числа 3, я сама выбросила это число при вводе исходного массива чисел.

Итак, квадраты со всеми магическими константами, которые мы в своё время пропустили (450, 462, 474), существуют. Не найден только ответ о квадрате с магической константой 438.
Этот ответ уже близко: мне осталось проверить всего 4 потенциальных массива из 36 чисел.