Интересная задачка: как автоматизировать выборку

[Nataly-Mak]

Задача с достраиванием примитивных прямоугольников оказалась не такой простой. Я уже проверила для обоих прямоугольников очень много массивов простых чисел, но нужные последовательности получить не удалось.
Для прямоугольника 13х12 удалось получить последовательность максимальной длины 12, то есть одно число в этой последоавтельности не является простым.
Существует ли вообще решение поставленной задачи? Это названное мной "чистое" достраивание. Прежде я решала задачу методом смешанного достраивания (получение больших матриц, в которых есть и простые и не простые числа, и выделение из них квадрата 13х13, полностью состоящего из простых чисел). Этот метод, похоже, быстрее приводит к результату, нежели "чистое" достраивание.

В общем, над задачей надо хорошо подумать. Можно ли доказать, что, например, достроить заданный примитивный прямоугольник 13х12 возможно или наоборот - невозможно? Найдётся ли на бесконечных просторах простых чисел ещё хоть одна последовательность с такими же разностями между соседними членами? Или таких последовательностей существует ровно 12 и все они уже найдены?

[Nataly-Mak]

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

Очевидно, что примитивный квадрат 13х13 можно составить из 13 арифметических прогрессий с одинаковой разностью.
Вот это уже точно теоретически можно сделать, ибо доказано, что существует арифметическая прогрессия из простых чисел любой длины, значит, существует арифметическая прогрессия длины 169, которая и даст нам 13 нужных прогрессий. Однако такая прогрессия пока не найдена. На сегодня найдена арифметическая прогрессия из простых чисел максимальной длины 26.
Уже имеем две прогрессии длины 13 с одинаковой разностью

Но нам не обязательно иметь одну прогрессию длины 169, достаточно найти 13 разных прогрессий длины 13, но с одинаковой разностью. Такие прогрессии, по-моему, найти проще, чем одну непрерывную прогрессию длины 169. Предлагаю всем попробовать решить эту задачу.

Вот минимальная прогрессия длины 13 из простых чисел:
14933623 + 30030n, n = 0, 1, ..., 12 (автор прогрессии David W. Wilson, 1999 г.).

[Nataly-Mak]

Много уже проверила простых чисел, нужную 13-ую последовательность так и не нашла.
Вот покажу последовательность, в которой только одно число не является простым:

1541963  1542131  1542377  1546997  1548893  1549853  1553381  1558343  1575521  1701731  2034833  2164571  2384897

Интересно, что такие последовательности (с одним не простым числом) встречаются и для чисел меньших первого числа 12-ой последовательности (имеются в виду первые числа последовательностей), например:

479209  479377  479623  484243  486139  487099  490627  495589  512767  638977  972079  1101817  1322143

Отписался бы хоть кто-нибудь, пробовавший решить задачу. Или таких нет?

[Nataly-Mak]

Задчу решил maxal. 13-ый столбец начинается с простого числа 175490449.
Результатом явился пандиагональный квадрат 13-го порядка.
Ещё помогал в построении этого квадрата EtCetera, он выделил из построенной мной матрицы примитивный прямоугольник 13х12, который затем достраивался до примитивного квадрата 13х13.

Теперь можно попытаться достроить полученный примитивный квадрат 13х13 до примитивного квадрата 17х17 из простых чисел (данный метод построения пандиагональных квадратов из примитивных квадратов по Россеру годится только для квадратов, порядок которых - простое число). Здесь уже надо достраивать и строки, и столбцы по тому же закону примитивного квадрата (одинаковые разности между соседними числами).

[Nataly-Mak]

Продолжаю решать задачу построения пандиагонального квадрата 13-го порядка из различных простых чисел.
Построенный квадрат имеет огромную магическую константу - 179870403.
Требуется найти квадрат с меньшей магической константой.
Получено ещё несколько примитивных прямоугольников 13х12 и 12х13. Вот, напримрер, один из них:

823 1109 3203 5003 5623 6793 9209 11399 177013 182653 233669 294773
1237 1523 3617 5417 6037 7207 9623 11813 177427 183067 234083 295187
1621 1907 4001 5801 6421 7591 10007 12197 177811 183451 234467 295571
5857 6143 8237 10037 10657 11827 14243 16433 182047 187687 238703 299807
7753 8039 10133 11933 12553 13723 16139 18329 183943 189583 240599 301703
8713 8999 11093 12893 13513 14683 17099 19289 184903 190543 241559 302663
12241 12527 14621 16421 17041 18211 20627 22817 188431 194071 245087 306191
13627 13913 16007 17807 18427 19597 22013 24203 189817 195457 246473 307577
17203 17489 19583 21383 22003 23173 25589 27779 193393 199033 250049 311153
127747 128033 130127 131927 132547 133717 136133 138323 303937 309577 360593 421697
427711 427997 430091 431891 432511 433681 436097 438287 603901 609541 660557 721661
598867 599153 601247 603047 603667 604837 607253 609443 775057 780697 831713 892817
740227 740513 742607 744407 745027 746197 748613 750803 916417 922057 973073 1034177

Каждый из полученных примитивных прямоугольников может быть достроен до примитивного квадрата 13х13, но какие получатся простые числа при достраивании? От этого будет зависеть магическая константа будущего пандиагонального квадрата.
Для приведённого прямоугольника я проверила простые числа до 10 млн., 13-ый столбец не нашёлся. Надо проверять дальше. Вполне возможно, что в результате достраивания этого прямоугольника получится ещё большая магическая константа, но возможно и обратное: магическая константа может оказаться меньше.

Наконец, есть альтернатива: совсем не обязательно использовать предложенный метод. Можно придумать другой алгоритм построения пандиагонального квадрата 13-го порядка и с помощью этого алгоритма построить квадрат с самой маленькой магической константой. Как пишет Зиммерманн в описании своего конкурса, его не интересует, какой вы будете пользоваться программой, важен результат.
Кто-то может взять лист бумаги, начертить матрицу 13х13 и заполнить её различными простыми числами так, что у него получится пандиагональный квадрат. А почему нет? Франклин, к примеру, строил свои знаменитые квадраты без компьютера и без программ, именно на листе бумаги.
Можно, например, использовать "тупой" перебор (основанный хотя бы на общей формуле пандиагонального квадрата 13-го порядка), но вряд ли он приведёт к цели в данном случае. Можно использовать вероятностный алгоритм (случайная генерация строк квадрата). Можно ещё что-нибудь придумать.
Задача для тех, кто любит решать нестандартные задачи.