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

[DemISdx]

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

ТС считает что мы высказываемся об авторе проекта ODLK2025 (o25) и о самом проекте только в отрицательном ключе.

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

Демис, скажете что я зря им подсказываю? Но мы же ведь многие вещи в теме обсуждаем в открытую. Вполне можно было взять эти наши идеи в открытом доступе и реализовать. Для начала хотя бы и на PARI, раз ничто другое не изучается ТС.

То, что считает или думает ТС не означает истину в последней инстанции.
Равно как и наше мнение.

(Оффтоп)

И она это знает.

Исправит ошибки - хвалить будем.

Мы просто видим со стороны явные косяки о25, как с технической стороны, так и с алгоритмической.
Критика (в здоровой форме) всегда приводит к переосмыслению тех или иных вещей конкретным индивидуумом.
И это нормальная форма в сообществе.
А то, что ТС ничего не предпринимает для исправления ситуации, ей на это наплевать.
Однако все прекрасно знают, что если не видишь проблемы, это не значит, что ее нет.
Вспомните детей.
Когда ругаешь "Кто это сделал???".
Ребенок руками глаза закрывает, мол это не я...

Характерный пример про ускорение.
ТС у себя писала что-то вроде "покажите мне как это сделать" и ссылку сюда на форум давала, на конкретный пост.
А то, что указанные операторы находятся на той-же странице, просто чуть выше, это же читать нужно, вот ведь облом...

Но самое прикольное в ускорении другое, о чем (возможно) даже не думает ТС.
Это "а что делать с проектом, при даже таком ускорении" ?

Запамятвовал, сколько там получалось на ее коде?
Вроде 1.2 минуты.
А что с этим делать?
Ну представьте есть нагенерированных (как сейчас, примерно) 100000 задач.
Это минимум 200000 записей в БД боинка (на самом деле гораздо больше).

100000 * 1.2 = 120000 минут
Делим минуты на число компов
120000 / 160 = 750 задач на комп.
В среднем на компе кранчера у них "проворачивается" 100 задач (цифра примерная, т.к. разное количество ядер у кранчерских машин).
Т.е. примерно за сутки один комп спокойно пережует эти 750 задач.
(предел у одного компа будет примерно 1200 задач на сутки при скорости счета 1.2 минуты)

Это значит, что нужно через сутки генерировать еще 100000 задач.
Про увеличение БД - вообще отдельный разговор, опущу пока этот момент.
(А сейчас в сутки генерируется около 15000 задач для одного приложения.
Если размножить этот подход ускорения на число приложений 3, то нужно по 300000 задач генерить.)

То есть каждые сутки нужно генерить по 100000 задач.
100000 задач, сам генератор задач, выдаст достаточно быстро - минут за 15.
А вот прописка сервером этих 100000 задач в БД займет примерно сутки.
(Тут еще возникает узкое и скользкое горлышко между суточными генерациями по 100000)
По сути возникает проблема масштабирования проекта.
И все из-за чего?
Из-за того что кто-то не умеет считать на пальцах и предвидеть "что" к "чему" приводит.
Хотя причина и так всем понятна - не эффективное приложение, с точки зрения производительности и производимого.

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

По этому пусть уж лучше так считают, все равно это пустое.
И читать больше 2-ух строк ТС не умеет, что было давно доказано и показано.

-- 25.04.2025, 11:20 --

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

Я вот чётко говорю: из найденных мною в последнем поиске 150 штук 15-к ровно одна оказалась и 17-кой. Это редкое явление. Причём отдельные паттерны проверять пока не было необходимости. Смотрим на гэпы с соседними простыми и всё ясно.

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

[Yadryara]

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

Вот как пример, берём все симметричные 5

Я немного по-другому пока делаю:

Кортеж  Загрязнение    Прогноз по HL1 для 0 - 73#
                max                          штук
3-12              2      797252637053699535486773
3-24              4      678341700760505338348249
3-36              8      577838106059426077711564
3-48             10      479042542262487109074398

5-36              6        1099004350734744435301
5-48              8         924978458999158103584
5-60-1           11         771443384190721585905
5-60-2           10         780756553888006558486

Ведь именно для этого интервала прогноз по 21-кам интересен.

Пока скучновато: самые плотные кортежи пока и есть самые вероятные.

[Dmitriy40]

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

Пола скучновато: самые плотные кортежи пока и есть самые вероятные.

