p_n<2^{n+1}

[rightways]

Докажите, что $p_n<2^{n+1}$, где $p_n$ это $n-$ ное простое число.

Задача предлагалась 7 классникам. Без Бертрана.

[mathematician123]

То есть, нужно доказать, что $\pi(2^{n + 1}) \ge n$. В книге Айерлэнд, Роузен "Классическое введение в современную теорию чисел" есть доказательство оценки $\pi(x) \ge \frac{\ln x}{2\ln 2} $, основанное на том, что любое число единственным образом представляется в виде $ab^2$, где $a$ свободно от квадратов. Подставив $x = 2^{n + 1}$, получим $\pi(2^{n + 1}) \ge \frac{n + 1}{2} $. Немного меньше, чем нужно. Можно попробовать модифицировать это доказательство.

[vicvolf]

У Прахара в "Распределении простых чисел" на стр 19 в элементарных оценках доказано немного слабее $p_n <e^{n+1}$, но знаний 7 класса для доказательства этого явно недостаточно.

[Руст]

Это на точный порядок числа 2 по модулю простого числа.
Если x,y взаимно простые определим число

$$\Phi_n(x,y)=\prod_{d|n}(x^{n/d}-y^{n/d})^{\mu(d)}.$$

Для любого простого делителя этого числа $p|\Phi_n(x,y)$
$p\not | \Phi_m(x,y), m\not =n$
Взяв $x=2,y=1$ и $p|\Phi_m(2,1), m=2,3,...,n$ получим (n-1) различных нечетных делителей меньше $2^n$, добавив четное простое число 2 получим чуть лучше оценку
$p_n\le 2^n$ (равенство только при n=1$.

[Null]

Руст, почему $\Phi_m(2,1)\neq 1$?

[iifat]

Постулат Бертрана, не? Не уверен, что для седьмого класса, но, вроде, достаточно элементарное.

[Руст]

Руст, почему $\Phi_m(2,1)\neq 1$?
$\Phi_m(x,1)$ круговой многочлен степени $\phi(m)$ от $x$.

[dubov]

Оценим число составных от 2 до $2^n$.
Это произведение некоторого числа простых, возможно одинаковых, но главное, что их степени дают в сумме не более $n$, и среди них есть две единицы. Каждая степень - 0 или 1.
Следовательно, составных будет не более (так как $3^n$ соответствует нашей конструкции, но не условию)
$\binom{n}{2}+\binom{n}{3}+...+\binom{n}{n}=2^n-\binom{n}{0}-\binom{n}{1}=2^n-n-1$
Следовательно, простых будет не менее
$2^n-1-(2^n-n-1)=n$

[Руст]

возможно одинаковых, но главное, что их степени дают в сумме не более $n$

Вы неправильно считаете. Если есть и одинаковые, то их гораздо больше.
Например при $n=3$ количество с суммой степеней 2 равно 6 ($p_1^2, p_1p_2, p_1p_3, p_2^2, p_2p_3, p_3^2$). Точнее их не $C_n^k$, a $C_{n+k-1}^k$.

С оценкой количества произведений можно получить гораздо более точную оценку (как Чебышев), но более длинным путем.

[vicvolf]

rightways в сообщении #1650238 писал(а):

Докажите, что $p_n<2^{n+1}$, где $p_n$ это $n-$ ное простое число.

Докажем по индукции. При $n=1$ получаем $p_1=2<2^2=4$ - выполняется.
Предположим, что выполняется для $n=k$, т.е. $p_k<2^{k+1}$.
Докажем, что выполняется $p_{k+1}<2^{k+2}$.
По постулату Бертрана при $n \geq 2$ найдется простое число в интервале $(n,2n)$.
Возьмем $n=2^{k+1}$, тогда $2n=2^{k+2}$. Следовательно, по постулату Бертрана на интервале $(2^{k+1},2^{k+2})$ найдется простое число.
Учитывая , что $p_k<2^{k+1}$, поэтому $p_{k+1}<2^{k+2}$ ч.т.д.

Возможно постулат Бертрана дали школьникам на дополнительном занятии, а потом решили закрепить материал решением данной задачи.

[nnosipov]

А теперь попробуйте как ТС хотел:

rightways в сообщении #1650238 писал(а):

Задача предлагалась 7 классникам. Без Бертрана.

Это гораздо интереснее.

-- Вс сен 15, 2024 14:20:16 --

vicvolf в сообщении #1654725 писал(а):

Возможно постулат Бертрана дали школьникам на дополнительном занятии

Постулат Бертрана в седьмом классе? Вы его доказательство сами-то читали?

[vicvolf]

nnosipov в сообщении #1654727 писал(а):

А теперь попробуйте как ТС хотел:

rightways в сообщении #1650238 писал(а):

Задача предлагалась 7 классникам. Без Бертрана.

Это гораздо интереснее.

Конечно интересно, если кто-то может доказать постулат Бертрана в седьмом классе)

Цитата:

Постулат Бертрана в седьмом классе? Вы его доказательство сами-то читали?

Просто дали без доказательства.