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

[Evgeniy82]

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

Чтобы такой контрпример существовал, нужно чтобы по какому-то $p_x$ было ровно $k$ вычетов, это возможно только если $p_x=k$, т.е. в кортеж входит и $k$ тоже, что противоречит условию $p_1>k$.

С другой стороны, недопустимые кортежи всё же есть, например:
$5,7,11,13,17,23,29 \mod 7$
только он состоит не из последовательных простых чисел (19 пропущено). И соответственно я не уверен что его можно называть кортежем.

Пока не дошло.
Возьмем $5,7,11,13,17 \mod 7$ это точно кортеж, в нем 5 элементов, а младшее простое тоже 5 - этот кортеж допустимый?
Условие $p_1>k$ не выполнено ведь.

[Yadryara]

Evgeniy82 в сообщении #1667437 писал(а):

Возьмем $5,7,11,13,17 \mod 7$ это точно кортеж, в нем 5 элементов, а младшее простое тоже 5 - этот кортеж допустимый?

Да, и в таблице этот паттерн есть: 0 2 6 8 12. Но серийное решение не 5 (modulo 30), а 11 (modulo 30), то есть решение с 5-кой — единственное исключение.

[Evgeniy82]

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

То есть кортеж по паттерну [0, 6, 12, 18] допустим, их полным-полно. А найдёте Вы хоть один кортеж по паттерну [0, 6, 12, 18, 24] ?

Поехали.

Пять простых расположенных через модуль $6$ не существует.
А вот показать это математически не могу.

[Dmitriy40]

Evgeniy82 в сообщении #1667437 писал(а):

Возьмем $5,7,11,13,17 \mod 7$ это точно кортеж, в нем 5 элементов, а младшее простое тоже 5 - этот кортеж допустимый?
Условие $p_1>k$ не выполнено ведь.

Да, допустимый: нет ни одного простого $p$, по которому числа $5,7,11,13,17$ покрывают все возможные остатки. В частности, по модулю $p=5$ числа дают следующие остатки: $0,2,1,3,2$ - их лишь 4 штуки разных, не 5, и остаток 4 остаётся допустимым (по модулю 5).
Следующие кортежи с тем же паттерном $[0,2,6,8,12]=[2,4,2,4]$:
$[11, 13, 17, 19, 23]$
$[101, 103, 107, 109, 113]$
$[1481, 1483, 1487, 1489, 1493]$
$[16061, 16063, 16067, 16069, 16073]$
$[19421, 19423, 19427, 19429, 19433]$

При чём здесь $p_1=5$ мне непонятно. Возможно можно перейти и к этому условию допустимости, но вот равносильно ли оно я не понимаю.

Evgeniy82 в сообщении #1667444 писал(а):

Пять простых расположенных через модуль $6$ не существует.
А вот показать это математически не могу.

Это не сложно: Такой кортеж покрывает все 5 возможных остатков по модулю 5, т.е. в частности и остаток 0, т.е. одно из его чисел обязано делиться на 5, а такое простое число лишь одно - само число 5. Прямая проверка с числом 5 на любой позиции кортежа говорит что кортежа с такими разностями не существует (вокруг числа 5 разности 2 вместо требуемых 6). Доказано.

[Evgeniy82]

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

Evgeniy82 в сообщении #1667437 писал(а):

Возьмем $5,7,11,13,17 \mod 7$ это точно кортеж, в нем 5 элементов, а младшее простое тоже 5 - этот кортеж допустимый?

Да, и в таблице этот паттерн есть: 0 2 6 8 12. Но серийное решение не 5 (modulo 30), а 11 (modulo 30), то есть решение с 5-кой — единственное исключение.

Как понимать когда брать какой модуль из праймориалов $6,30,210,...$ ?

-- 28.12.2024, 13:57 --

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

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

Приближаюсь к пониманию, но еще спрошу.

Для недопустимых кортежей обязательно существует какой-нибудь остаток от чисел увеличенных на второе число паттерна и деленный на количество элементов в нем равный нулю?
$(0,6,12,18,24)+6=(6,12,18,24,30)$, где $5$ - количество элементов в кортеже
Тогда (6,12,18,24,30) (modulo 5)=(1,2,3,4,0)

[Dmitriy40]

Evgeniy82 в сообщении #1667448 писал(а):

Для недопустимых кортежей обязательно существует какой-нибудь остаток от чисел паттерна равный нулю?

Конечно, иначе как покрыть ровно все $n$ разных остатков по числу (модулю) $n$ ...

Evgeniy82 в сообщении #1667448 писал(а):

Как понимать когда брать какой модуль из праймориалов $6,30,210,...$ ?

Никак, можно брать любой, на выбор. Можно даже не из праймориалов, вообще по любому числу, например произведение нескольких произвольных простых. Просто праймориалы кое в чём удобнее (например коротким обозначением).

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

