Симметричные кортежи из последовательных простых чисел

[Evgeniy101]

Yadryara в сообщении #1676409 писал(а):

Остаток 12 по модулю 13 потеряли, остальное верно.

Потерял.

Yadryara в сообщении #1676409 писал(а):

Итого, у нас 3 остатка по модулю $13\#$ и 21 остаток по модулю $17\#$. Согласны?

Как-то 21 не понял, вижу только 7 в строке и всего 15 остатков разрешенных сосчитанных без перекрытия, т.е. одинаковые остатки увеличивали число сосчитанных.
Хорошо бы направить на путь истинный в этом и показать алгоритм дальнейших расчетов.

Dmitriy40 в сообщении #1676456 писал(а):

А я хотел попросить (в качестве упражнения) подробнейшим образом объяснить почему в список по модулю 13 не попали остатки 10 и 12. Именно оба (т.е. каждый отдельно). И максимально подробно. В надежде что в процессе ошибка обнаружится, а потраченное усилие по обоснованию поспособствует пониманию.

Evgeniy101
Впрочем, ещё не поздно, если есть желание и это не банальная опечатка от невнимательности.

Объяснить затрудняюсь, сосчитать легче:

П____k___k+П__MOD(13)
0___ 23___23__10
2___ 23___25__12
6___ 23___29__3
8___ 23___31__5
12__ 23__ 35__ 9
18__ 23__ 41__ 2
20__ 23__ 43__ 4
26__ 23__ 49__ 10
30__ 23__ 53__ 1
32__ 23__ 55__ 3
36__ 23__ 59__ 7
42__ 23__ 65__ 0
Имеется нулевой остаток у кандидата по модулю $13$, следовательно, при любом кандидате с остатком $10$ у младшего числа в кортеже, будет число без остатка делящееся на $13$, т.е. составное число, и такие кандидаты запрещены.

П____k___k+П__MOD(13)
0__ 103__103__12
2__ 103__105__1
6__ 103__109__5
8__ 103__111__7
12__ 103__115__11
18__ 103__121__4
20__ 103__123__6
26__ 103__129__12
30__ 103__133__3
32__ 103__135__5
36__ 103__139__9
42__ 103__145__2,
где П -- Паттерн, k -- kan, k + П -- Kan + Паттерн, MOD(13) - остаток по модулю $13$ у кандидата с остатком по первой строке, т.е. $10$ в первой таблице и $12$ во второй.
Кандидат с остатком $12$ у младшего числа предполагаемого кортежа может отыскаться со всеми простыми числами, т.к. нулевого остатка во второй таблице нет, а все кандидаты с остатком $12$ у младшего числа в кортеже будут иметь точно такие же остатки.

[Yadryara]

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

Теперь снова тот самый вопрос. Как зная все разрешённые остатки по модулям, определить формулы, по которым будем перебирать кандидатов?

Yadryara в сообщении #1672918 писал(а):

1 по модулю 2;
2 по модулю 3;
1 по модулю 5;
4 по модулю 7;
6 по модулю 11.

И далее я подробно расписал, заметьте без всякого КТО, как найти эту формулу:

$$1271+2310n$$

где $n = 0, 1, 2, 3, ...$

Теперь у нас новый простой модуль 13 и нам уже нужны формулы для разрешённых остатков

1 по модулю 2;
2 по модулю 3;
1 по модулю 5;
4 по модулю 7;
6 по модулю 11;
2, 4, 12 по модулю 13.

Все меньшие модули кроме 13 мы уже проверили. Значит проверяем только его.

Наш список пока подходящих чисел по всем остаткам по всем младшим модулям:

$ 1271, 3581, 5891, ...$

Какие числа из них имеют остаток $2$ по модулю $13$ ?
Какие числа из них имеют остаток $4$ по модулю $13$ ?
Какие числа из них имеют остаток $12$ по модулю $13$ ?

