Количество простых чисел.

[Батороев]

Родилась идея написания формулы для прикидочного расчета количества простых чисел до квадрата простого числа $p_{i}^2$ :

$$ \pi(p_{i}^2)=\dfrac {\varphi (p_{i}\#)\cdot p_{i}^2}{p_{i}\#}$$

где
$p_{i}\#$ - примориал простых чисел до $p_{i}$
$\varphi (p_{i}\#)$ - функция Эйлера для этого примориала.

Хотелось бы узнать мнение форумчан, какова будет относительная точность такой формулы?

[Dmitriy40]

Для грубой оценки $\pi(p^2)$ неплохая:

? foreach([2..10],t, p=precprime(10^t); x=1.*p^2; forprime(pp=2,p, x*=(pp-1)/pp); print("p=",p,": ",n=primepi(p^2)," / ",x," = ",n/x))
p=97: 1163 / 1132.0653860786651881300046347355859243 = 1.0273258190752466140428699770320864898
p=997: 78060 / 80480.200613172895604738290038426856521 = 0.96992799974734704768138426812930635076
p=9973: 5732087 / 6055635.8965984903405735455914190111937 = 0.94657061584891011910727913263877700132
p=99991: 454974398 / 487441427.20700706214546896828998827624 = 0.93339296293907547770806806914161557779
p=999983: 37606680932 / 40636828484.246983330559418300325717440 = 0.92543346355334715104093348941833090813
p=9999991: 3204936166853 / 3483371182885.1123909931092443060680698 = 0.92006737111446797554580242116386472751
p=99999989: 279238281319527 / 304797149050483.51407132798970735311724 = 0.91614466273526986969104480752753412920
p=999999937: 24739951247708012 / 27093151456133562.717416504482260808139 = 0.91314409428391489051640458779143640003
p=9999999967: 2220819588229234473 / 2438386097710728320.2300988913975605425 = 0.91077438077351428043523319007874597927
\\Точка наилучшей точности:
p=241: 5882 / 5851.9342794141379507849092249144787297 = 1.0051377406427182323852702830178476517
p=251: 6320 / 6322.3580178240243179654801718872529791 = 0.99962703506866005025980360775545822632

Но и 3%-9% не сказать чтобы прям великая точность.
И судя по тенденции точность так и будет падать, хоть и весьма медленно.

-- 23.03.2025, 23:06 --

Да, если это кому-то не очевидно:

$$\dfrac {\varphi (p\#)}{p\#}=\prod_{i\in P}^p\dfrac{i-1}{i}$$

Т.е. произведение дробей по всем простым по $p$ включительно. Что считается гораздо проще праймориалов и функции Эйлера, хоть записывается и сложнее.

[vicvolf]

Батороев в сообщении #1679687 писал(а):

Хотелось бы узнать мнение форумчан, какова будет относительная точность такой формулы?

$\dfrac {\varphi (p_{i}\#)}{p_{i}\#}$ - это плотность взаимно простых чисел, а не простых чисел. На интервале взаимно простых чисел после 1 сразу идет простое число $p_{i+1}$. Число 1 не является простым, поэтому его в формуле надо вычесть, а простые числа с $p_1$ до $p_i$ надо добавить. Таким образом, более точная формула будет иметь вид:

$$ \pi(p_{i}^2)=i-1+\dfrac {\varphi (p_{i}\#)\cdot p_{i}^2}{p_{i}\#}.$$

Однако, все равно на конечном интервале формула не будет точной, так как плотность взаимно простых чисел не равна плотности простых чисел. Данная формула становится точной только на бесконечном интервале, т.е. асимптотически при $p_i \to \infty$.

[Dmitriy40]

vicvolf
Я бы не сказал что добавление $i=\pi(p_i)$ как-то кардинально улучшает ситуацию, скорее наоборот лишь ухудшает:

? foreach([9],t, p=precprime(10^t); x=1.*p^2; forprime(pp=2,p, x*=(pp-1)/pp); print("p=",p,": ",n=primepi(p^2)," / ",x," = ",n/x))
p=999999937: 24739951247708012 / 27093151456133562.717416504482260808139 = 0.91314409428391489051640458779143640003
? foreach([9],t, p=precprime(10^t); x=1.*p^2; forprime(pp=2,p, x*=(pp-1)/pp); x+=primepi(p); print("p=",p,": ",n=primepi(p^2)," / ",x," = ",n/x))
p=999999937: 24739951247708012 / 27093151506981096.717416504482260808139 = 0.91314409257015614343832278970425036512

Но разница всего лишь в 9-м знаке, а погрешность уже в первом.

Так что я сильно сомневаюсь что формула станет точной на любом интервале, хоть бы и бесконечном - погрешность похоже растёт с ростом $p_i$, а не падает, а Вы её и ещё увеличили.

[vicvolf]

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

Таким образом, более точная формула будет иметь вид:

$$ \pi(p_{i}^2)=i-1+\dfrac {\varphi (p_{i}\#)\cdot p_{i}^2}{p_{i}\#}.$$

Для $p_i=7,p_i\#=210,\varphi[(210)=48$ получим по формуле:
$ \pi(7^2)=4-1+\dfrac {48 \cdot 7^2}{210}=14,2$. Фактически $ \pi(7^2)=15$. Если без прибавки $4-1=3$, то по формуле получим $11,2$, т.е. значительно хуже.
Для $p_i=11,p_i\#=2310,\varphi[(2310)=480$ получим по формуле:
$ \pi(11^2)=5-1+\dfrac {480 \cdot 11^2}{2310}=29,14$. Фактически $ \pi(11^2)=30$. Если без прибавки $5-1=4$, то по формуле получим $25,14$, т.е. значительно хуже.

[Dmitriy40]

Ну то есть данная коррекция формулы имеет смысл лишь на самом начальном участке (который никому не интересен так как там известны точные значения $\pi(p)$), не более того. А для чисел $p>250$ она лишь ухудшает и так невеликую точность.

[Sonic86]

Эх, горе мне, горе.
Задача для лялек самостоятельных упражнений читателю.
Докажите, что формула

Батороев в сообщении #1679687 писал(а):

Родилась идея написания формулы для прикидочного расчета количества простых чисел до квадрата простого числа $p_{i}^2$ :

$$ \pi(p_{i}^2)=\dfrac {\varphi (p_{i}\#)\cdot p_{i}^2}{p_{i}\#}$$

неверна асимптотически используя 3-ю теорему Мертенса https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 1%81%D0%B0:

$$ \prod\limits _{p\leqslant n}\left(1-{\frac {1}{p}}\right)\sim\frac{e^{-\gamma }}{\ln n} $$

[vicvolf]

Спасибо Sonic86. Вы меня немного опередили. Хотел сегодня об этом написать.
На основании 3-ей теоремы Мертенса:

$$\frac {\varphi(p_i\#)}{p_i\#}=\prod_{p \leq p_i}(1-1/p) \sim \frac {e^{-C}}{\ln(p_i)},$$

где $C=0,577215...$.
Поэтому:

$$\frac {\varphi(p_i\#)\cdot p_i^2}{p_i\#} \sim \frac {e^{-C}\cdot p_i^2}{\ln(p_i)}.$$

А на основании PNT:

$$\pi(p_i^2) \sim \frac{p_i^2}{\ln(p_i)}.$$

Таким образом, асимптотика по указанной формуле имеет методическую ошибку - $e^{-C}$.

[Dmitriy40]

По моему двойку в знаменателе забыли, с которой относительная погрешность станет $e^C/2 \approx 0.89$ в пределе, при экспериментальном значении $0.91$, очень похоже.

[vicvolf]

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

По моему двойку в знаменателе забыли.

Да

[Батороев]

Sonic86
vicvolf
Извините! Я не задавлся целью составить точную формулу расчета количества простых чисел.
Во-первых, поместил тему в разделе "Помогите решить", а во-вторых, зная, что она имеет погрешность, так и назвал ее "прикидочной".
Я просто спросил то, что спросил, и Dmitriy40 мне подробно ответил. За что ему большое спасибо! Его данные я долго "переваривал" и поэтому задержался со своим ответом.
Dmitriy40
Еще раз спасибо!

[Dmitriy40]

Вообще-то гораздо более простая $\pi(p^2)=\frac{p^2}{2\ln(p)}$ даёт существенно лучшую точность, например для $p=9999999967$ погрешность -2.2% против +9.8% Вашей.
Вот если Вашу скорректировать на указанную Sonic86 и vicvolf константу $e^C$, то станет интереснее, хотя бы асимптотически точной. Интереснее в математическом смысле, не практически.

Кстати, $\pi(10^k)$ известны до $10^{29}$ в A006880, добавку (или уменьшение) для $p^2\approx10^k$ легко найти по обычной формуле, $\pi(p^2)=\pi(10^k)+\frac{p^2}{2\ln(p)}-\frac{10^k}{k\ln(10)}$ (на самом деле на такую погрешность можно и просто плюнуть и оставить лишь первый член), а $\prod\limits_{p \in P} \frac{p-1}{p}$ до $10^{14\ldots15}$ я кажется публиковал где-то в теме про кортежи из простых чисел - т.е. формулы можно сверить и до $p\approx10^{14.5}$.