Формула для n-ного простого числа

[Sonic86]

Легко доказать, что нет элементарной формулы (плюс, умножить, возвести в степень) от одной переменной, которая принимала бы только простые значения.
Насчет рекуррентностей - подумать надо.

[Попов А.В.]

Вопрос интенресный. Мне попадалfсь как-то статья в которой автор строил рекуррентные формулы поиска простого числа по предыдущему.
А вообще, можно вспомнить, что в доказательстве теоремы Евклида о бесконечности множества простых чисел дается рекуррентная формула построения простого числа:

\[ \left\{ {\begin{array}{*{20}c} {s_0 = 1,p_0 = 1;} \\ {p_i = s_{i - 1} + 1,} \\ {s_i = s_{i - 1} \cdot p_i } \\ \end{array}} \right. \]

Где $ p_{i\left( {i \ge 1} \right)} собственно и есть последовательность простых чисел

[RIP]

Попов А.В. писал(а):

А вообще, можно вспомнить, что в доказательстве теоремы Евклида о бесконечности множества простых чисел дается рекуррентная формула построения простого числа:

\[ \left\{ {\begin{array}{*{20}c} {s_0 = 1,p_0 = 1;} \\ {p_i = s_{i - 1} + 1,} \\ {s_i = s_{i - 1} \cdot p_i } \\ \end{array}} \right. \]

Где $ p_{i\left( {i \ge 1} \right)} собственно и есть последовательность простых чисел

Вы плохо помните доказательство Евклида. $p_i$ не будут все простые (уже $p_5=13\cdot139$). Кроме того, это не есть рекуррентная формула $p_i$ через $p_{i-1}$.
P.S. Рекуррентную формулу, выражающую $(n+1)$-е простое число через все предыдущие, можно найти здесь

[Профессор Снэйп]

Руст писал(а):

Уже есть и полиномиальный ( по количеству цифр или logp) aлгоритм проверки на простоту и учитывая, что следующее простое число не больше (хотя это ещё не доказано, а гипотеза) $p+(lnp)^2,p>2$ получим, что алгоритм получения следующего простого закончится за полиномиальное время.

Для полиномиальности достаточно $p_{n+1} \leqslant 2p_n$. Этот факт вроде бы доказан.

Sonic86 писал(а):

Легко доказать, что нет элементарной формулы (плюс, умножить, возвести в степень) от одной переменной, которая принимала бы только простые значения.

Было бы любопытно посмотреть на доказательство.

[ArtemKim]

Sonic86, Вы можете прямо здесь доказать, что с помощью арифметических действий нельзя из предыдущего простого получить следующее ?

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

Все ли определения простых чисел можно свести к следующему: натуральное, не имеющее делителей кроме единицы и себя ?

[MaximKat]

Профессор Снэйп писал(а):

Для полиномиальности достаточно $p_{n+1} \leqslant 2p_n$. Этот факт вроде бы доказан.

Имеется ввиду полиномиальность по $\ln{p}$ или что то же самое - по количеству десятичных разрядов $p$.

[ArtemKim]

Необходимость перебора предыдущих простых для получения следующего вероятно вызвана определением простого числа. Так?

[Профессор Снэйп]

MaximKat писал(а):

Профессор Снэйп писал(а):

Для полиномиальности достаточно $p_{n+1} \leqslant 2p_n$. Этот факт вроде бы доказан.

Имеется ввиду полиномиальность по $\ln{p}$ или что то же самое - по количеству десятичных разрядов $p$.

А, ну да, понял. Затупил конечно же. Нам ведь надо перебирать все числа от $p_n+1$ до $p_{n+1}$ и длина отрезка $[p_n+1, p_{n+1}]$ должна зависеть полиномиально от длины записи $p_n$.

[MaximKat]

p-h-o-e-n-i-x писал(а):

Необходимость перебора предыдущих простых для получения следующего вероятно вызвана определением простого числа. Так?

Она вызвана тем, что никто (из здесь присутствующих, по крайней мере) не знает, как это сделать по другому

[ArtemKim]

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

[RIP]

p-h-o-e-n-i-x писал(а):

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

Вряд ли. Вот, например, что пишет Zagier в Боро В., Цагир Д., Рольфс Ю. — Живые числа на с.42.

Zagier писал(а):

Правда, другие математики иногда используют и иные определения. Так, для специалиста по теории функций простое число - это целочисленный нуль аналитической функции

$$1-\frac{\sin\frac{\pi\Gamma(s)}s}{\sin\frac\pi s}.$$

Для алгебраиста - это
"характеристика конечного поля",
или
"точка из $\mathop{\mathrm{spec}}\mathbb Z$",
или
"неархимедово нормирование"...
И, наконец, логики определяют в последнее время простые числа как положительные значения многочлена [2]

$$\text{Мне лень переписывать этот многочлен.}$$

[luitzen]

RIP писал(а):

Zagier писал(а):

И, наконец, логики определяют в последнее время простые числа как положительные значения многочлена…

Натуральное $n$ называют простым в том случае, когда логика Лукасевича $\L_{n+1}$ функционально предполна

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

Карпенко А. С. — Логики Лукасевича и простые числа.

[Профессор Снэйп]

Простое число --- это число лопастей у плохого вентилятора.

[ArtemKim]

Уважаемый Rip, а вы не могли бы эту книгу залить на рапиду или депозит ?

[RIP]

p-h-o-e-n-i-x писал(а):

Уважаемый Rip, а вы не могли бы эту книгу залить на рапиду или депозит ?

Если б я ещё знал, что это такое . Книжку можно найти тут (см. Живые числа).