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

Форум для обсуждения вопросов математики

Модератор: Admin

nataly-mak
Сообщения: 29
Зарегистрирован: Вс авг 17, 2008 5:45 pm
Контактная информация:

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

Сообщение nataly-mak » Чт ноя 04, 2010 3:55 pm

Эта задача возникла в процессе построения примитивного квадрата 13х13, который нужен для построения пандиагонального квадрата 13-го порядка из простых чисел. Задача эта очень сложная. Я решала её методом смешанного достраивания. Один результат получен, но не совсем хороший: в квадрате повторились два числа.

Формулировка задачи:

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

Код: Выделить всё

305849, 306263, 310883, 312779, 313739, 317267, 318653, 322229, 335957, 341339, 364607, 372299, 512903

Разности между соседними членами этой последовательности:

Код: Выделить всё

414, 4620, 1896, 960, 3528, 1386, 3576, 13728, 5382, 23268, 7692, 140604

Требуется найти три последовательности из простых чисел такой же длины с такими же разностями между соседними членами. Числа в новых последовательностях должны быть больше первого числа заданной последовательности - 305849. Кроме того, во всех четырёх последовательностях числа должны быть различные.

Иммет ли решение эта задача? Я уже проверила много простых чисел и решение пока не нашла.
Можно ли доказать, что такие последовательности существуют или наоборот не существуют?

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

Подробнее о задаче можно посмотреть
здесь
или в теме "Магические квадраты".
Лучше один раз увидеть...

nuklear rider
Сообщения: 69
Зарегистрирован: Чт апр 19, 2007 1:07 pm

Сообщение nuklear rider » Пт ноя 05, 2010 12:27 am

Как бы это сказать - до сих пор не решена даже задача близнецов: существует ли бесконечно много пар простых чисел, разность между которыми равна 2. Та задача, которую предлагаете нам Вы, на порядок сложнее. И тем более никем пока не решена. Удачи в переборе чисел, может, случайно наткнетесь на решение ;)

nataly-mak
Сообщения: 29
Зарегистрирован: Вс авг 17, 2008 5:45 pm
Контактная информация:

Сообщение nataly-mak » Пт ноя 05, 2010 4:08 am

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

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

Мой алгоритм подробно изложен по указанным выше ссылкам. Кратко: строится большая матрица nxm, в которой есть и простые, и не простые числа. Но матрица составляется по закону примитивного квадрата.
Затем превращаем в этой матрице простые числа в единички, а не простые в нули и выделяем из матрицы квадрат 13х13 из единичек. Это и есть искомый примитивный квадрат, полностью состоящий из простых чисел.
По этому алгоритму я построила примитивный квадрат 11х11 из различных простых чисел, из которого получен пандиагональный квадрат 11-го порядка (по алгоритму Россера).
Так что, в этом алгоритме нет никакого перебора.

А в предложенной выше задаче (во втором варианте) надо найти всего одну последовательность из простых чисел с заданными разностями, 12 таких последовательностей уже найдены (по описанному алгоритму).
В этой задаче - да, простой перебор. Но вот он-то как раз ничего и не даёт пока. Я уже проверила большой массив простых чисел и нужную последовательность пока не нашла.
Так что, мне придётся вернуться к построению больших матриц и выделению из них квадрата 13х13.

А другие идеи есть? Ведь сложная задача тем и хороша, что решение не лежит на поверхности и надо думать, как его найти :wink:

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

Код: Выделить всё

823  1109  3203  5003  5623  6793  9209  26479  50789  63443  852689  1154819
991  1277  3371  5171  5791  6961  9377  26647  50957  63611  852857  1154987
1237  1523  3617  5417  6037  7207  9623  26893  51203  63857  853103  1155233
5857  6143  8237  10037  10657  11827  14243  31513  55823  68477  857723  1159853
7753  8039  10133  11933  12553  13723  16139  33409  57719  70373  859619  1161749
8713  8999  11093  12893  13513  14683  17099  34369  58679  71333  860579  1162709
12241  12527  14621  16421  17041  18211  20627  37897  62207  74861  864107  1166237
17203  17489  19583  21383  22003  23173  25589  42859  67169  79823  869069  1171199
34381  34667  36761  38561  39181  40351  42767  60037  84347  97001  886247  1188377
160591  160877  162971  164771  165391  166561  168977  186247  210557  223211  1012457  1314587
493693  493979  496073  497873  498493  499663  502079  519349  543659  556313  1345559  1647689
623431  623717  625811  627611  628231  629401  631817  649087  673397  686051  1475297  1777427
843757  844043  846137  847937  848557  849727  852143  869413  893723  906377  1695623  1997753


Разности между соседними числами в каждом столбце:

Код: Выделить всё

168, 246, 4620, 1896, 960, 3528, 4962, 17178, 126210, 333102, 129738, 220326


Имеем 12 последовательностей из различных простых чисел с заданными разностями. Осталось найти всего одну последовательность с такими же разностями! Важно: числа в искомой последовательности не должны совпасть с числами известных 12 последовательностей.
Лучше один раз увидеть...

nataly-mak
Сообщения: 29
Зарегистрирован: Вс авг 17, 2008 5:45 pm
Контактная информация:

Сообщение nataly-mak » Сб ноя 06, 2010 4:08 am

Забыла показать последовательность, найденную к 12 известным последовательностям, в которой только одно число не является простым:

Код: Выделить всё

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

Эта последовательность нашлась довольно быстро. Ещё находилось много последовательностей с двумя не простыми числами. Но вот полностью состоящую из простых чисел найти не удаётся :(
Лучше один раз увидеть...

nataly-mak
Сообщения: 29
Зарегистрирован: Вс авг 17, 2008 5:45 pm
Контактная информация:

Сообщение nataly-mak » Вс ноя 07, 2010 9:17 pm

Задача решена на форуме dxdy.ru.
Найден 13-ый столбец, он начинается с простого числа 175490449.
Результатом явился дьявольский квадрат 13-го порядка из простых чисел.

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

nataly-mak
Сообщения: 29
Зарегистрирован: Вс авг 17, 2008 5:45 pm
Контактная информация:

Сообщение nataly-mak » Вт ноя 09, 2010 8:20 am

Да, для тех, кто решал задачу достраивания примитивного прямоугольника или собирался её решать, но опоздал :)

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

Мной получено ещё несколько примитивных прямоугольников 13х12 и 12х13. Вот, например, прямоугольник 13х12:

Код: Выделить всё

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-ый столбец.
А это прямоугольник 12х13:

Код: Выделить всё

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

В этом прямоугольнике надо достроить 13-ую строку.

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

Примитивные прямоугольники я получаю методом смешанного достраивания, вообще-то преследую цель получить прмитивный квадрат 13х13, но пока не получается. Программу выделения квадрата или прямоугольника из единиц из большой матрицы nxm, состоящей из нулей и единиц, составил участник форума dxdy.ru. Тоже очень интересная задача. Я строю такие матрицы и по этой программе выделяю из них квадрат или прямоугольник из единиц максимального размера.

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