[Yadryara]

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

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

Кстати, да, как раз хотел сказать, что вот есть такой интересный период в той же таблице: $11741730 = 2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot23$

Может они подбирали период так, чтобы серийная добавка была единственной?

Но тогда это означает, что и нам необязательно было выбирать между 67# и 71#, а взять промежуточный период, например 67 убрать, а 97 добавить? Правда, тогда количество кандидатов возрастёт в $\frac{78}{48}$ раз. Плохо: это больше чем $\frac{97}{67}$.

[Evgeniy82]

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

Evgeniy82 в сообщении #1667437 писал(а):

Возьмем $5,7,11,13,17 \mod 7$ это точно кортеж, в нем 5 элементов, а младшее простое тоже 5 - этот кортеж допустимый?

Да, и в таблице этот паттерн есть: 0 2 6 8 12. Но серийное решение не 5 (modulo 30), а 11 (modulo 30), то есть решение с 5-кой — единственное исключение.

Тут у меня возник еще вопрос, который остается:

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

Evgeniy82 в сообщении #1667448

писал(а):
Как понимать когда брать какой модуль из праймориалов $6,30,210,...$ ?

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

Никак, можно брать любой, на выбор. Можно даже не из праймориалов, вообще по любому числу, например произведение нескольких произвольных простых.

Если любой модуль можно взять, то беря модуль $6$ пройдя по $((96)$$(5,7,11,13,17)) \mod 6$, получим $(101,103,107,109,113) \mod 6$ такой кортеж и множество иных такой же конфигурации.
Наверно все-таки надо по некоему правилу выбирать модуль?

[Yadryara]

Evgeniy82, поправьте цитирование, плиз. Часть слов принадлежит не мне.

Evgeniy82 в сообщении #1667489 писал(а):

Наверно все-таки надо по некоему правилу выбирать модуль?

Чтобы легче было искать кортежи лучше брать модуль побольше. И совсем необязательно, чтобы добавка была только одна. Что эффективнее перебирать одну добавку с шагом 6 или две добавки с шагом 30? Что быстрее перебирать две добавки с шагом 30 или пять добавок с шагом 210? Очевидно, что оба раза лучше выбирать больший период.

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

[Evgeniy82]

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

Evgeniy82, поправьте цитирование, плиз. Часть слов принадлежит не мне.

Поправил. Прошу прощение за оплошность.

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

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

Можно пропустить подходящий

[Yadryara]

Evgeniy82 в сообщении #1667503 писал(а):

Можно пропустить подходящий

Нет, не в этом дело. Мы вот нашли 293 квадриллиона добавок в периоде 67#. И умеем их генерить по всему этому периоду. А не будет ли эффективней считать на периоде 997# ? На первый взгляд, да. Но увы, не придумано способа как генерить добавки в самом низу этого периода, среди самых маленьких чисел...

[Evgeniy82]

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

Evgeniy82 в сообщении #1667503 писал(а):

Можно пропустить подходящий

Нет, не в этом дело. Мы вот нашли 293 квадриллиона добавок в периоде 67#. И умеем их генерить по всему этому периоду. А не будет ли эффективней считать на периоде 997# ? На первый взгляд, да. Но увы, не придумано способа как генерить добавки в самом низу этого периода, среди самых маленьких чисел...

В вашу работу я еще не въехал. С базовыми понятиями еще у меня не все хорошо.

В выходные буду редко.

[Dmitriy40]

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

Правда, тогда количество кандидатов возрастёт в $\frac{78}{48}$ раз. Плохо: это больше чем $\frac{97}{67}$.

Зато вместо $41\#$ лучше брать $43\#/41=43\times37\#$, потому что и для 41 и для 43 количество допустимых остатков одинаково, 24шт, а $\frac{41}{24}<\frac{43}{24}$. Аналогично для $[3\ldots17]$, $[19,23]$, $[29,31]$ - для всех этих комбинаций количество остатков одинаково и лучше брать не праймориал.
Я несколько раз видел даже и уменьшение количества допустимых остатков для большего простого, не помню для каких паттернов.

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

А не будет ли эффективней считать на периоде 997# ? На первый взгляд, да. Но увы, не придумано способа как генерить добавки в самом низу этого периода, среди самых маленьких чисел...

Ну почему не придумано, побить весь 997# на части, например 67# и несколько остальных и применить КТО (которая сильно упрощается если не нужны числа больше первого модуля, 67#, до проверки равенства по модулю). Вот только это будет сильно медленнее чем сейчас. А попытки ускорить приводят обратно к текущему алгоритму. Так что не придумано столь же быстрого/эффективного способа.
Вернее я знаю такой способ, в 64 раза быстрее текущего, две итерации по 12 вычислительных команд заменяются на две команды, выполняемые обе за такт, можно обработать не 32 числа за 4 такта, а 512 чисел за такт, только уже трижды писал тесты и все они показывают реальную скорость в разы ниже текущей - слишком много накладных расходов и мал объём кэша L2 (а L3 и тем более память не успевает).

