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

Someone · 23/07/05 17973 Москва

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

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

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

Cube · 20/01/06 64 оттуда

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 · 12/05/05 60 Baku

to Cube

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

Someone · 23/07/05 17973 Москва

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 · 12/05/05 60 Baku

Цитата:

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

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

Someone · 23/07/05 17973 Москва

Anar Yusifov писал(а):

Цитата:

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

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

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

незваный гость · 17/10/05 3709

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

tolstopuz · 31/12/05 1480

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

Если не ошибаюсь, существует полином о многих (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 · 27/05/07 115

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

MaximKat · 11/05/06 363 Киев/Севастополь

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

Echo-Off · 23/09/07 364

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

MaximKat · 11/05/06 363 Киев/Севастополь

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

ArtemKim · 27/05/07 115

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

Henrylee · 30/10/07 1221 Самара/Москва

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

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

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

Руст · 09/02/06 4382 Москва

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

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

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

Кто сейчас на конференции