2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: Простое число, док-во
Сообщение19.02.2013, 23:12 
ИСН в сообщении #685893 писал(а):
Переход в таком изложении может прокатить перед слушателем, который уже и так согласен. Вы в одной строчке говорите "нужно проверить, что $p_{n+1}\leqslant 2^{n+1}$", а в следующей немедленно утверждаете этот факт как факт. Почему факт? Потому что нам нужно? Ну ОК.


Спасибо, да, там это было лишнее.

Нужно проверить, что $p_{n+1}\leqslant 2^{n+1}$.

Используя постулат Бертрана, взяв $k=2^n$ , имеем $2^{n}\leqslant p_{n+1} \leqslant2\cdot 2^{n}$. чтд.

 
 
 
 Re: Простое число, док-во
Сообщение19.02.2013, 23:17 
Аватара пользователя
Как в точности формулируется постулат Бертрана, который Вы используете? А то у Вас получилось, что $2^n\leqslant p_{n+1}$, т.е., например, $1024=2^{10}\leqslant p_{11}=31$. От этого как-то тревожно.

 
 
 
 Re: Простое число, док-во
Сообщение19.02.2013, 23:21 
ИСН в сообщении #685910 писал(а):
Как в точности формулируется постулат Бертрана, который Вы используете? А то у Вас получилось, что $2^n\leqslant p_{n+1}$, т.е., например, $1024=2^{10}\leqslant p_{11}=31$. От этого как-то тревожно.

Для любого натурального $n \geqslant 2$ найдётся простое число $p$ в интервале $n < p < 2n$

(Оффтоп)

Ух, :facepalm: что ж я делал. Жуткая ошибка. Мозг вечером уже не тот, что утром

 
 
 
 Re: Простое число, док-во
Сообщение19.02.2013, 23:25 
Аватара пользователя
Так. С учётом этого огласите ещё раз переход индукции.

 
 
 
 Re: Простое число, док-во
Сообщение19.02.2013, 23:29 
Не в ту сторону знаки рисуются...

Нужно доказать $p_k\leqslant 2^k$(*)

1) База ...

2) Пусть для $k=n$ выполняется, проверим для $k=n+1$.

$p_{n+1}\underbrace{\leqslant}_{?}  2p_n\leqslant 2^{n+1}$

Теперь нужно доказать, что $p_{n+1}\leqslant 2p_n$. Реально это сделать или я опять не туда?

 
 
 
 Re: Простое число, док-во
Сообщение19.02.2013, 23:35 
Аватара пользователя
Ещё как реально! Надо применить... Вы не поверите... постулат Бертрана!

 
 
 
 Re: Простое число, док-во
Сообщение19.02.2013, 23:55 
ИСН в сообщении #685927 писал(а):
Ещё как реально! Надо применить... Вы не поверите... постулат Бертрана!


$p_{n}\leqslant p_{n+1}\leqslant 2p_n$

Спасибо, понятно!!! Что ж я так тупил.

 
 
 
 Re: Простое число, док-во
Сообщение20.02.2013, 00:02 
Аватара пользователя
Изображение Изображение

-- Ср, 2013-02-20, 01:03 --

оба неравенства можно сделать строгими

 
 
 
 Re: Простое число, док-во
Сообщение20.02.2013, 01:27 
Аватара пользователя
Да и нижнюю оценку можно доказать через теорему Чебышева:
Взяв $x=p_n$ мы получим, что $$a\dfrac{p_n}{\ln p_n}\leqslant n \leqslant A\dfrac{p_n}{\ln p_n}$$ Рассматривая второе неравенство и оценив его получаем, что при $n>N_1$ будет $n\leqslant A\dfrac{p_n}{\ln p_n}\leqslant \dfrac{p_n}{3}$, а отсюда сразу получаем, что $p_n\geqslant 3n$ начиная с некоторого $n>N_1$

(Оффтоп)

ИСН
то, что теорема Чебышева -- сильное утверждение я с Вами полностью согласен, но я просто хотел, чтобы ТС увидел, что такие оценки получить легко из данного неравенства. Да и здесь нужно немного знания матана, а теорема Чебышева доказывается весьма просто. Да и постулат Бертрана на мой взгляд тоже сильное утверждение.

 
 
 
 Re: Простое число, док-во
