кортежи последовательных простых. ключ к 19-252

[Dmitriy40]

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

[vicvolf]

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

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

А какой наибольший интервал перебора проверен?

[Dmitriy40]

vicvolf в сообщении #1632216 писал(а):

А какой наибольший интервал перебора проверен?

Очень сильно зависит от паттерна (k-tuples), для некоторых проверено очень далеко, для многих лишь примерно до $10^{31}$, для того что в этой теме 19-252 я проверил лишь до $10^{24}$ (примерно, за почти год, это почти $10^{18}$ кандидатов). Ещё для многих и многих проверено практически тотально до $9\cdot10^{18}$ (это несколько боинк проектов считали), там найдены все цепочки что вообще искали (а искали не все возможные, это собственно неопределённое понятие), но даже и это миллионы цепочек/кортежей.
В общем всё зависит что именно искать.

[vicvolf]

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

Ещё для многих и многих проверено практически тотально до $9\cdot10^{18}$ (это несколько боинк проектов считали), там найдены все цепочки что вообще искали (а искали не все возможные, это собственно неопределённое понятие), но даже и это миллионы цепочек/кортежей.

А как распределяются вычисления между участниками боинк проектов, чтобы они не считали одинаковые промежутки?

-- 09.03.2024, 10:03 --

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

для того что в этой теме 19-252 я проверил лишь до $10^{24}$ (примерно, за почти год, это почти $10^{18}$ кандидатов).

Вы потратили почти год, а может кто-то в проектах уже считал этот интервал?

[Dmitriy40]

vicvolf в сообщении #1632282 писал(а):

Вы потратили почти год, а может кто-то в проектах уже считал этот интервал?

Кто-то точно этот интервал уже считал, и не один раз. Даже я сам его уже считал, десятки раз.
НО! Простых чисел очень много, и структур на них можно понастроить очень разных, потому искать и хранить на будущее просто абсолютно все простые - идиотизм (и места не хватит, и снова найти их быстрее чем считать из БД такого размера), ищутся всегда какие-то структуры на множестве простых (некие подмножества), и вопрос какие именно это структуры/подмножества.
Вот например интервал до 1e15 я выше считал два раза, для двух таблиц (num17 и num15), хотя он был мною же просчитан ещё лет 10 назад, плюс потом в боинк, плюс для поиска 19-252 тоже был просчитан, плюс ещё для множества разных других паттернов тоже был каждый раз снова просчитан - потому что каждый раз искались разные структуры/подмножества на простых числах и прочие игнорировались.

vicvolf в сообщении #1632282 писал(а):

А как распределяются вычисления между участниками боинк проектов, чтобы они не считали одинаковые промежутки?

Можно по разному, но наиболе просто и логично выявить (или задать) интервал который считается в среднем около (полу)часа и поделить всю задачу/работу на такие интервалы и выдавать каждому компу свой интервал, ведь расчёт внутри каждого интервала независим (за исключением начальной инициализации, но это секунды). Есть некоторые тонкости и хитрости, но в общем так.

[vicvolf]

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

для того что в этой теме 19-252 я проверил лишь до $10^{24}$

Я прикинул, чтобы встретить данный кортеж надо проверить не меньше, чем до $10^{36}$.

[Dmitriy40]

vicvolf в сообщении #1632305 писал(а):

Я прикинул, чтобы встретить данный кортеж надо проверить не меньше, чем до $10^{36}$.

Это явно сильно завышенная оценка, я выше по методу Yadryara посчитал что до 5e25 должно быть в среднем 154 цепочек (возможно с лишними простыми между нужными). Если даже как для более коротких на каждые 30-40 цепочек с лишними простыми приходится одна правильная (без лишних простых), то всё равно до 5e25 должно быть 4-5 искомых цепочек.
Оценка по тренду по более коротким цепочкам вообще даёт оценку первой цепочки до 2e24.

Оцените своим методом ожидаемый интервал для центральных 17 чисел из этого паттерна (17-240) и сравниtе с реально найденным решением практически на 1e21 (при том что оценка по методу Yadryara даёт около 34 цепочек с лишними простыми в том же интервале).
И оцените требуемый интервал для центральных 15 чисел из этого паттерна (15-228), реально же цепочка нашлась в 2.08e18.
Будет понятно насколько Ваша оценка завышена.

[vicvolf]

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

Оцените своим методом ожидаемый интервал для центральных 17 чисел из этого паттерна (17-240) и сравниtе с реально найденным решением практически на 1e21 И оцените требуемый интервал для центральных 15 чисел из этого паттерна (15-228), реально же цепочка нашлась в 2.08e18.

При $17$ получилось $10^{31}$. При 15 получилось $10^{26}$. Оценки ориентировочные. Возможно завышены.

[Yadryara]

vicvolf в сообщении #1632305 писал(а):

Я прикинул, чтобы встретить данный кортеж надо проверить не меньше, чем до $10^{36}$.

Эдак никакого ха-ха не хватит. Предположим, что Dmitriy40 сможет ускорить свою прогу ещё раз эдак в пять, до 5е24/год. Это что же 200 миллиардов лет считать ??

