О количестве простых чисел в интервале

[12d3]

tapos в сообщении #289889 писал(а):

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

А $\mathbb{R}$ неупорядоченное, чтоли?

[Батороев]

А вот интересно стало, можно ли рассмотреть вопрос следующим образом


Существует доказанная П. Л. Чебышевым оценка количества простых чисел до числа $x_1$:

$$ 0,89\cdot \dfrac{x_1}{ \ln x_1} < \pi (x_1) < 1,11\cdot\dfrac{x_1}{ \ln x_1} $$

Допустим, что число простых чисел увеличилось на единицу:

$$0,89 \cdot\dfrac{x_1}{ \ln x_1}+1<\pi (x_1)+1< 1,11 \cdot\dfrac{x_1}{ \ln x_1}+1$$

Тогда существует $x_2$, для которого выполняется неравенство Чебышева:

$$ 0,89\cdot\dfrac{x_2}{ \ln x_2} < \pi (x_2)=\pi (x_1)+1 < 1,11\cdot \dfrac{x_2}{ \ln x_2} $$

Отсюда, по-видимому, можно записать:

$$ 0,89\cdot\dfrac{x_2}{ \ln x_2} \leq1,11\cdot \dfrac{x_1}{ \ln x_1}+1 $$

После преобразований получаем:

$$ 0,89 \cdot x_2 \cdot \ln x_1 \leq 1,11 \cdot x_1 \cdot \ln x_2+ \ln x_1 \cdot \ln x_2 $$

Для достаточно больших чисел в виду малой погрешности будем считать, что $ \ln x_1 = \ln x_2$.

Тогда получаем:

$$ x_2 \leq \dfrac {1,11 \cdot x_1 + \ln x_1}{0,89}$$

[venco]

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

Существует доказанная П. Л. Чебышевым оценка количества простых чисел до числа $x_1$:

$$ 0,89\cdot \dfrac{x_1}{ \ln x_1} < \pi (x_1) < 1,11\cdot\dfrac{x_1}{ \ln x_1} $$

Это неравенство не Чебышева, и выглядит оно немного по другому:

$$ 0,89\cdot Li(x_1) < \pi (x_1) < 1,11\cdot Li(x_1)$$

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

Допустим, что число простых чисел увеличилось на единицу:

$$0,89 \cdot\dfrac{x_1}{ \ln x_1}+1<\pi (x_1)+1< 1,11 \cdot\dfrac{x_1}{ \ln x_1}+1$$

Это не число простых чисел увеличилось на единицу, а вы прибавили единицу к верному неравенству, при этом оно осталось верным (если использовать $Li$ - интегральный логарифм).

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

Тогда существует $x_2$, для которого выполняется неравенство Чебышева:

$$ 0,89\cdot\dfrac{x_2}{ \ln x_2} < \pi (x_2) < 1,11\cdot \dfrac{x_2}{ \ln x_2} $$

Это неравенство (с $Li$) выполняется для всех больших $x_2$.

Дальше непонятно.

[Батороев]

venco в сообщении #290164 писал(а):

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

Существует доказанная П. Л. Чебышевым оценка количества простых чисел до числа $x_1$:

$$ 0,89\cdot \dfrac{x_1}{ \ln x_1} < \pi (x_1) < 1,11\cdot\dfrac{x_1}{ \ln x_1} $$

Это неравенство не Чебышева, и выглядит оно немного по другому:

$$ 0,89\cdot Li(x_1) < \pi (x_1) < 1,11\cdot Li(x_1)$$

Упоминаемое неравенство я взял из статьи.

venco в сообщении #290164 писал(а):

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

Допустим, что число простых чисел увеличилось на единицу:

$$0,89 \cdot\dfrac{x_1}{ \ln x_1}+1<\pi (x_1)+1< 1,11 \cdot\dfrac{x_1}{ \ln x_1}+1$$

Это не число простых чисел увеличилось на единицу, а вы прибавили единицу к верному неравенству, при этом оно осталось верным (если использовать $Li$ - интегральный логарифм).

Я именно и добавил ко всем частям 1. При этом, вроде бы, в средней части получается $\pi (x_2)=\pi (x_1)+1$. А почему нет?

venco в сообщении #290164 писал(а):

Дальше непонятно.

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

Допустим, что число простых чисел увеличилось на единицу:

$$0,89 \cdot\dfrac{x_1}{ \ln x_1}+1<\pi (x_1)+1< 1,11 \cdot\dfrac{x_1}{ \ln x_1}+1$$

Тогда существует $x_2$, для которого выполняется неравенство Чебышева:

$$ 0,89\cdot\dfrac{x_2}{ \ln x_2} < \pi (x_2)=\pi (x_1)+1 < 1,11\cdot \dfrac{x_2}{ \ln x_2} $$

Отсюда, по-видимому, можно записать:

$$ 0,89\cdot\dfrac{x_2}{ \ln x_2} \leq1,11\cdot \dfrac{x_1}{ \ln x_1}+1 $$

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

[venco]

А, понятно! У вас $x_1$ и $x_2$ - два последовательных простых числа.
Тогда правильно. Для больших чисел отношение двух последовательных простых не превышает $\frac{1.11}{0.89}=1.25$
Вроде бы, доказано гораздо более сильное утверждение - в любом интервале $[k^2,(k+1)^2]$ есть хотя бы одно простое число.