Сообщение20.02.2013, 06:46 

(Оффтоп)

ИСН в сообщении #685858 писал(а):
Whitaker, имейте совесть. Вы опираетесь на неадекватно сильное утверждение - фактически, что $p_n<C\cdot n\cdot\ln n$. Этого не нужно. Постулат Бертрана, как и было сказано - в самый раз.
Не надо, в самый раз, доказательство постулата Бертрана фактически задает верхнюю оценку $\pi (x)\leqslant A\frac{x}{\ln x}$. Вот $\pi(x)\sim \frac{x}{\ln x}$ сильнее.
И вообще, ТС должен понимать, что если он полез в АТЧ, то там надо быть во всеоружии.


Ward в сообщении #685877 писал(а):
как получить оценку $p_n\geqslant 3n$?
Ее можно получить через конечное число шагов решета Эратосфена + численную базу для шага индукции (для самых малых $n$ утверждение может быть просто неверно) + индукцией по $n$.

 
 
 
 Re: Простое число, док-во
Сообщение20.02.2013, 11:16 
Аватара пользователя
Вообще, постулат Бертрана не сильно проще оценок Чебышёва. Хотя вид оценки и намекает на него. Интересно, можно ли эту оценку доказать совсем по-простому? (Из совсем простых оценок я знаю только что-то вроде $p_n<4^n$; можно улучшить в константу раз, но четвёрку я уменьшать не умею.)

 
 
 
 Re: Простое число, док-во
Сообщение20.02.2013, 11:19 
Аватара пользователя
Дух задания кагбе подразумевает, что Бертрана надо воспринимать как данность, без доказательства, и применять по необходимости.
Совсем простых не надо. Это сложно.

 
 
 
 Re: Простое число, док-во
Сообщение20.02.2013, 12:15 
RIP в сообщении #686074 писал(а):
Вообще, постулат Бертрана не сильно проще оценок Чебышёва. Хотя вид оценки и намекает на него. Интересно, можно ли эту оценку доказать совсем по-простому?

Можно воспользоваться известным соотношением
$\sum \limits_{p \leqslant x}\frac{1}{p} \geqslant \ln \ln x + O(1)$
Его, в свою очередь, легко вытащить из оценки
$\prod \limits_{p \leqslant x}(1+\frac{1}{p}+\frac{1}{p^2} \dots ) \geqslant \sum \limits_{k \leqslant x} \frac{1}{k}$

С другой стороны, при $n > 4$ имеем очевидное неравенство $p_n \geqslant 2n+1$, а значит
$2\sum \limits_{k \leqslant n}\frac{1}{p_k} \leqslant \sum \limits_{k \leqslant n} \frac{1}{k} + O(1)$
Отсюда
$\ln n \geqslant 2\ln \ln p_n + O(1)$
$p_n \leqslant e^{C\sqrt n}$

 
 
 
 Re: Простое число, док-во
Сообщение20.02.2013, 12:21 
Аватара пользователя
Можно дать еще такое доказательство:
Рассмотрим такое произведение $$\prod \limits_{p\leqslant x}\left(1-\dfrac{1}{p}\right)^{-1}=\sum\limits^{*} \dfrac{1}{n}$$ причем зведочка в $\sum\limits^{*}$ означает, что суммирование ведется только по тем $n$, простые множители которых не превосходят $x$. В частности, $$\sum\limits^{*} \dfrac{1}{n}>\sum\limits_{n\leqslant x} \dfrac{1}{n}>\int \limits_{1}^{[x]+1}\dfrac{d\xi}{\xi}>\ln x$$ Также понятно, что $$\prod \limits_{p\leqslant x}\left(1-\dfrac{1}{p}\right)^{-1}\leqslant \prod \limits_{k=2}^{\pi(x)+1}\left(1-\dfrac{1}{k}\right)^{-1}=\dfrac{2\cdot 3 \cdots\{\pi(x)+1\} }{1\cdot 2 \cdots\pi(x) }=\pi(x)+1$$ Если воспользоваться еще тем, что $\pi(p_n)=n$, то получаем, что $p_n<e^{n+1}$

(Оффтоп)

Мне кажется, что ТС это уже вообще неинтересно

 
 
 [ Сообщений: 29 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group