Так что прикидку в студию, плиз.

Я ещё в июне делал завышенные прикидки:

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

Ведь для 17-к простое перемножение предсказывает одну на 6e23, а для 19-к — одну на 2.7e26.

Тот метод был совсем прост. Но обратите внимание: 26-й порядок, а не 36-й.

Затем я довольно долго возился с кэфами, но потом отказался и придумал другой метод, который подробно описал здесь, в теме, на 3-4 страницах. Кстати, не сразу заметил похвалу от гуру:

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

Yadryara
Слушайте, а ведь отличный метод оценки!
Пусть и грязных цепочек. Зато хоть какое-то нормальное (математическое) обоснование где они должны быть хотя бы в среднем, а не гадание по трендам.

Затем я хотел ещё точнее оценить, по валидс18, привёл свою прогу, но почему-то оба собеседника промолчали в ответ.

Может сейчас повеселей будет, если MGM и vicvolf подключатся поконкретней.

[Dmitriy40]

vicvolf в сообщении #1632315 писал(а):

При $17$ получилось $10^{31}$. При 15 получилось $10^{26}$. Оценки ориентировочные. Возможно завышены.

Ну то есть грубо по 5 порядков на каждые две единицы длины. А практика показывает что реально всего лишь около двух порядков на две единицы длины (ну и коэффициент запаса скажем от 1/3 до 3). Так что нет, 5 порядков это очень сильно завышено.

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

но почему-то оба собеседника промолчали в ответ.

Я недавно внимательно на неё посмотрел (убрав всё лишнее) и не увидел ничего нового по сравнению с уже выполненной оценкой (только лишь точность чуть повыше, не 19 цифр, а 50, что в общем не суть).

-- 09.03.2024, 21:09 --

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

Предположим, что Dmitriy40 сможет ускорить свою прогу ещё раз эдак в пять, до 5е24/год.

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

[Yadryara]

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

Суммарно пока получается 12 раз по отношению к работающей версии.

Я ориентировался вот на это, совсем недавнее:

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

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

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

ускорению за счёт КТО (отказа от линейного перебора и переходу к перебору лишь допустимых вариантов, что даёт ускорение 3.34 раза)

Я это понимаю так.

Счёт пойдёт с какого-то места из диапазона 0-78е23 и в каком-то порядке, но точно не по возрастанию и не по убыванию. При этом будут заново(!) пересчитываться числа из диапазона 0-10е23, на который ушёл почти год счёта.

Хотя, может это уже и не такая проблема как раньше, ежели 10-12-кратное ускорение будет достигнуто. Месяц пересчёта.

[vicvolf]

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

Так что прикидку в студию, плиз.

Я ничего нового не изобретал. Есть первая гипотеза Харди-Литтлвуда о количестве k-кортежей на интервале $x$: $\pi(x,k) \sim \frac{Cx}{\ln^k(x)}$, где постоянная $C$ зависит от структуры кортежа. В данном случае я хотел просто грубо оценить порядок величины $x$ до первого кортежа, поэтому предположил значение $\pi(x,k)=1$, а значение $C$ вообще не учитывал. Наверно так делать нельзя, так как значение $C$ при большом значение $k$ велико и формула асимптотическая. До этого я проверял гипотезу при небольших значениях $k$ и большом количестве кортежей и она давала хорошие результаты.

[Dmitriy40]

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

Я это понимаю так.
Счёт пойдёт с какого-то места из диапазона 0-78е23 и в каком-то порядке, но точно не по возрастанию и не по убыванию. При этом будут заново(!) пересчитываться числа из диапазона 0-10е23, на который ушёл почти год счёта.
Хотя, может это уже и не такая проблема как раньше, ежели 10-12-кратное ускорение будет достигнуто. Месяц пересчёта.

В принципе правильно, только в деталях несколько по другому: я пока отказался от учёта 67 и по КТО перебираю лишь 61#, что в 1.4 раза медленнее (ускорение не 4.66, а 3.34 раза), зато можно идти с шагом 61#=1.173e23 и не пересчитывать то что уже насчитано (10 полных интервалов 61#). Зато пока скорость внутреннего цикла более чем вдвое выше и в итоге скорость уже не х12, а лишь х7 (вчера была ошибка в программе) от работающей программы. Если решение встретится до 6e24 (а должно бы и до 2-3e24), то так оно будет найдено раньше (за 190 дней) чем перебором по 67#. Если не встретится до 67#, будут насчитаны 17 лишних интервалов 61# (ещё за 80 дней), потом переделаю перебор на 67# и пропущу первую итерацию чтобы не повторять. Или брошу эту затею.

[vicvolf]

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

. Это что же 200 миллиардов лет считать ??

У Вас все как-то наоборот. Для чего нужна предварительная оценка трудоемкости счета задачи? Для того, чтобы не тратить время на пока неразрешимые.

-- 10.03.2024, 15:30 --

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

Или брошу эту затею.

Вот именно!

[Dmitriy40]

vicvolf в сообщении #1632390 писал(а):

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

Только оценка должна быть более-менее точной, а не завышенной на 10 порядков.