[maxal]

venco в сообщении #290216 писал(а):

Вроде бы, доказано гораздо более сильное утверждение - в любом интервале $[k^2,(k+1)^2]$ есть хотя бы одно простое число.

Не доказано. Это известная гипотеза Лежандра:
http://mathworld.wolfram.com/LegendresConjecture.html

[Батороев]

Рискну ( ) сделать предположение с некоторым не совсем строгим обоснованием.

С некоторой, не очень большой погрешностью количество простых чисел можно подсчитать:

$$ \pi (n)= n\cdot \dfrac {\varphi (x)}{x}$$

где $x$ - произведение всех простых до $\sqrt n$.

Тогда запишем:

$$ n_2\cdot \dfrac {\varphi (x_2)}{x_2}-n_1\cdot \dfrac {\varphi (x_1)}{x_1}=1$$

Откуда, пренебрегая погрешностью:

$$ \dfrac {p_{n_2}}{p_{n_2}-1}}=\dfrac {\sqrt n_1}{\sqrt n_1-1}}$$

где $p_{n_2}$ - наибольшее простое число, непревосходящее $\sqrt {n_2}$

и учитывая то, что

$$ \dfrac {x}{\varphi (x)}<\ln n$$

получил оценку:

$$ n_2 < \dfrac {n_1^{\frac{3}{2}}}{n_1^{\frac{1}{2}}}+\ln n_1$$

которую проверить на больших числах, к сожалению, не могу.

[Батороев]

В последнем выражении очепятался!
Должно быть:

$$ n_2 < \dfrac {n_1^{\frac{3}{2}}}{n_1^{\frac{1}{2}}-1}+\ln n_1$$

[venco]

Скорее, $(\ln n_1)^2$.

Почитайте здесь:
http://en.wikipedia.org/wiki/Prime_gap
http://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture

[tapos]

12d3 в сообщении #290066 писал(а):

А неупорядоченное, чтоли?

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

[tapos]

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

Существует доказанная П. Л. Чебышевым оценка количества простых чисел до числа :

Это неравенство не Чебышева, и выглядит оно немного по другому:

Разрешите Вам напомнить, что все неравенства и оценки относительно простых чисел являются асимптотическими. Это означает, что они верны только в бесконечности. А до этой самой бесконечности могут быть провалы (отсутствие простых чисел) или интервалы с аномально большим количеством простых чисел. Вы же, уважаемые, обращаетесь с асимптотическими выражениями как с точными оценками. Будьте корректны.

[terminator-II]

tapos
а на вопрос отвечать будем? post290776.html#p290776

[bot]

Вряд ли - есть люди, которым смену смысла при перестановке кванторов не объяснишь.
Пробовал привязывать к $\forall$ человека, а к $\exists$ - отца.
Некоторым помогает, а некоторым нет.

[tapos]

hjunec в сообщении #238466 писал(а):

О количестве простых чисел в интервале

Посмотрите внимательней на алгоритм по имени решето Эратосфена. Это единственный алгоритм, позволяющий в принципе найти все простые числа. Этот алгоритм показывает механизм возникновения простых чисел. Обобщенно этот механизм можно выразить следующим положением: каждое следующее простое число (за исключением 2) является функцией всех предыдущих простых чисел (у 2 нет предыдущего простого числа). Следовательно, для вычисления простого числа методом решета Эратосфена, необходимо знать все предыдущие простые числа. Если попробывать выразить решето Эратосфена уравнением, то количество переменных этого уравнения (или показатель степени полинома) неограниченно растет. Поэтому не найдено более простых алгоритмов вычисления простых чисел. Более того, если хорошенько присмотреться к решету Эратосфена, то этот алгоритм есть ничто иное, как перебор подмножеств множества чисел натурального ряда. А еще Кантор доказал, что множество подмножеств натурального ряда несчетно. Поэтому даже в принципе невозможно создать какие-либо конечные алгоритмы, позволяющие вычислять все простые числа по их номеру.

[BapuK]

tapos в сообщении #292229 писал(а):

hjunec в сообщении #238466 писал(а):

О количестве простых чисел в интервале

Посмотрите внимательней на алгоритм по имени решето Эратосфена. Это единственный алгоритм, позволяющий в принципе найти все простые числа. Этот алгоритм показывает механизм возникновения простых чисел. Обобщенно этот механизм можно выразить следующим положением: каждое следующее простое число (за исключением 2) является функцией всех предыдущих простых чисел (у 2 нет предыдущего простого числа). Следовательно, для вычисления простого числа методом решета Эратосфена, необходимо знать все предыдущие простые числа. Если попробывать выразить решето Эратосфена уравнением, то количество переменных этого уравнения (или показатель степени полинома) неограниченно растет. Поэтому не найдено более простых алгоритмов вычисления простых чисел. Более того, если хорошенько присмотреться к решету Эратосфена, то этот алгоритм есть ничто иное, как перебор подмножеств множества чисел натурального ряда. А еще Кантор доказал, что множество подмножеств натурального ряда несчетно. Поэтому даже в принципе невозможно создать какие-либо конечные алгоритмы, позволяющие вычислять все простые числа по их номеру.

всегда думал что некоторая совокупность элементов множества является его подмножеством, а не множеством подмножеств и кстати доказано что множество всех подмножеств несчетно