1271 имеет остаток 10 по модулю 13, не годится;
3581 имеет остаток 6 по модулю 13, не годится;
5891 имеет остаток 2 по модулю 13, ОК;
8201 имеет остаток 11 по модулю 13, не годится;
10511 имеет остаток 7 по модулю 13, не годится;
12821 имеет остаток 3 по модулю 13, не годится;
15131 имеет остаток 12 по модулю 13, ОК;
17441 имеет остаток 8 по модулю 13, не годится;
19751 имеет остаток 4 по модулю 13, ОК;
22061 имеет остаток 0 по модулю 13, не годится;
24371 имеет остаток 9 по модулю 13, не годится;
26681 имеет остаток 5 по модулю 13, не годится;
28991 имеет остаток 1 по модулю 13, не годится;

И дальше пошли повторы, остатки снова 10, 6, 2, ... :

31301 имеет остаток 10 по модулю 13, не годится;
33611 имеет остаток 6 по модулю 13, не годится;
35921 имеет остаток 2 по модулю 13, ОК;

И новый период будет равен $35921-5891=30030 = 13\#$

Теперь у нас не одна формула на периоде $11\#$, а три формулы на периоде $13\#$ :

$5891+13\# \cdot n$

$15131+13\# \cdot n$

$19751+13\# \cdot n$

А на периоде $17\#$ у нас будет 21 формула. Или, что то же самое, имеется 21 разрешённый остаток по модулю $17\#$.

Вопросы?

[Dmitriy40]

Evgeniy101 в сообщении #1676518 писал(а):

k -- kan

Контрольный вопрос: а можно было взять k=kan=10? Ведь именно этот остаток и есть для kan+0. Или надо только простое k=kan?

[Evgeniy101]

Dmitriy40 в сообщении #1676539 писал(а):

Evgeniy101 в сообщении #1676518 писал(а):

k -- kan

Контрольный вопрос: а можно было взять k=kan=10? Ведь именно этот остаток и есть для kan+0. Или надо только простое k=kan?

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

Ответ: да, можно было взять k=kan=10, как и иное любое целое число, т.к. остатки при тестировании всегда при этом идентичны.

[Dmitriy40]

ОК.

[Evgeniy101]

Yadryara в сообщении #1676533 писал(а):

А на периоде $17\#$ у нас будет 21 формула. Или, что то же самое, имеется 21 разрешённый остаток по модулю $17\#$.

Почему 21 разрешенный остаток?

-- 26.02.2025, 21:11 --

Yadryara в сообщении #1676533 писал(а):

А на периоде $17\#$ у нас будет 21 формула. Или, что то же самое, имеется 21 разрешённый остаток по модулю $17\#$.

Почему 21 разрешенный остаток тогда, когда модуль 17?

[Dmitriy40]

Evgeniy101 в сообщении #1676687 писал(а):

Почему 21 разрешенный остаток тогда, когда модуль 17?

Потому что 1 разрешённый остаток по модулю 11#, 3 разрешённых остатка по модулю 13 и 7 разрешённых остатков по модулю 17 вместе дают ровно 21 комбинацию (произведение всех количеств) по модулю 11#*13*17=17#. Что именно из этого непонятно? Почему из 3 и 7 получается 21? Ну так запишите какие числа от 0 по 220 (13*17-1) даёт остатки (2,4,12) по модулю 13, какие из них же даёт остатки (1,3,6,7,10,12,13) по модулю 17, сколько чисел совпадает по обоим модулям (мне руками лень, мне проще программку написать):

