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

[Someone]

Идущий писал(а):

Someone, а как Вы считаете формула простых чисел существует?

Посмотрите вот это: http://primes.utm.edu/notes/faq/p_n.html.

[Cube]

Someone писал(а):

Идущий писал(а):

Someone, а как Вы считаете формула простых чисел существует?

Посмотрите вот это: http://primes.utm.edu/notes/faq/p_n.html.

Там пишется:

Цитата:

1.
This type formula would only be of value if the necessary constant could be found without first finding the primes--this may be possible, but it seems unlikely.
2.
...still using the floor function [x]...

[Anar Yusifov]

to Cube

Я читал о такой теореме: существует такое a что $p_n=$потолок$(a^n)$. Докозательство невидел, но вполне в неё верю.

[Someone]

Anar Yusifov писал(а):

to Cube

Я читал о такой теореме: существует такое a что $p_n=$потолок$(a^n)$. Докозательство невидел, но вполне в неё верю.

Не слышал о такой теореме. Если под $p_n$ понимается $n$-ное простое число, то, разумеется, это не так, поскольку показательная функция растёт достаточно регулярно, чего не скажешь о $p_n$. Но даже если под $p_n$ понимать просто $\lceil a^n\rceil$, то всё равно вряд ли все такие числа будут простыми.
Зато есть похожая теорема вот здесь: http://primes.utm.edu/notes/proofs/A3n.html. Там доказывается, что существует такое число $A>1$, что число $\left[A^{3^n}\right]$ простое для всех натуральных $n$.

[Anar Yusifov]

Цитата:

Но даже если под понимать просто , то всё равно вряд ли все такие числа будут простыми.

Именно так и надо понимать. Постораюсь в близжайшее время запостить автора теоремы и источник.

[Someone]

Anar Yusifov писал(а):

Цитата:

Но даже если под понимать просто , то всё равно вряд ли все такие числа будут простыми.

Именно так и надо понимать. Постораюсь в близжайшее время запостить автора теоремы и источник.

С удовольствием посмотрю.

[незваный гость]

Если не ошибаюсь, существует полином о многих (20-50) переменных, все значения которого -- простые. Но он выдает, естественно, простые не по порядку. (Почему-то всплывает по ассоциации Матиясевич, но не больно надежно).

[tolstopuz]

незванный гость писал(а):

Если не ошибаюсь, существует полином о многих (20-50) переменных, все значения которого -- простые. Но он выдает, естественно, простые не по порядку. (Почему-то всплывает по ассоциации Матиясевич, но не больно надежно).

Не все, а только положительные (при неотрицательных значениях переменных). Матиясевич доказал существование такого полинома в 1971 году в связи с решением десятой проблемы Гильберта, а конкретную реализацию нашли через 5 лет.
http://primes.utm.edu/glossary/page.php ... asevicPoly
Насколько я понимаю, такая возможность вытекает из тьюринговой полноты диофантовых уравнений - любой алгоритм можно превратить в систему диофантовых уравнений и далее в многочлен.
http://lib.mexmat.ru/books/4427
http://logic.pdmi.ras.ru/~yumat/H10Pbook/commch_5.htm

Если же не ограничиваться многочленами, а допустить, скажем, модуль, то задача решается еще проще:
http://mathworld.wolfram.com/PrimeFormulas.html (ближе к концу)
Тогда даже не нужно фильтровать отрицательные значения - модуль позволяет в неподходящих случаях просто выдавать 2.

[ArtemKim]

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

[MaximKat]

О, конечно.
Пусть $p$ - данное простое число. Для каждого $q=p,p+1,p+2,\ldots$ перебираем все целые числа от 2 до $[\sqrt{q}]$ и проверяем делится ли $q$ на них. Если не делится - значит мы нашли следующее за $p$ простое число. Поскольку простых чисел бесконечно много, то алгоритм завершится.
Или вопрос не в этом был?

[Echo-Off]

Хочется, видимо, иметь полиномиальный алгоритм

[MaximKat]

полиномиальный по чем?

[ArtemKim]

Я думаю для начала все равно будет ли такой алгоритм полиномиальным или нет. Мне интересно, можно ли доказать его существование. Вопрос вероятно не понят. Я хочу узнать, что надо сделать с числом 13 чтобы получилось 17 ? И чтобы тоже самое можно было бы сделать с числом 17, чтобы получить 19.

[Henrylee]

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

Я хочу узнать, что надо сделать с числом 13 чтобы получилось 17 ? И чтобы тоже самое можно было бы сделать с числом 17, чтобы получить 19.

Рекуррентную формулу что ли??

[Руст]

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