Кортежи из простых чисел

[Dmitriy40]

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

И какие же нынче не закрытые вопросы по CPAP-x-210? Только по CPAP-7-210 и выше?

Ну вопросы можно наверное придумать разные, а вот минимальные кортежи найдены для всех длин по 6 включительно, в указанной A301810. Там же есть и лучшее ограничение на CPAP-7-210 (и оно же есть в https://www.pzktupel.de/CPAP/mini.php и в http://primerecords.dk/cpap.htm#smallest).

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

Как понимаю, не с тем же диаметром, а с теми же гэпами.

Да, конечно, оговорился.
Только не гэпами, а интервалами.

[Yadryara]

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

Только не гэпами, а интервалами.

Не люблю спорить о терминологии, но здесь поспорю. Гэп понимается в конкретном смысле: prime gaps A001223.

А интервал это то же что и диапазон. То есть в интервале от нуля до 21 миллиона, видимо, встречается лишь один гэп равный 210.

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

Прямая проверка это подтвердила за 1ч (до первого):Код:

? q=w=0; forprime(p=2,oo, if(p-w==210 && w-q==210, print(q)); q=w; w=p; );

Повозился с этой простейшей программой в Убунте. Сначала смотрел сколько времени занимает счёт одного интервала длиной в миллиард, например:

print; q=w=0; forprime(p=249e9,250e9, if(p-w==210 && w-q==210, print(q)); q=w; w=p; );

И обнаружил скачок:

   e9   real time + 1e9, sec
    1                 10.409
   10                 10.555
  100                  9.780
  200                  9.832
  240                  9.951
  244                 10.057
  245                 10.567
  246                 10.607
  247                  9.849
  248                  9.905
  249                 11.808
  250                 75.757

То есть где-то не доходя до 250 ярдов, время, видимо, скачком увеличивается семикратно. Посмотрел поточнее:

      e6   real time + 1e8, sec
  249700                  0.999
  249800                  1.101
  249900                  2.462
  250000                  7.647
  250100                  7.677
...
  250700                  7.513
  250800                  7.544

Да, с какого-то числа вблизи 249900000000, начинает гораздо дольше считать.

[Dmitriy40]

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

Да, с какого-то числа вблизи 249900000000, начинает гораздо дольше считать.

Это почти наверняка связано с размером таблицы простых primelimit, похоже на квадрат максимального простого из таблицы (порядка 500000), потому что в новых версиях PARI цикл forprime использует решето Эратосфена для ускорения, а тому нужны простые до корня. Поменяйте primelimit (он действует только при запуске PARI) и перетестируйте скорость.

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

Не люблю спорить о терминологии, но здесь поспорю.

А я не люблю насаждать англицизмы без нужды. Gap вполне переводится на русский, на "интервал" не настаиваю.

[Yadryara]

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

Поменяйте primelimit (он действует только при запуске PARI) и перетестируйте скорость.

Вообще да, об этом же на первой странице интерактивного курса по PARI рассказано.

Да, в Убунте 500000. Но default(primelimit,10^6) не помог — скорость та же.

А в Виндовской PARI уже 2^20 (1048576). Хотя обычно эта версия медленнее. Как и сейчас до порога она медленнее: считает миллиард за 14 секунд вместо 10 в Убунте, но она зато так и продолжает считать по 14 секунд, а не перескакивает на 75 секунд.

Да, дело в пороге 500000, просто, видать, не удаётся его так просто изменить что ли.

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

А я не люблю насаждать англицизмы без нужды.

Я-то считаю что нужда есть, но здесь развивать эту мысль не буду. Вроде была об этом тема.

[Dmitriy40]

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

Но default(primelimit,10^6) не помог — скорость та же.

Может не перезапустили PARI? В доке прямо написано:

Цитата:

3.4.31 primelimit.
...
This default is only used on startup: changing it will not recompute a new table.

Я себе в файле gprc.txt написал другой primelimit=... (без default и прочего) и у меня скорость падает позже (зато дольше запускается сам gp.exe).

[Yadryara]

Я так понял что команды default(timer,1) и default(primelimit,10^6) работают только на одну сессию. Перезаходишь, снова 500000 и снова нет автоматического вывода времени. С gprc пока не стал разбираться. Всё равно довольно быстро посчитались все 14 CPAP-3-210 до триллиона:

264860525297
288603524707
472173513523
472468296407
496175478451
603808685273
649711478681
675580812497
788796373567
813186292493
859175566397
912066019591
949580295659
973684246399

А ИИ нашёл только одну из них (603), несмотря на его заявление что ищет все.

[Cantata]

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

А можно скриншот посмотреть? 12 потоков были задействованы?

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

97: 45194847791 (vremya: 290.390 sek)
98: 45321778427 (vremya: 291.307 sek)
99: 46006843591 (vremya: 296.298 sek)
100: 47023892827 (vremya: 303.534 sek)

Gotovo! Multithreading variant nashel 100 elementov za 304 sekund.

5min, 18,035 ms

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

Так что минимальным CPAP-3d210 является 264860525507-210=264860525297.

Оно же есть в A224324
и A301810
(тут и остальные длины с тем же диаметром интервалом/шагом).

Прямая проверка это подтвердила за 1ч (до первого):Код:

Спасибо!

[Dmitriy40]

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

Я так понял что команды default(timer,1) и default(primelimit,10^6) работают только на одну сессию. Перезаходишь, снова 500000 и снова нет автоматического вывода времени. С gprc пока не стал разбираться.

Любые изменения работают только внутри одной сессии.
Чтобы работало всегда и придуман файл gprc.txt.

[Yadryara]

Cantata

Cantata в сообщении #1726175 писал(а):

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

Ну вот видите! Только что говорил что люди ухитряются друг друга не понимать даже когда говорят на одном и том же языке!

Вот же я про что говорил:

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

Номинальное количество потоков можно посмотреть в многопоточной версии PARI. А можно и через знаменитую программу primesieve. У меня скачана сравнительно недавняя версия:

primesieve 12.13
February 05, 2026
Kim Walisch, <[e-mail]>

Это написано в файле "README.txt". Вот как мой комп ищет все простые до триллиона:

C:\PrimeSieve>primesieve 1e12
Sieve size = 256 KiB
Threads = 12
100%
Seconds: 28.035
Primes: 37607912018

Видите, программа задействовала все 12 потоков (Threads). Попробуйте, заодно ещё раз скорость сможем сравнить.

Видите, здесь 28 секунд и 12 потоков (Threads) ?

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

[Dmitriy40]

>primesieve 1e12
Sieve size = 128 KiB
Threads = 4
100%
Seconds: 66.134
Primes: 37607912018

[Yadryara]

Ну вот, вижу что Дмитрий меня правильно понял и написал ровно то, о чём я говорил.

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

вспоминать как ищутся кортежи. Для этого планирую вернуться к прошлой зиме, где мы подробнейшим образом объясняли Evgeniy101 как искать кортежи. Я спустился ещё ниже и объяснял на самом примитивном уровне и только тогда он понял. Это примерно 50-60-е страницы темы СКППЧ.

Да, 52-я страница. Причём здесь как раз о CPAP шла речь:

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

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

Можно проще разъяснить это?

Не только можно, но и нужно. Возможно, и Демису пригодится.

Я же Вас специально к этому подводил:

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

А можно ли найти кортеж с тремя подряд гэпами равными 6? Да.

А с четырьмя? Попробуйте. Не натолкнётесь ли Вы на некое теоретическое препятствие?

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

Поехали.

Чётные числа сразу отбрасываем. Иными словами, допустимый остаток по модулю 2 только один и равен 1-це.
Наименьшее нечётное простое — 3. Ставим его на первую позицию. Тогда следующее число 9. Остаток по модулю 3 в обоих случаях равен 0. Это недопустимый остаток. Для любого модуля. Ну не может число быть простым, если оно делится нацело на простое, кроме самого этого числа.

Берём следующее простое — 5. Остаток по модулю 3 равен 2. Остаток для числа на 2-й позиции, то есть для числа 11 по модулю 3 тоже равен 2-м. Нетрудно увидеть, что и для всех остальных чисел кортежа он будет равен 2-м.

Берём следующее простое — 7. Остаток по модулю 3 равен 1.
Снова смотрим числа на всех позициях паттерна. Тщательно расписываем остатки по самым маленьким модулям.

Попробуйте. Если что-то непонятно, спрашивайте, не стесняйтесь

А на 58-й странице и программа есть.

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

Но ведь фильтрация по разрешённым остаткам гораздо более сильная, чем по простым. По крайней мере для тех периодов о которых шла речь.

А сейчас, кстати, для столь коротких цепочек как тройки и четвёрки, фильтрация по разрешённым остаткам не всегда сильнее. Поэтому простейшая программа Дмитрия эффективна. Но я всё-таки пытался поискать по праймориалам. Тройки находятся и в большом количестве, четвёрки — пока нет. Подробнее расскажу позже.

[Yadryara]

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

Тройки находятся и в большом количестве, четвёрки — пока нет.

Ну вот и 4-ка нашлась. Имею в виду CPAP-4-210:

11669531963218422221

Нашлась она на периоде 53#. Кэф фильтрации всего лишь 42.9.

Можно, кстати, не в OEIS смотреть, а вот сюда: https://en.wikipedia.org/wiki/Prime-counting_function

Для $10^{19}$ кэф фильтрации 42.7, для $10^{20}$ — 45.0.

Ну то есть очень близкие кэфы. У традиционного способа (через праймориалы) пока не видно явного преимущества.

Если кто-то не понимает о чём речь: вблизи $10^{20}$ примерно каждое 45-е число натурального ряда является простым.

[Dmitriy40]

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

Ну вот и 4-ка нашлась. Имею в виду CPAP-4-210:
11669531963218422221

А из A301810 известна минимальная CPAP-4-210: 110176968196069, на 5 порядков меньше однако. Т.е. должна найтись и на периоде 41#, среди почти 9.234трлн кандидатов, с кэфом фильтрации 32.95 (против ln(41#)=33.35).

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

Нашлась она на периоде 53#. Кэф фильтрации всего лишь 42.9.

Я бы сказал 42.95, округлять 0.04915 до нуля как-то слишком грубо ИМХО.

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

Для $10^{19}$ кэф фильтрации 42.7, для $10^{20}$ — 45.0.

И тоже я бы сказал чуть точнее: 43.75 и 46.05.
А именно для 53# кэф будет $\ln(53\#)\approx44.93$.

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

вблизи $10^{20}$ примерно каждое 45-е число натурального ряда является простым.

Соответственно 46-е, не 45-е. Ошибка невелика конечно, но зато заметно дальше от 42.95.

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

Можно, кстати, не в OEIS смотреть, а вот сюда: https://en.wikipedia.org/wiki/Prime-counting_function

Что смотреть? Не увидел на этой странице ни одного из чисел 264860525297, 110176968196069, 11669531963218422221, ни аббревиатуры CPAP.
А факт $\pi(x)\approx x/\ln(x)$, т.е. кэф примерно равен натуральному логарифму, общеизвестен (всем кто хоть чуточку интересуется простыми числами).

[Yadryara]

Dmitriy40, сейчас пока в эти тонкости вникать не хочется.

Тем более что для CPAP-5-210 на периоде 59# кэф при стандартной фильтрация явно лучше: 92.8.

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

Что смотреть?

Смотреть сколько простых до какой-нибудь ближайшей степени 10-ки.

Например, вот primesieve только недавно проверяли до $10^{12}$ : 37,607,912,018 — совпадает.

И для 59# по этой таблице можно прикинуть и без логарифма. Поскольку 59# повыше чем $10^{21}$, можно грубо взять $\frac1{21}$, то есть кэф в районе 48. Он же явно хуже чем 92.8.

[Dmitriy40]

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

Смотреть сколько простых до какой-нибудь ближайшей степени 10-ки.

Зато в OEIS есть и до праймориалов A000849, и до факториалов A003604, и до степеней двойки A007053, и тройки A055729, и до квадратов простых A000879, и кубов A086688, и много других.

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

Тем более что для CPAP-5-210 на периоде 59# кэф при стандартной фильтрация явно лучше: 92.8.

Разумеется чем длиннее паттерн, тем больше выигрыш проверки по остаткам относительно тотальной.

-- добавлено через 6 минут --

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

И для 59# по этой таблице можно прикинуть и без логарифма.

А зачем? У меня калькулятор (и PARI/GP и гугл) всегда под рукой и вбить в него $\ln(59\#)$ секундное дело.
Вот $\pi(x)$ для больших $x$ (для малых или помню, или есть PARI) приходится поискать, да. Но и нужно это значение очень нечасто. А примерно прикинуть можно опять же на калькуляторе через логарифм.