? select(i->setsearch([2,4,12],i%13),[0..13-1])
%1 = [2, 4, 12]
? select(i->setsearch([1,3,6,7,10,12,13],i%17),[0..17-1])
%2 = [1, 3, 6, 7, 10, 12, 13]
? select(i->setsearch([2,4,12],i%13),[0..13*17-1])
%3 = [2, 4, 12, 15, 17, 25, 28, 30, 38, 41, 43, 51, 54, 56, 64, 67, 69, 77, 80, 82, 90, 93, 95, 103, 106, 108, 116, 119, 121, 129, 132, 134, 142, 145, 147, 155, 158, 160, 168, 171, 173, 181, 184, 186, 194, 197, 199, 207, 210, 212, 220]
? select(i->setsearch([1,3,6,7,10,12,13],i%17),[0..13*17-1])
%4 = [1, 3, 6, 7, 10, 12, 13, 18, 20, 23, 24, 27, 29, 30, 35, 37, 40, 41, 44, 46, 47, 52, 54, 57, 58, 61, 63, 64, 69, 71, 74, 75, 78, 80, 81, 86, 88, 91, 92, 95, 97, 98, 103, 105, 108, 109, 112, 114, 115, 120, 122, 125, 126, 129, 131, 132, 137, 139, 142, 143, 146, 148, 149, 154, 156, 159, 160, 163, 165, 166, 171, 173, 176, 177, 180, 182, 183, 188, 190, 193, 194, 197, 199, 200, 205, 207, 210, 211, 214, 216, 217]
? select(i->setsearch([2,4,12],i%13)&&setsearch([1,3,6,7,10,12,13],i%17),[0..13*17-1])
%5 = [12, 30, 41, 54, 64, 69, 80, 95, 103, 108, 129, 132, 142, 160, 171, 173, 194, 197, 199, 207, 210]
? apply(i->i%13,%5)
%6 = [12, 4, 2, 2, 12, 4, 2, 4, 12, 4, 12, 2, 12, 4, 2, 4, 12, 2, 4, 12, 2]
? Set(%6)
%7 = [2, 4, 12]
? apply(i->i%17,%5)
%8 = [12, 13, 7, 3, 13, 1, 12, 10, 1, 6, 10, 13, 6, 7, 1, 3, 7, 10, 12, 3, 6]
? Set(%8)
%9 = [1, 3, 6, 7, 10, 12, 13]

Как видите чисел и правда 21, и все они имеют именно указанные остатки и по 13 и по 17.
Возьмите калькулятор и перепроверьте. И что другие числа 0-220 под два условия (остатки по двум модулям) одновременно не подходят.
Разумеется это всё проще было проделать на меньших паттернах (например на [0,6,12] или [0,2,6,8]), где меньше числа и меньше остатков, понять принцип и потом уже переходить к длинным паттернам и большим модулям.
Что теперь непонятно?

-- 27.02.2025, 00:28 --

Да, добавлю, произведение ровно потому что модули 11#, 13, 17 - взаимно просты, не имеют общих простых делителей, потому и произведение (что модулей, что количеств остатков). Разумеется можно брать любые другие модули, но если они не будут взаимно простыми, то с разрешёнными остатками начнётся чехарда (усложнится их расчёт), для взаимно простых же модулей есть удобные методы/формулы вычисления, потому такие модули удобны. А самыми удобными взаимно простыми модулями являются простые или их независимые (не имеющие общих простых делителей) произведения - т.е. например праймориалы.

-- 27.02.2025, 00:34 --

(Оффтоп)

Yadryara
Вы правда думаете что эти вот основы модулярной арифметики нужны именно здесь, именно в теме про поиск симметричных кортежей, а не в ПРР(М), где им и самое место? Может и деление с остатком тоже будете здесь разъяснять, тема ведь ещё не 100500 страниц, можно же?

[Yadryara]

Evgeniy101 в сообщении #1676687 писал(а):

Почему 21 разрешенный остаток тогда, когда модуль 17?

У Вас опечатка в вопросе? Вы хотели спросить не про 17, а про 17# ?

Предлагаю сначала ответить на вопрос:

Почему 3 разрешённых остатка тогда, когда модуль 13# ?

Мне представлялось, что намёк понятен:

Если понятно, как я вывожу формулы выше, то попробовав посчитать таким же способом формулы для модуля 17#, естественным образом получится 21 формула, по 7 новых формул получится для каждой из этих трёх:

Yadryara в сообщении #1676533 писал(а):

$5891+13\# \cdot n$

$15131+13\# \cdot n$

$19751+13\# \cdot n$

Dmitriy40 в сообщении #1676716 писал(а):

Вы правда думаете что эти вот основы модулярной арифметики нужны именно здесь, именно в теме про поиск симметричных кортежей, а не в ПРР(М), где им и самое место?

Я правда думаю что буду объяснять там, где задан вопрос. Насчёт отделения в другую тему не возражаю.

Dmitriy40 в сообщении #1676716 писал(а):

Может и деление с остатком тоже будете здесь разъяснять

Да, я готов объяснять и деление с остатком.

[Yadryara]

Кстати, попробовал подытожить наше движение к искомым кортежам на периоде 43# для паттерна [0, 2, 6, 8, 12, 18, 20, 26, 30, 32, 36, 42] :

