Количество простых чисел на интервале (р-п)

[Апис]

Артамонов говорит, что нет предмета для спора. Все расказывают какие есть резултаты по иследованию простых чисел и если что-то им не соответствует, признаётся неправильным. Что бы лишить вас возможности сравнивать, я открываю новую тему "количество составных чисел на интервале (р-п)" Более того в новой теме попрошу не упоминать всё что касается простых чисел. Категорически будет запрещено упоминать о простых числах в любой ипостаси
Может тогда дискусия войдёт в нужное русло.

[juna]

По какому такому руслу должна потечь эта дискуссия?
Под девизом: Невежество - это порок!
Лично мне не хочется вступать в эти дискуссии

[PAV]

Апис писал(а):

Все расказывают какие есть резултаты по иследованию простых чисел и если что-то им не соответствует, признаётся неправильным.

А каким же еще признавать то, что не соответствует доказанным классическим результатам? Правильным, что ли?

[Апис]

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

[нг]

[mod]Апис
Замечание за грубость, переход на личности.[/mod]
Если две оценки разные, и одна из них признана правильной, то другая, очевидно, ошибочна. Указание на несоответствие — косвенное указание на ошибку. Было бы, конечно, лучше, если бы Вам указали на конкретное место в вычислениях, но это может требовать большего труда: например, в этом сообщениеесть ошибка, но найти ее может только Руст, поскольку выкладки он не поместил. А вот факт наличия ошибки доказуем: вместе с $x$ решением должно быть и $1/x$.

[Руст]

Это я и сам успел заметить и даже исправить до вашего сообщения.

[нг]

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

[e2e4]

Этта. Уважаемый нг, мне кажется, что ваша фраза

Цитата:

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

не совсем верна... Посудите сами, если речь идет о 2-х оценках какой-либо точной величины, то как можно говорить о том, что вторая ошибочна, т.к. первая - верна? Простой пример: Число пи Архимед приближал как $\frac{22}{7}$, древнекитайский астроном Цзу Чун-цжи оценивал пи как $\frac{355}{113}$. Но тут нельзя сказать, что первая оценка ошибочна, т.к. вторая более точна, ведь верно?

Не вернее ли сказать, что метод оценки кол-ва простых на интервале, предложенный Апис'ом, просто дает менее точный результат, чем существующие сегодня методы, но тем не менее он все-таки является методом оценки кол-ва простых на интервале.

[Someone]

PAV писал(а):

Разница между истинным значением и оценкой - абсолютная погрешность. Отношение абсолютной погрешности к истинному значению - относительная погрешность.

К приближённому значению. А истинное может быть и неизвестным.

[juna]

