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

[Yadryara]

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

можно выбрать любую точку

Да нельзя выбрать любую точку-то ! Вы же сами писали:

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

главное не заходить в область огромных ошибок HL-1 около 2-10-100,

[Dmitriy40]

Yadryara
Ну так посчитайте точное количество кортежей до 10-100-1e3-1e6-1e9 (PARI справляется на ура) или докуда угодно и подставьте его в формулу, оставив интеграл лишь дальше этой точки. Вот он и не будет заходить в область больших ошибок HL-1.

[vicvolf]

Это прогнозные средние значения по "грязному" кортежу [0, 6, 24, 36, 66, 84, 90, 114, 120, 126, 150, 156, 174, 204, 216, 234, 240]:

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

C =204267977.27052456200777283266142295380; for(po=20,25, print("1e",po,": ", C*intnum(t=10^15, 10^po, 1/log(t)^17)))
1e20: 1.7557245002275315546308709801402952266
1e21: 7.4351443404451914718020312280718548578
1e22: 32.821919356801697595127500054036228216
1e23: 150.52077685440651819771879578445903007
1e24: 714.70091617197361582471365013812979683
1e25: 3502.9848354834459300047762495294712228

А какие фактические данные по количеству "грязных" кортежей [0, 6, 24, 36, 66, 84, 90, 114, 120, 126, 150, 156, 174, 204, 216, 234, 240] по интервалам?

[Dmitriy40]

Надоело париться с вложенными циклами, сделал рекурсивно (показываю только добавления, все вложенные циклы грохнуть):

