2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: О количестве простых чисел в интервале
Сообщение18.02.2010, 13:12 
Заслуженный участник


04/03/09
914
tapos в сообщении #289889 писал(а):
Элементы несчетных бесконечностей невозможно упорядочить по величине как ряд натуральных чисел.

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

 Профиль  
                  
 
 Re: О количестве простых чисел в интервале
Сообщение18.02.2010, 18:36 


23/01/07
3497
Новосибирск
А вот интересно стало, можно ли рассмотреть вопрос следующим образом :?:


Существует доказанная П. Л. Чебышевым оценка количества простых чисел до числа $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}$$

 Профиль  
                  
 
 Re: О количестве простых чисел в интервале
Сообщение18.02.2010, 19:21 
Заслуженный участник


04/05/09
4589
Батороев в сообщении #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$.

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

 Профиль  
                  
 
 Re: О количестве простых чисел в интервале
Сообщение18.02.2010, 21:31 


23/01/07
3497
Новосибирск
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 писал(а):
Дальше непонятно. :roll:

Батороев в сообщении #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  $$

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

 Профиль  
                  
 
 Re: О количестве простых чисел в интервале
Сообщение18.02.2010, 22:02 
Заслуженный участник


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

 Профиль  
                  
 
 Re: О количестве простых чисел в интервале
Сообщение18.02.2010, 22:20 
Модератор
Аватара пользователя


11/01/06
5710
venco в сообщении #290216 писал(а):
Вроде бы, доказано гораздо более сильное утверждение - в любом интервале $[k^2,(k+1)^2]$ есть хотя бы одно простое число.

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

 Профиль  
                  
 
 Re: О количестве простых чисел в интервале
Сообщение19.02.2010, 14:54 


23/01/07
3497
Новосибирск
Рискну ( :roll: ) сделать предположение с некоторым не совсем строгим обоснованием.

С некоторой, не очень большой погрешностью количество простых чисел можно подсчитать:
$$ \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$$
которую проверить на больших числах, к сожалению, не могу.

 Профиль  
                  
 
 Re: О количестве простых чисел в интервале
Сообщение19.02.2010, 20:55 


23/01/07
3497
Новосибирск
В последнем выражении очепятался! :(
Должно быть: $$ n_2 <  \dfrac {n_1^{\frac{3}{2}}}{n_1^{\frac{1}{2}}-1}+\ln n_1$$

 Профиль  
                  
 
 Re: О количестве простых чисел в интервале
Сообщение19.02.2010, 21:08 
Заслуженный участник


04/05/09
4589
Скорее, $(\ln n_1)^2$.

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

 Профиль  
                  
 
 Re: О количестве простых чисел в интервале
Сообщение20.02.2010, 21:21 
Аватара пользователя


14/02/10
63
г. Йошкар-Ола
12d3 в сообщении #290066 писал(а):
А неупорядоченное, чтоли?

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

 Профиль  
                  
 
 Re: О количестве простых чисел в интервале
Сообщение23.02.2010, 18:04 
Аватара пользователя


14/02/10
63
г. Йошкар-Ола
Батороев в сообщении #290204 писал(а):
Существует доказанная П. Л. Чебышевым оценка количества простых чисел до числа :

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


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

 Профиль  
                  
 
 Re: О количестве простых чисел в интервале
Сообщение23.02.2010, 18:17 


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

 Профиль  
                  
 
 Re: О количестве простых чисел в интервале
Сообщение23.02.2010, 19:21 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: О количестве простых чисел в интервале
Сообщение25.02.2010, 19:45 
Аватара пользователя


14/02/10
63
г. Йошкар-Ола
hjunec в сообщении #238466 писал(а):
О количестве простых чисел в интервале

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

 Профиль  
                  
 
 Re: О количестве простых чисел в интервале
Сообщение26.02.2010, 14:11 
Аватара пользователя


06/03/09
240
Владивосток
tapos в сообщении #292229 писал(а):
hjunec в сообщении #238466 писал(а):
О количестве простых чисел в интервале

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 51 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Mikhail_K


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group