2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5  След.
 
 Формула для n-ного простого числа
Сообщение21.01.2006, 18:04 
Заслуженный участник
Аватара пользователя


23/07/05
18040
Москва
Идущий писал(а):


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

 Профиль  
                  
 
 Re: Формула для n-ного простого числа.
Сообщение21.01.2006, 22:06 
Аватара пользователя


20/01/06
64
оттуда
Someone писал(а):


Там пишется:
Цитата:
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]...

 Профиль  
                  
 
 
Сообщение23.01.2006, 12:19 


12/05/05
60
Baku
to Cube

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

 Профиль  
                  
 
 
Сообщение23.01.2006, 12:46 
Заслуженный участник
Аватара пользователя


23/07/05
18040
Москва
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$.

 Профиль  
                  
 
 
Сообщение23.01.2006, 12:52 


12/05/05
60
Baku
Цитата:
Но даже если под понимать просто , то всё равно вряд ли все такие числа будут простыми.

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

 Профиль  
                  
 
 
Сообщение23.01.2006, 12:53 
Заслуженный участник
Аватара пользователя


23/07/05
18040
Москва
Anar Yusifov писал(а):
Цитата:
Но даже если под понимать просто , то всё равно вряд ли все такие числа будут простыми.

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


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

 Профиль  
                  
 
 
Сообщение23.01.2006, 20:32 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение23.01.2006, 20:47 
Заслуженный участник


31/12/05
1539
незванный гость писал(а):
Если не ошибаюсь, существует полином о многих (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.

 Профиль  
                  
 
 Простые числа
Сообщение02.05.2008, 21:07 
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение02.05.2008, 21:53 


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

 Профиль  
                  
 
 
Сообщение02.05.2008, 22:22 
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение02.05.2008, 22:43 


11/05/06
363
Киев/Севастополь
полиномиальный по чем?

 Профиль  
                  
 
 
Сообщение02.05.2008, 22:47 
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение02.05.2008, 22:53 
Заслуженный участник
Аватара пользователя


30/10/07
1221
Самара/Москва
p-h-o-e-n-i-x писал(а):
Я хочу узнать, что надо сделать с числом 13 чтобы получилось 17 ? И чтобы тоже самое можно было бы сделать с числом 17, чтобы получить 19.

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

 Профиль  
                  
 
 
Сообщение03.05.2008, 16:06 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 63 ]  На страницу 1, 2, 3, 4, 5  След.

Модераторы: Модераторы Математики, Супермодераторы



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

Сейчас этот форум просматривают: Утундрий


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group