[Yadryara]

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

Ну почему не придумано, побить весь 997# на части, например 67# и несколько остальных и применить КТО (которая сильно упрощается если не нужны числа больше первого модуля, 67#, до проверки равенства по модулю).

Может мы о разном говорим? Я-то говорю о том, о чём говорил ещё прошлым летом.

Чем больше период, тем лучше фильтрация. Но КТО будет генерить добавки по всему огроменному диапазону.
Ещё вот здесь расписано, как генерить добавки. Но они же всё равно генерятся по всему диапазону. В этом с тех пор прогресса нету. Или есть?

[Dmitriy40]

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

Чем больше период, тем лучше фильтрация. Но КТО будет генерить добавки по всему огроменному диапазону.
Ещё вот здесь расписано, как генерить добавки. Но они же всё равно генерятся по всему диапазону. В этом с тех пор прогресса нету. Или есть?

Да, КТО генерит добавки по всему диапазону. Но проблема не только сгенерить добавки, но и проверить их на кортеж 19-252, это значительно дольше. И по ссылке как раз как проверять добавки используя КТО и не генеря при этом саму добавку, а только и нужные вычеты/остатки по модулям простых. Как работает сама КТО было понятно и до того, вопрос был как её применить для получения вычетов без использования медленных команд делений.
Про прогресс уже сказал: идеи есть, но на практике они все оказываются медленнее текущего варианта. В разы.

Ограничить же КТО небольшим диапазоном легко. Для примера возьму диапазон 67#, т.е. надо среди 997# найти только добавки меньшие 67#. При этом считаем что 293e15 добавок в 67# уже известны (это не обязательное условие, так проще объяснить).
Смотрим на формулу КТО для двух векторов $x_i,y_j$: $x=x_i+Mx(((y_j-x_i)d_l) \bmod My_l)$, где $x_i<Mx, y_j<My_l, d_l=\frac{1}{Mx}\bmod My_l$. Положим $Mx=67\#$, тогда $x_i$ это вектор из 293e15 добавок по модулю 67#.
В $My_l$ подставляем оставшиеся простые по 997 в любом порядке, в том числе их произведения. Чтобы при этом число $x$ осталось меньше 67# надо чтобы второе слагаемое было равно нулю. Это возможно только если $y_j=x_i \mod My_l$, именно по модулю $My_l$ (именно это портит всю малину). Т.е. для каждого $x_i$ надо проверить существуют ли $y_j$ (для каждого $My_l$) равные по соответствующему модулю $x_i$. Если не существуют, то такая добавка $x_i$ отбрасывается.
В пределе, если каждый раз $My_l$ просто одно из простых чисел, в $y_j$ будут лишь допустимые вычеты/остатки по этому простому. Их много. Потому выгоднее сделать обратное сравнение, иметь список запрещённых остатков вместо разрешённых, запрещённых всего 19шт независимо от величины простого (для простых больше 41). И тогда достаточно сравнить каждую добавку $x_i$ по модулю каждого простого 71-997 с 19-ю числами (причём эти 19 чисел можно сделать одинаковыми для всех простых больше 252), при первом же совпадении добавку $x_i$ отбрасывать.
Собственно всё. Не отброшенными останутся только те добавки $x_i$ которые по модулю 997# дают число меньше $Mx=67\#$, что и требовалось.
Вместо вычисления сначала полного огроменного числа $x$ и потом долгого деления на малое простое для получения остатка можно оперировать лишь остатками по малым простым и вместо умножений и делений выполнять простое сравнение на равенство.
Да, если есть лишь $x_i$, то их по любому придётся делить на все простые 71-997 для получения остатков, но, как собственно и было показано в январе, можно и не хранить и не вычислять все $x_i$, а получать из массивов меньших размеров сразу остатки по простым 71-997, без умножений и делений, только лишь сравнениями и сложениями/вычитаниями, причём не больших чисел, а весьма малых, лишь по модулям простых 71-997, что тоже заметно проще и быстрее.

-- 29.12.2024, 09:20 --

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

Собственно всё. Не отброшенными останутся только те добавки $x_i$ которые по модулю 997# дают число меньше $Mx=67\#$, что и требовалось.

Если внимательно посмотреть, то это просто переформулировка что добавка $x_i$ имеет разрешённые остатки по простым 71-997.
Поэтому сейчас программа фильтрует по простым 71-131071 и выдаёт лишь те добавки по модулю 67#, которые имеют разрешённые остатки по всем простым 71-131071, что равносильно тому что эти добавки по модулю 131071# дают числа меньшие 67#. Номер периода 67# учитывается отдельно и в общем на вышесказанное не влияет.