Возьму на себя смелость еще раз объяснить откуда и почему вылезает ошибка, хотя уже RIP сделал это много раз в следующей теме
Надеюсь, что труды не пройдут напрасно. Излагаю как можно более популярно.
Пусть для заданного числа $N$ в промежутке $[1...\sqrt{N}]$ содержатся простые числа $p_1,p_2,...p_s$. Ставится задача найти количество простых чисел в промежутке от $p_s$ до $N$.
Проще рассмотреть на конкретном примере. Пусть $N=20$
В промежутке от 1 до $\sqrt{20}$ из всех простых - это $2,3$
Четных имеем $\lfloor{\frac{20}{2}}\rfloor$
Делящихся на 3 $\lfloor{\frac{20}{3}}\rfloor$
Достаточно брать только эти простые, т.к. известно, что число простое, если оно не делится ни на одно простое из промежутка $[1..\sqrt{N}]$
Вычеркиваем из 20 все четные - это $20-\lfloor{\frac{20}{2}\rfloor$,
из оставшихся вычеркиваем все делящиеся на три $20-\lfloor{\frac{20}{2}\rfloor-\lfloor{\frac{20}{3}\rfloor$
Учитываем, что есть числа, делящиеся на два и на три одновременно (делящиеся на шесть), сейчас мы их вычеркнули два раза. Для исключения двухкратного вычитания суммируем к результату один раз: $20-\lfloor{\frac{20}{2}\rfloor-\lfloor{\frac{20}{3}\rfloor+\lfloor{\frac{20}{2\cdot3}\rfloor$
Итак, у нас остались только простые числа, большие $p_s$ и еще единица, которая тоже не вычеркнута. Для ее исключения берем $20-1-\lfloor{\frac{20}{2}\rfloor-\lfloor{\frac{20}{3}\rfloor+\lfloor{\frac{20}{2\cdot3}\rfloor$
Здесь через $\lfloor .. \rfloor$ - обозначается ближайшее меньшее целое.
Расчеты дают $20-1-\lfloor{\frac{20}{2}\rfloor-\lfloor{\frac{20}{3}\rfloor+\lfloor{\frac{20}{2\cdot3}\rfloor=20-1-10-6+3=6$
Таким образом, простых чисел, больших $2,3$ и меньших $20$ ровно шесть: 5, 7, 11, 13, 17, 19.
Повторяю - это абсолютно верная формула, дающая абсолютно точное значение для любых $N$. Если убрать знак взятия целой части, то имеем $20-20/2-20/3+20/(2\cdot3)=6.666(6)$
Таким образом, теперь мы должны осознавать, что имеем уже лишь приближение.
Во что это выльется, покажем ниже.
Итак, распостраняя эти рассуждения для любого $N$ приходим к известной формуле, указанной RIPом - она верна всегда.
Отбрасываем целую часть, проводим преобразования и получаем, что искомая величина равна $N(\frac{p_1-1}{p_1}\cdot\frac{p_2-1}{p_2}...\frac{p_s-1}{p_s})$.
Еще раз напоминаю - это не точная формула. Мы сознательно исказили результат (завысили его на некоторую величину $\delta$), отбросив значки взятия целой части. Вопрос теперь в том, как эта величина $\delta$ будет себя вести. Априори она может увеличиваться до бесконечности, уменьшаться или стремиться к некоторой константе.
Однако есть классический доказанный результат - формула Мертенса: $\prod\limits_{p<N}(\frac{p-1}{p})\sim\frac{e^{-\gamma}}{ln(N)}$
Слева произведение по всем простым, меньшим $N$, справа $e=2.718..$ - экспонента, $\gamma=0,577..$ - постоянная Эйлера. В нашем случае берутся все простые, меньшие $\sqrt N$. Поэтому формула преобразуется $\prod\limits_{p<\sqrt N}(\frac{p-1}{p})\sim\frac{e^{-\gamma}}{ln(\sqrt N)}$. Или вспоминая свойства логарифмов $\prod\limits_{p<\sqrt N}(\frac{p-1}{p})\sim\frac{2e^{-\gamma}}{ln(N)}$
Таким образом, $\frac{p_1-1}{p_1}\cdot\frac{p_2-1}{p_2}...\frac{p_s-1}{p_s}\sim\frac{2e^{-\gamma}}{ln(N)}$
Здесь значек $\sim$ - асимптотически стремится, т.е. если $N$ стремится к бесконечности, то отношение этих выражений стремится к единице (на самом деле, в формуле Мертенса они отличаются на некоторую постоянную, которой можно пренебречь на бесконечности).
Поэтому, ваша формула, Апис, $N \cdot m_p$ асимптотически ( при очень больших $N$) ничем не отличается от $N\frac{2e^{-\gamma}}{ln(N)}$.
С другой стороны, известен еще один доказанный классический результат, что количество простых чисел меньших $N$ асимптотически стремится к $\frac{N}{ln(N)}$ (в данном случае отличается от истинного значения на некоторую постоянную, которой можно пренебречь в бесконечности), т.е. количество простых чисел в промежутке от $p_s$ до $N$ - это $\frac{N}{ln(N)}-\frac{p_s}{ln(p_s)}=\frac{N}{ln(N)}-\frac{\sqrt N}{ln(\sqrt N)}$
Если $N$ устремлять к бесконечности, то вылезает асимптотическая ошибка $2e^{-\gamma}$, потому что
$\lim\limits_{N \to\infty}\frac{\frac{2\cdot e^{-\gamma}N}{lnN}}{\frac{N}{lnN}-\frac{\sqrt N}{ln(\sqrt N)}}=2e^{-\gamma}$.
На ваш вопрос, по-поводу количества составных чисел, также уже ответили. Почитайте посты Руста, RIPа в этом топике.

[незваный гость]

e2e4 писал(а):

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

Не претендуя на абсоюлютность утверждения, попробую объяснить разницу. Две оценки не обязательно противоречат друг другу. Например, $1.7 \pm 0.3$ и $2.2 \pm 0.3$ друг другу не противоречат (я этим пользовался для улучшения оценки, посмотрите тему домино в физике). С другой стороны, $1.7 \pm 0.1$ и $2.2 \pm 0.1$ друг другу противоречат. Пример с приближенным значением числа $\pi$ и вовсе плох, поскольку точность приближения неизвестна. Можно, например, взять $5$ как приближенное значение, ведь правда? И 55 можно. Поэтому, пока нет некоторой точности оценки, говорить что-либо бессмысленно.

То, что $\pi(n)$ растет как $\frac{n}{\ln n}$ — это хорошо известный факт. Но такое утверждение — это неформальная запись серьезного факта. Формально он записывается иначе: $\pi(n) = \frac{n}{\ln n} (1+{\rm o}(1))$. Предположим, у нас есть $\pi_1(n)$ (с аналогичной точностью). Тогда соотношение $\frac{\pi_1(n)}{\pi(n)}$ просто обязано стремиться к 1. И действительно, $\pi_1(n) = {\rm li}(n)$ (интегральный логарифм) обладает этим свойством.

С другой стороны, если мы получили для $\pi^*(N) = \frac{N}{\ln N} 2 e^{-\gamma}$, у нас получается $\frac{\pi^*(n)}{\pi(n)}} = 2 e^{-\gamma}$. Вот это и есть противоречие.

[e2e4]

Цитата:

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

Можно взять хоть 100. Я же написал:

Цитата:

Не вернее ли сказать, что метод оценки кол-ва простых на интервале, предложенный Апис'ом, просто дает менее точный результат, чем существующие сегодня методы,

"Менее точный" я выделил жирным только что. Естественно, что разные оценки дают разные по точности результаты. Даже если вы докажете, что $\pi = 3 \pm 0.2$, это не делает неверной оценку, что $ 0<\pi<10$, вы так и написали. У Апис'а не уточняется, какая погрешность получается при вычислении кол-ва простых на интервале с помощью приведенной им формулы. Более того, он сам ставит вопрос о нахождении этой погрешности. С другой стороны, его формула достаточно хорошо приближает кол-во простых на интервале, веков 5 назад, я думаю, это было бы лучшим приближением .

RIP, незваный гость, скажите пожалуйста, неужели асимптотический закон распределения простых чисел строго доказан? Насколько я знаю, приближение пи(n) = n/ln(n) впервые предложил Галуа в достаточно малом возрасте, играя с логарифмической линейкой. Далее закон, а точнее сказать, гипотеза, многократно уточнялись. Что означает в записи $\pi(n) = \frac{n}{ln(n} (1+o(1))$ член o(1)?

[RIP]

Асимптотический закон распределения простых был доказан в 1896 г. независимо Адамаром и Валле-Пуссеном.

Добавлено спустя 4 минуты 58 секунд:

Относительно простое док-во можно найти, например, в книжке Галочкин А.И., Нестеренко Ю.В., Шидловский А.Б. — Введение в теорию чисел

[juna]

e2e4 писал(а):

Насколько я знаю, приближение пи(n) = n/ln(n) впервые предложил Галуа в достаточно малом возрасте, играя с логарифмической линейкой. Далее закон, а точнее сказать, гипотеза, многократно уточнялись. Что означает в записи $\pi(n) = \frac{n}{ln(n} (1+o(1))$ член o(1)?

Это был К.Ф.Гаусс, и, по-моему, он был не первый, кто этот факт заметил.

[Апис]

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

Добавлено спустя 1 минуту 39 секунд:

количество простых чисел на интервале (р-п)

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