Период     2#  3#  5#   7#   11#    13#    17#    19#  23#  29#  31#  37#  41#  43#
Остатков   1   1   1    1     1      3      7      7   11   17
Формул      1   1   1    1     1      3     21
KF          2   6  30  210  2310  10010  24310

Предлагаю заполнить таблицу полностью. Надеюсь понятно, что количества остатков указаны по тем простым модулям под которыми они стоят. А количество формул и Кэфы Фильтрации указаны уже под решётками, то есть они для периодов.

[Evgeniy101]

Yadryara в сообщении #1676735 писал(а):

Кстати, попробовал подытожить наше движение к искомым кортежам на периоде 43# для паттерна [0, 2, 6, 8, 12, 18, 20, 26, 30, 32, 36, 42] :

Период     2#  3#  5#   7#   11#    13#    17#   19#   23#  29#  31#  37#  41#  43#
Остатков   1   1   1    1     1      3      7      7   11   17
Формул      1   1   1    1     1      3     21
KF          2   6  30  210  2310  10010  24310

Предлагаю заполнить таблицу полностью. Надеюсь понятно, что количества остатков указаны по тем простым модулям под которыми они стоят. А количество формул и Кэфы Фильтрации указаны уже под решётками, то есть они для периодов.

Как я воспринял:

Dmitriy40 в сообщении #1676716 писал(а):

Да, добавлю, произведение ровно потому что модули 11#, 13, 17 - взаимно просты, не имеют общих простых делителей, потому и произведение (что модулей, что количеств остатков),

так дополнил таблицу.

Период     2#  3#  5#   7#   11#    13#    17#    19#   23#     29#    31#       37#        41#        43#
Остатков   1   1   1    1     1      3     7      7     11      17      19       25         29         32      
Формул      1   1   1    1     1     3     21    147   1617    27489  522291  13057275  378660975  12117151200
KF          2   6  30  210  2310  10010  24310

KF пока не дошло как рассчитывается и какую нагрузку он несет

[Yadryara]

Не-а, не совсем правильно, разве ж для модуля 43 32 разрешённых остатка?

А про KF Вы же сами писали, что сразу стало понятно:

Evgeniy101 в сообщении #1675515 писал(а):

Yadryara в сообщении #1675513 писал(а):

Сейчас, чтобы не пропустить никаких кортежей нужно рассматривать 4 числа из каждых 30. То есть кэф фильтрации равен 7.5.

А после проверок по модулю 7 нужно будет рассматривать в качестве кандидатов на начальное число кортежа 16 чисел из каждых 210. Кэф фильтрации уже не 7.5, а существенно выше — 13.125. Выше кэф — пропорционально выше и скорость поиска.

Сразу стало понятно!

Это важнейший показатель. Я нашёл кортеж по этому паттерну за полтора часа не потому что у меня шибко быстрый комп, как Вы подумали, а потому что кэф фильтрации для периода 43# был достаточно большой.

[Evgeniy101]

Yadryara в сообщении #1676774 писал(а):

Не-а, не совсем правильно, разве ж для модуля 43 32 разрешённых остатка?

31, тогда формул 11738490225.

Yadryara в сообщении #1676774 писал(а):

А про KF Вы же сами писали, что сразу стало понятно:

Я надеялся увидеть 30030, 510510, 9699690, т.е. праймориалы, но увидел иные числа, следовательно надо еще что-то понимать.

[Yadryara]

Evgeniy101 в сообщении #1676806 писал(а):

Я надеялся увидеть 30030, 510510, 9699690, т.е. праймориалы, но увидел иные числа, следовательно надо еще что-то понимать.

А Вы что их не видите?? Они же в верхней строке таблицы стоят, только в краткой записи: 13#, 17#, 19#, ... , 43#

[Evgeniy101]

Yadryara в сообщении #1676808 писал(а):

А Вы что их не видите?? Они же в верхней строке таблицы стоят, только в краткой записи: 13#, 17#, 19#, ... , 43#

Вижу, тогда что KF

[Yadryara]

Ну так я же цитировал уже их значения для другого паттерна и Вы сказали: "Сразу стало понятно!"

Хорошо, вот табличка для этого паттерна:

[0, 6, 12]

Период     2#     3#    5#       7#        11#
Остатков   1      2     2        4
Formul      1      2     4       16 
KF          2      3   7.5   13.125