2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4, 5  След.
 
 
Сообщение03.05.2008, 16:35 
Легко доказать, что нет элементарной формулы (плюс, умножить, возвести в степень) от одной переменной, которая принимала бы только простые значения.
Насчет рекуррентностей - подумать надо.

 
 
 
 
Сообщение03.05.2008, 18:22 
Вопрос интенресный. Мне попадал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)} собственно и есть последовательность простых чисел

 
 
 
 
Сообщение03.05.2008, 18:41 
Аватара пользователя
Попов А.В. писал(а):
А вообще, можно вспомнить, что в доказательстве теоремы Евклида о бесконечности множества простых чисел дается рекуррентная формула построения простого числа:

\[
\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)$-е простое число через все предыдущие, можно найти здесь

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


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

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


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

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

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

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

 
 
 
 
Сообщение03.05.2008, 19:17 
Профессор Снэйп писал(а):
Для полиномиальности достаточно $p_{n+1} \leqslant 2p_n$. Этот факт вроде бы доказан.

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

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

 
 
 
 
Сообщение03.05.2008, 19:42 
Аватара пользователя
MaximKat писал(а):
Профессор Снэйп писал(а):
Для полиномиальности достаточно $p_{n+1} \leqslant 2p_n$. Этот факт вроде бы доказан.

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


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

 
 
 
 
Сообщение03.05.2008, 19:43 
p-h-o-e-n-i-x писал(а):
Необходимость перебора предыдущих простых для получения следующего вероятно вызвана определением простого числа. Так?
Она вызвана тем, что никто (из здесь присутствующих, по крайней мере) не знает, как это сделать по другому ;)

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

 
 
 
 
Сообщение03.05.2008, 23:34 
Аватара пользователя
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{Мне лень переписывать этот многочлен.}$$

:D

 
 
 
 
Сообщение04.05.2008, 00:04 
RIP писал(а):
Zagier писал(а):
И, наконец, логики определяют в последнее время простые числа как положительные значения многочлена…


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

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

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

 
 
 
 
Сообщение04.05.2008, 06:22 
Аватара пользователя
Простое число --- это число лопастей у плохого вентилятора.

 
 
 
 
Сообщение04.05.2008, 06:41 
Аватара пользователя
Уважаемый Rip, а вы не могли бы эту книгу залить на рапиду или депозит ?

 
 
 
 
Сообщение04.05.2008, 11:51 
Аватара пользователя
p-h-o-e-n-i-x писал(а):
Уважаемый Rip, а вы не могли бы эту книгу залить на рапиду или депозит ?

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

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


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