Еще о простых числах

[Lesobrod]

Предположим, известна функция "количество простых чисел до данного" $\pi(x)$.
Либо в простеньком виде $\pi(x) \sim \frac{x}{\ln(x)}$,
либо посложнее $\pi(x) \sim Li(x)+\mathrm{O}(\sqrt{x} \ln(x))$, либо "as is" $\pi(x)$.
Как отсюда получить функцию "ближайшее (допустим, снизу) простое к данному числу" $p(x)$?
Я в курсе, что асимптотика для "n-го простого числа" есть $p_n \sim n \ln(n)$.
Но, во-первых, это не совсем то, а во-вторых не очень понятно, почему

$$\pi(x) \sim \frac{x}{\ln(x)} \Rightarrow p_n \sim n \ln(n)$$

И нельзя ли написать какое-то функциональное уравнение для $\pi(x)$ и $p(x)$?

[Sonic86]

об этом хорошо в Кнуте "Конкретная математика" написано в главе про асимптотику. Хотя книга совсем не про то. причем заметьте, что такой асимптотикой характеризуются не только простые числа но и вообще-то многие последовательности.

-- Пт окт 29, 2010 17:55:29 --

А функциональное уравнение банально:

$$\pi(p(x)) = [x]$$

[Lesobrod]

Ну примерно такое уравнение и я получил, только оно не работает!
Еще раз: $\pi(x)$ - количество простых (строго)до $x$, $p(x)$ - ближайшее (снизу) простое к $x$.
$x=10, p(10)=7, \pi(7)=3 ???$

[ИСН]

У вас (у обоих) взаимное непонимание из-за перепутывания $p_n$ и $p(x)$.

[caxap]

Lesobrod в сообщении #367909 писал(а):

$\pi(x)$ - количество простых (строго)до $x$

Не строго. $\pi(7)=4$.

In[1]:= Table[Prime[k],{k,1,10}]
Out[1]= {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}

In[2]:= Table[PrimePi[k],{k,1,10}]
Out[2]= {0, 1, 2, 2, 3, 3, 4, 4, 4, 4}

In[3]:= Table[PrimePi[Prime[k]],{k,1,10}]
Out[3]= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

[Lesobrod]

Всё, понятно. Сорри, Sonic86, спасибо, Сахар!
Строго - я имел в виду "не включая", но это слишком путано.
И в Вольфраме $PrimePi[7]==4$.
Тогда уравнение правильное. А вот как из него по $\pi(x)$найти $p(x)$ ?
В Кнуте я нашел только утверждение, что асимптотики следуют одна из другой; вывода там нет.
Я не думаю, что он сложный; где-то мне попадалось такое рассуждение.
Если до $x$ имеется $\pi(x)$ простых, то "среднее расстояние" между ними $\frac{x}{\pi(x)}$ , а значит, "$x$"-вым простым будет $\frac{x \cdot x}{\pi(x)}=xln(x)$. Но чего-то как-то это наивно.

[venco]

Lesobrod в сообщении #368037 писал(а):

Если до $x$ имеется $\pi(x)$ простых, то "среднее расстояние" между ними $\frac{x}{\pi(x)}$ , а значит, "$x$"-вым простым будет $\frac{x \cdot x}{\pi(x)}=xln(x)$. Но чего-то как-то это наивно.

Это приблизительные формулы.
Точной же, и в то же время простой и пригодной для применения формулы не известно.

[Lesobrod]

Это я знаю!! Кстати, с помощью дзета-функции Римана можно получить сколь угодно точное приближение к $\pi(x)$ (если гипотеза Римана верна).
Меня интересует более "простой" вопрос - если $\pi(x)$ известна, или выписана какая-то асимптотика, как выразить через неё $p(x)$?

[venco]

Lesobrod в сообщении #368058 писал(а):

Меня интересует более "простой" вопрос - если $\pi(x)$ известна, или выписана какая-то асимптотика, как выразить через неё $p(x)$?

$p(x)=\pi^{-1}\left(\pi\left(x\right)\right)$
$p(x)=p_{\pi(x)}$

[Lesobrod]

Первое уравнение крутое. Однако обратная функция $\pi^{-1}(x)$ многозначна!
Если брать наименьшее из её значений, то всё получается.

[Droog_Andrey]

Lesobrod в сообщении #368058 писал(а):

с помощью дзета-функции Римана можно получить сколь угодно точное приближение к $\pi(x)$ (если гипотеза Римана верна).

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

[Sonic86]

Lesobrod в сообщении #368058 писал(а):

Это я знаю!! Кстати, с помощью дзета-функции Римана можно получить сколь угодно точное приближение к $\pi(x)$ (если гипотеза Римана верна).

Угу:
topic21405.html
Кстати, правильно ли, что для вычисления $\pi(x)$ через дзета-функцию, нужно знать большое число нулей дзета-функции? Какова зависимость между нужным числом нулей и величиной $x$? Может быть окажется проще считать решетом? Или протабулировать функцию?

Lesobrod в сообщении #368058 писал(а):

Меня интересует более "простой" вопрос - если $\pi(x)$ известна, или выписана какая-то асимптотика, как выразить через неё $p(x)$?

В Конкретной математике в главе асимптотика есть такой вывод. Смысл такой: берется нужное число членов разложения интегрального логарифма в ряд и обращается с отбрасываем в нужный момент дохлых слагаемых. Можно методом неопределенных коэффициентов искать. К сожалению, у меня не получилось просто записать асимптотическое разложение для функции, обратной к интегральному логарифму. В общем виде - сами знаете как это страшно. Там еще 1 "нерегулярное слагаемое" имеется + члены ряда имеют вид $\frac{P_k(\ln \ln x)}{\ln ^k x}$, в числителе - многочлен степени $k$ c $k+1$ неизвестными коэффициентам. Ессно, считать простые числа по их номеру через формулу - нечто страшно чудовищное и бессмысленное. Может я и ошибаюсь. Однако там же в любом случае погрешность $O(\sqrt{n})$.
А чисто теоретически - вполне себе вещь! Например, Вы можете вычислить возможную асимптотику для всяких $\sum\limits_{p \leqslant x} \frac{1}{p}$ и $\sum\limits_{p \leqslant x} \frac{\ln p}{p}$ и более сложных рядов с любой точностью в возможных рамках (там есть ограничения такие же как ограничение невозможности вычислить $\operatorname{Li}(x)$ через асимптотический ряд с точностью $O(x^{1- \epsilon})$ для $\epsilon > 0$) лишь используя $\pi (x) \approx \operatorname{Li}(x)$, причем не пользуясь каждый раз отдельным хитрым приемом как авторы, а тупо почти алгоритмически (но придется сильно потрудится ), результаты, конечно, теряют при этом часть своей красоты... Число членов асимптотики при всех таких преобразованиях - инвариант (и даже - инвариант метода).

[Droog_Andrey]

Sonic86 в сообщении #472921 писал(а):

Кстати, правильно ли, что для вычисления $\pi(x)$ через дзета-функцию, нужно знать большое число нулей дзета-функции? Какова зависимость между нужным числом нулей и величиной $x$? Может быть окажется проще считать решетом? Или протабулировать функцию?

Всё зависит от величины $x$ и от количества вычисляемых значений $\pi(x)$.

Для начала посмотрите вот тут: http://www.dtc.umn.edu/~odlyzko/doc/arc ... i.of.x.pdf