{Iterate(n,m,k)=my(a,t,p,mm=m);
   for(a=1,k,
      forprime(p=3,#v+n, if(m[p]==2^(-dd[a]%p), next(2)); );
      t=CC[#v+n]; forprime(p=3,#m, t*=hammingweight(mm[p]=bitnegimply(m[p],2^(-dd[a]%p))); );
      vC[n] += t; nn[n]++;
      if(n<maxn, Iterate(n+1,mm,a-1));
   );
}
vC=vector(10); maxn=4;\\Номер максимальной считаемой Cx
Iterate(1,m0,#dd);
for(k=1,#vC, if(vC[k]>0, print("C",k,"=",vC[k])); );

В интегралах тоже разумеется заменить все Cx на vC[x].
Замедление где-то пара процентов.

-- 28.07.2024, 16:32 --

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

А какие фактические данные по количеству "грязных" кортежей [0, 6, 24, 36, 66, 84, 90, 114, 120, 126, 150, 156, 174, 204, 216, 234, 240] по интервалам?

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

-- 28.07.2024, 16:45 --

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

да и я лишь потому что так моя программа устроена, что ищет грязные

Причём грязные именно 19-252, а более короткие очень многие пропускает.
И до 1.6e24 нашла 15 грязных 17-240 (12 из которых до 1e24 и 2 до 1e23).

[Yadryara]

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

Ну так посчитайте точное количество кортежей до 10-100-1e3-1e6-1e9 (PARI справляется на ура) или докуда угодно и подставьте его в формулу, оставив интеграл лишь дальше этой точки.

Какой именно точки ? Ведь вопрос именно в этом. Чем дальше, тем меньше ошибка? То есть кортеж 7-108-1 обсчитан до 1е15. Значит стартуем с 1е15 и прибавляем 1.3 млн чистых кортежей ?

Это логично, если уж за миллион количество перевалило, потому что очень вероятно, что погрешность меньше 1%.

А в других случаях как быть, вот вопрос.

Ваша рекомендация была ровно об обратном:

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

и в то же время начинать задолго до первого реального грязного кортежа.

Так задолго до первого начинать или наоборот, после последнего?

Или, если кортежей нет ни одного, то лучше задолго до первого? А насколько задолго?

Если известно что есть один кортеж до 1.3е24, почему нужно стартовать не с 1.3е24 прибавив 1-ку, а с 1е15, ничего не прибавляя?

По моей рекомендации было: стартовать с 1е8, ничего не прибавляя. Точнее ли это?

А как быть, если кортежи есть, но их явно больше 1-го и явно меньше миллиона, десятки, сотни, тысячи?

Вроде это всё пока не выяснено.

[vicvolf]

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

до 1.6e24 нашла 15 грязных 17-240 (12 из которых до 1e24 и 2 до 1e23).

Да, похоже программа очень много пропустила. Вот среднее значение:

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

C =204267977.27052456200777283266142295380; for(po=20,25, print("1e",po,": ", C*intnum(t=10^15, 10^po, 1/log(t)^17)))
1e20: 1.7557245002275315546308709801402952266
1e21: 7.4351443404451914718020312280718548578
1e22: 32.821919356801697595127500054036228216
1e23: 150.52077685440651819771879578445903007
1e24: 714.70091617197361582471365013812979683
1e25: 3502.9848354834459300047762495294712228

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

подсчитал средне квадратичные отклонения для данного кортежа [0, 6, 24, 36, 66, 84, 90, 114, 120, 126, 150, 156, 174, 204, 216, 234, 240] на том же диапазоне.
C =204267977.27052456200777283266142295380;
for(po=20,25, print("1e",po,": ",sqrt(C*intnum(t=10^15, 10^po, 1/log(t)^17)-C^2*intnum(t=10^15, 10^po, 1/log(t)^34))))

1e20: 1.3250375467236887150272578898712175202
1e21: 2.7267461085413125554224436286046511819
1e22: 5.7290417485650859581276282740212296666
1e23: 12.268690918529430383401940989756943337
1e24: 26.733890778784400798366380695907488922
1e25: 59.186018919027202382429157581189982916

Похоже, что должны быть "грязные" кортежи до $10^{22}$ и далее.
Так и есть

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

Ради интереса посмотрел на оценку кортежей 17-240, их известно 5шт до 1e22, причём первый почти точно на 1e21. Оценка до шестикратного загрязнения:

v=[0, 6, 24, 36, 66, 84, 90, 114, 120, 126, 150, 156, 174, 204, 216, 234, 240]
C =204267977.27052456200777283266142295380
C1=28369943870.637190788534643770043972079
C2=1882883655575.2751806520561345784915500
C3=79503105963393.861809247903002671637974
C4=2398827502988278.8370655540475223328881
C5=55074965123455739.447710661923258904122
C6=1000416540944375388.0187642856124195935
[1, 104, 2952, 41852, 379420, 2471696, 12318076]
10^20: 0.364217
10^21: 1.209901
10^22: 4.437549
10^23: 17.921522
10^24: 78.976390
10^25: 375.024404

Считаю совпадение отличным.
И кстати это довод что меньшего кортежа нет.

Ведь чистых кортежи входят в грязные.
-- 28.07.2024, 17:49 --

Мои мысли. Если можно опровергните на цифрах. Я предполагаю, что известно точное фактическое число найденных кортежей и точка, где найден последний кортеж.

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

Или, если кортежей нет ни одного, то лучше задолго до первого? А насколько задолго?

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

Цитата:

Если известно что есть один кортеж в точке 1.3е24

Надо стартовать с 1.3е24 прибавив один.

Цитата:

А как быть, если кортежи есть, но их явно больше 1-го и явно меньше миллиона

Надо стартовать с точки последнего найденного кортежа и прибавить найденное число кортежей.

[Yadryara]

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

Если можно опровергните на цифрах.

Ну вот цифры по 19-252:

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

24   1.9317722199750494549    4.34
25   8.6942641180382782259    4.50

Это был старт с 1е9 без прибавки.

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

Надо стартовать с 1.3е24 прибавив один.

Довольно очевидно, что раз 1-й грязный кортеж припозднился, то прогноз при таком счёте будет ещё хуже: не 8.7 всех кортежей до 1е25, а никак не больше чем 7.5 всех кортежей до 1е25.

[Dmitriy40]

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

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

Вот с этим и проблема: кортеж найден на 1.302063e24, если взять стартовую точку 1.3e24 и посчитать прогноз до 1.303e24, то получим 0.0034188573730684845385440903949572166889 вместо почти 1. Проблема.

[vicvolf]

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

Довольно очевидно, что раз 1-й грязный кортеж припозднился, то прогноз при таком счёте будет ещё хуже: не 8.7 всех кортежей до 1е25, а никак не больше чем 7.5 всех кортежей до 1е25.

Надо еще учесть среднее квадратичное отклонение.

[vicvolf]

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

Вот с этим и проблема: кортеж найден на 1.302063e24, если взять стартовую точку 1.3e24 и посчитать прогноз до 1.303e24, то получим 0.0034188573730684845385440903949572166889 вместо почти 1. Проблема.

Ну так считать не надо. Ведь известно, что найден кортеж в точке 1.302063e24, значит его нужно добавить и потом стартовать с этой точки. Поскольку формула Харди-Литтлвуда асимптотическая, то на небольшом интервале после найденного кортежа она будет давать больше ошибку, но по мере увеличения интервала ошибка будет уменьшаться и так до следующего найденного кортежа. Если же кортежи встречаются часто, то можно использовать обычную (не модифицированную) формулу.

[Yadryara]

Забавно. Нашу задачу по 19-252 на другом форуме обсуждают, при этом не понимая, что мы её уже давно решили.

https://mathhelpplanet.com/viewtopic.php?p=483408#p483408 писал(а):

Для этого нужно рассмотреть все паттерны, содержащие помимо указанных чисел и другие возможные простые и применить формулу включений-исключений. При этом уже с 2 добавленными частота по Х-Л будет сильно меньше, а случаем с 3 добавленными, наверное, и вовсе можно пренебречь.

И это неверно. Нельзя пренебрегать ни тремя, ни четырьмя. Досчитали до 10 добавленных, и только 11-ю пренебрегли.

А итоги вот:

$\tikz[scale=.1]{ \draw[step=20cm] (0,320) grid +(60,30); \draw (0,350) -- (60,350); \draw (0,330) -- (60,330); \node at (10,345){\text{Диапазон}}; \node at (30,345){\text{Чистых}}; \node at (50,345){\text{Всех}}; \node at (10,335){$\leqslant 10^{25}$}; \node at (10,325){$\leqslant 10^{26}$}; \node at (30,335)[red]{\text{0.6}}; \node at (30,325){\text{3.2}}; \node at (50,335){\text{8.7}}; \node at (50,325){\text{40.4}}; }$

[vicvolf]

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

А итоги вот:
$\tikz[scale=.1]{ \draw[step=20cm] (0,320) grid +(60,30); \draw (0,350) -- (60,350); \draw (0,330) -- (60,330); \node at (10,345){\text{Диапазон}}; \node at (30,345){\text{Чистых}}; \node at (50,345){\text{Всех}}; \node at (10,335){$\leqslant 10^{25}$}; \node at (10,325){$\leqslant 10^{26}$}; \node at (30,335)[red]{\text{0.6}}; \node at (30,325){\text{3.2}}; \node at (50,335){\text{8.7}}; \node at (50,325){\text{40.4}}; }$

А что такое 0,6 кортежа? Может не быть данного кортежа на интервале, т.е. быть 0 кортежей или один, два, и.т.д. На самом деле количество кортежей на определенном интервале это дискретная случайная величина, которая имеет свое распределение. В работе, на которую я давал ссылку, я показал, что закон распределения данной случайной величины стремится к нормальному при возрастании интервала.

[Yadryara]

vicvolf, согласен с Дмитрием: опять банальности вещаете.

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

Чтобы всем-всем-всем было понятно?

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

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

0.6 чистых кортежей на 1е25 — это и есть матожидание:

Да

Тогда не спросили, согласились, а теперь-то зачем надо спрашивать?

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

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

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

Хорошо, средняя ожидаемая частотность. Не хочется говорить матожидание, потому что не уверен, что в данном случае это уместно.

Уместно. Или кто-то не согласен?

Похоже только Вы)

Кстати, могу пояснить осторожность своей формулировки.

Являются ли простые числа случайной величиной?

С одной стороны, нет конечно: они жёстко детерминированы. Можно сколько угодно раз искать их в первой сотне и результат каждый раз будет один и тот же — 25 чисел от 2 до 97.

Кстати, возможно именно поэтому Дмитрий может предполагать, что 1-й чистый кортеж встречается раньше чем в среднем.

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

[vicvolf]

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

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

Нет это не банальности. Среднее значение, дисперсия (среднее квадратичное отклонение), функция распределения могут описывать не только случайную величину, а любую величину, если для ее описания удобно использовать аппарат теории вероятностей или математической статистики. Кстати ведь прогноз тоже использует среднее (тренд) и отклонение от среднего.
Очевидно эти сомнения не дают Вам сделать еще один шаг и использовать для оценки не только среднее, но и отклонение от среднего. Ведь гораздо понятнее сделать прогноз, что с такой-то вероятностью на таком интервале количество кортежей определенного вида колеблется от такой-то величины до такой-то.
При небольшом количестве кортежей на интервале нормальное распределение наверно не пройдет, но использовать неравенство Чебышева для получения такой вероятности вполне возможно https://ru.wikipedia.org/wiki/%D0%9D%D0 ... 0%B2%D0%B0

[Dmitriy40]

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

Являются ли простые числа случайной величиной?

Не стоит его поднимать ещё и здесь, где-то в соседних математических темах по vicvolf уже не однажды проходились катком что он неправомерно применяет теоремы о случайных числах к простым числам (которые очевидно не случайны, хотя в пределах ведут себя похоже). Его не убедили. Потому я с осторожностью отношусь к его формулам и особенно названиям/терминам - например совершенно не уверен что формула 4.10 даёт именно СКО, а не что-то совсем другое, ведь квадратов разностей отклонений в ней нет, а смысла вычитать из вероятности примерно её же квадрат я не понимаю, даже размерности результата.
Но в чисто практическом плане да, простые числа (и соответственно кортежи из них) очень похожи на случайные с известным распределением.

-- 05.08.2024, 11:53 --

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

Кстати, возможно именно поэтому Дмитрий может предполагать, что 1-й чистый кортеж встречается раньше чем в среднем.

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