А количество разрешённых делителей учитываете? А то ведь количество вариантов в 71# может отличаться на порядок (для более длинных паттернов). А мы считаем именно по вариантам, а не по диапазону.
Ну и константы загрязнений легко посчитать все, до 20, по крайней мере для паттернов диаметром до 120 (на них по 4 минуты).
Я себе поправил программу чтобы все константы были сразу в vC[] (вместе с начальной С для нулевого загрязнения) - после расчётов vC[] делаю vC=concat(C,vC) - тогда интеграл упростился до intnum(t=1e3, 71#, 1/log(t)^#v * sum(i=0,#vC-1, (-1)^i*vC[i+1]/log(t)^i)). Интеграл с квадратами: intnum(t=1e3, 71#, 1/log(t)^(#v*2) * sum(i=0,#vC-1, (-1)^i*vC[i+1]^2/log(t)^(i*2)));.

[Yadryara]

Уже интереснее:

Кортеж  Загрязнение    Прогноз по HL1 для 0 - 73#
                max                          штук
5-36              6        1099004350734744435301
5-48              8         924978458999158103584
5-60-1           11         771443384190721585905
5-60-2           10         780756553888006558486
5-60-3           10        1569696049095661397600
5-60-4           10         792977567580574621362

5-60-3 прям вдвое больше ожидается.

И действительно:

В 0-23#  350 кортежей 5-60-1
В 0-23#  411 кортежей 5-60-2
В 0-23#  745 кортежей 5-60-3
В 0-23#  405 кортежей 5-60-4

-- 26.04.2025, 12:24 --

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

А количество разрешённых делителей учитываете? А то ведь количество вариантов в 71# может отличаться на порядок (для более длинных паттернов). А мы считаем именно по вариантам, а не по диапазону.

Не понял вопроса. Я считаю многократно проверенным способом.

[Dmitriy40]

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

Не понял вопроса. Я считаю многократно проверенным способом.

Вопрос что считать оптимальным: большее количество паттернов или быстрее проверку диапазона или их отношение. Смотрите (для 23#, количество вариантов / оценка по HL1 по всем константам):
5-60-1: 1161216 / 366.86601435203428910342914381779759600 = 3165
5-60-2: 1161216 / 384.53158212920312491550321985233850520 = 3020
5-60-3: 2322432 / 786.18051252775037984679722681234494445 = 2954
5-60-4: 1161216 / 409.45650165566549245130371477246916116 = 2836
Т.е. третий паттерн будет проверяться вдвое дольше (вариантов вдвое больше)! А среднее время между нахождением кортежей у всех 4-х паттернов почти одинаково (разница менее 12%). И если оптимизировать его (ради нахождения первого кортежа), то выгоднее четвёртый паттерн. Хотя больше всего кортежей у третьего (который вдвое дольше остальных).
Потому и вопрос какой критерий оптимальности Вы предпочитаете? Больше кортежей в диапазоне или быстрее их находить? Третий паттерн выгоднее или четвёртый или любой кроме третьего?
Когда ищем много кортежей, выгоднее больше оценка (третий паттерн), но если ищем первый кортеж, то выгоднее меньшее среднее время (четвёртый паттерн). Это разные критерии оптимизации.

[Yadryara]

Вспомнил, да. Видимо, вместо количества формул (добавок, разрешённых остатков) Вы говорите "количество вариантов".

Полагаю, надо на всякий случай считать сразу для 73#, а не для 23#. Ну и, возможно, разбиения ещё нужно учитывать.

[Dmitriy40]

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

Полагаю, надо на всякий случай считать сразу для 73#, а не для 23#.

Можно подумать что-то изменится, ведь и 23 уже больше 1/3 диаметра, а значит дальше все коэффициенты (отношение количества разрешённых остатков к простому) одинаковы. Смотрите:

23#: [0, 6, 30, 54, 60]: 1161216 / 366.86601435203428910342914381779759600 +- 19.155387993779778311569395713992858178 = 3165.2318682365869121303076618184194863
23#: [0, 12, 30, 48, 60]: 1161216 / 384.53158212920312491550321985233850520 +- 19.611065227307827610605631045353087147 = 3019.8195778099440317647032850807865931
23#: [0, 18, 30, 42, 60]: 2322432 / 786.18051252775037984679722681234494445 +- 28.043346583200694739380243721933096182 = 2954.0696608376227651888745006245590163
23#: [0, 24, 30, 36, 60]: 1161216 / 409.45650165566549245130371477246916116 +- 20.236535167178224944685198987119767376 = 2835.9935556146827151467678575940089304
73#: [0, 6, 30, 54, 60]: 53808455816068424307572736 / 771443384190721585905.26027965287403777 +- 27774869039.435373116212374159881522589 = 69750.362656251031539477816434055528783
73#: [0, 12, 30, 48, 60]: 53808455816068424307572736 / 780756553888006558485.62461492414095197 +- 27942020672.125409234320345947701605145 = 68918.353036056393895584759963646029311
73#: [0, 18, 30, 42, 60]: 107616911632136848615145472 / 1569696049095661397599.9012371918765303 +- 39619388049.960179784440812697529971200 = 68559.076576728002920301049118912695870
73#: [0, 24, 30, 36, 60]: 53808455816068424307572736 / 792977567580574621362.97687263211016087 +- 28159856749.549615617567174619123152947 = 67856.214369646636350294320137374909446

Всё то же самое. Только разница скоростей нахождения совсем уменьшилась. Но порядок (кто больше кто меньше) остался.

[Yadryara]

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

И здесь 3-й паттерн (5-60-3) имеет перевес. Ведь если искомый кортеж не находится в конкретном периоде, значит искать надо выше. То есть придётся работать с бо́льшими числами. А с ними работать дольше. И проверять на простоту дольше и возможно многое другое делать дольше.

То есть нужно пробовать поискать Вашей программой кортежи по 3-му паттерну и по 4-му. Допустим, стоит задача найти 500 кортежей. По 3-му паттерну они все найдутся в 0-23#, а для того чтобы найти их по 4-му, придётся подняться во второй интервал 23#.

[Dmitriy40]

Моя программа не заточена на такие маленькие интервалы (или такие огромные количества кортежей в больших интервалах).

500 кортежей говорите, ну давайте прикинем.
По 3-му паттерну достаточно проверить интервал 0-14*19#, это 129024*14=1.806млн вариантов.
По 4-му паттерну достаточно проверить интервал 0-29*19#, это можно сделать проверив 0-23# полностью за 1161216 вариантов, плюс 6 периодов 19# выше 23#, это ещё 64512*6=387072 вариантов, суммарно 1.548млн вариантов.
Числа 29*19#<3e8, укладываются даже в 32 бита, вообще никакой разницы в скорости не будет.
Очевидно 4-й паттерн конкретно для этой задачи выгоднее, на 17%.
Разумеется всё это бессмысленно так как накладные расходы (на запуск exe файла, инициализация таблиц, передача списка кандидатов в PARI, допроверка их) займут гораздо больше времени чем сам счёт двух миллионов вариантов (2млн / 500млн/с = 4мс счёта в один поток, а только запуск exe тратит сотни мс).

Скорость моей программы может незначительно (доли процента) упасть лишь для чисел выше 6e23 (2^15*2^64), ниже скорость от величины чисел не зависит (почти все операции лишь по модулю простого до 2^15).
Скорость допроверки в PARI резко падает после 2^64 (и 2^32 для 32-битных версий), но это по идее занимает меньше процента общего времени (иначе надо увеличивать интервал чтобы моя программа работала дольше или улучшать фильтрацию в моей программе) и потому на итог влияет несущественно.

[Yadryara]

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

500 кортежей говорите, ну давайте прикинем.
По 3-му паттерну достаточно проверить интервал 0-14*19#, это 129024*14=1.806млн вариантов.

Я исходил из того, что заранее неизвестно, где они. Явно проговорю поближе к теме.

Задача найти один кортеж. Допустим по прогнозу получается, что в интервале 0-p# ожидается 0.8 кортежей по первому паттерну и 0.4 по второму. Но по второму и проверить надо в два раза меньше.

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

Необязательно именно такие матожидания. Например 1.2 против 0.6.

[Dmitriy40]

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

Задача найти один кортеж.

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

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

Заметили как подменили задачу? С поиска одного кортежа на уложиться в период. Это разные задачи и решать их можно по разному.
Я вот не вижу зачем укладываться в период.
Тем более что при наличии разбиений периоды могут не соответствовать праймориалам. И вообще то что используем праймориалы - это лишь удобство и выгода (она кстати есть не всегда), но это не обязательно, я вот например в поиске AP22 праймориалы не использовал, там перебор по 2,23-59 или по 2,3,5,29-59 (в зависимости от параметра).

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

Необязательно именно такие матожидания. Например 1.2 против 0.6.

Нет, это важно. Не только соотношение, но и сами величины. Потому что если 0.97, то надо проверять весь период, а если 0.7, то выгоднее проверять несколько меньших периодов.
И вообще, оценивать выгодность по ожидаемой вероятности не совсем правильно, правильнее оценивать необходимый диапазон для вероятности 1.0. И лишь получив его уже решать как его выгоднее перебрать.


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

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

Но всё равно лучших оценок нет и надо ориентироваться на то что есть.

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