2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 17:42 


24/11/06
564
г.Донецк,Украина
Можно ли для начала задать вопросы:
1.Существует ли формула, обеспечивающая точное значение искомой величины факториала?
2.Труднозатратный ли по времени расчёт искомой величины факториала по формуле Стирлинга и стандартным способом?
Возможно ли уточнения величин факториалов, расчитанных изначально по формуле Стирлинга?
3.Какие из значений факториалов к настоящему времени известны, и где с ними можно ознакомиться?
Кроме этого хочется узнать, какая закономерность используется в программе, например РНР?

http://ru.wikipedia.org/wiki/%D0%A1%D0% ... 0%B5%D0%BB ,

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

Самостоятельно рассчитать требуемые значения факториалов, у меня возможности нет.
Поиски, как программистов, так и программистов-аналитиков успехом не увенчались и для других работ, которые оговаривались и на вашем форуме, но верно не вызвали достаточного интереса, так как практически оставлены без анализа и требуемой поддержки.
Чтобы не оказаться смешным изначально и задаю свой вопрос:
Существует ли метод определения простых чисел, основанный на использовании значений факториалов?

 Профиль  
                  
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 17:51 
Заслуженный участник


04/05/09
4582
Как вам может помочь "метод определения простых чисел, основанный на использовании значений факториалов", если "Самостоятельно рассчитать требуемые значения факториалов, у меня возможности нет"?

 Профиль  
                  
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 19:41 


24/11/06
564
г.Донецк,Украина
venco в сообщении #227990 писал(а):
Как вам может помочь "метод определения простых чисел, основанный на использовании значений факториалов", если "Самостоятельно рассчитать требуемые значения факториалов, у меня возможности нет"?

Да очень просто! Для определения закономерностей не обязательно использовать значения, которые необходимы для получения новых простых чисел.
Но закономерности остаются и для получения желаемых результатов, о невозможности полученмя которых мной я и упомянул. :roll:

 Профиль  
                  
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 20:38 
Заслуженный участник


04/05/09
4582
Ну, например, есть такая теорема: $(p-1)!\ =\ -1$ modulo $p$ iff $p$ - простое число.

-- Сб июл 11, 2009 14:06:06 --

Iosif1 в сообщении #227989 писал(а):
Можно ли для начала задать вопросы:
1.Существует ли формула, обеспечивающая точное значение искомой величины факториала?
Да: $n! = \prod\limits_{i=1}^{n}i$

Iosif1 в сообщении #227989 писал(а):
2.Труднозатратный ли по времени расчёт искомой величины факториала по формуле Стирлинга и стандартным способом?
Зависит от требуемой точности.

Iosif1 в сообщении #227989 писал(а):
Возможно ли уточнения величин факториалов, расчитанных изначально по формуле Стирлинга?
Возможно. Формула Стирлинга включает бесконечную сумму, которую можно посчитать с любой точностью.

Iosif1 в сообщении #227989 писал(а):
3.Какие из значений факториалов к настоящему времени известны, и где с ними можно ознакомиться?
Т.к. для факториалов есть точная формула, то можно сказать, что все значения факториалов известны.

Iosif1 в сообщении #227989 писал(а):
Кроме этого хочется узнать, какая закономерность используется в программе, например РНР?

http://ru.wikipedia.org/wiki/%D0%A1%D0% ... 0%B5%D0%BB ,
В этой программе используется определение простого числа, т.е. неделимость на любые натуральные числа, кроме $1$ и самого числа. Весьма неэффективный метод.

Iosif1 в сообщении #227989 писал(а):
и если можно и в других, показанных по этой же ссылке, используются ли закономерности, отличные от решета Эрастофена (классического или преобразованного)?
Насколько я знаю, нет способа быстрее решета Эратосфена для поиска всех простых чисел до какого-либо предела.

Iosif1 в сообщении #227989 писал(а):
Это вызвано желанием разместить на форуме алгоритм построения числового ряда простых чисел, основанного на использовании факториала, и позволяющего рассчитывать простые числа значительно превосходящие, известные ныне.
Вам известен такой способ?

 Профиль  
                  
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 22:08 


24/11/06
564
г.Донецк,Украина
venco в сообщении #228017 писал(а):
Ну, например, есть такая теорема: $(p-1)!\ =\ -1$ modulo $p$ iff $p$ - простое число.

Можно это же словестно! Или примером.
Я такого не проходил

venco в сообщении #228017 писал(а):
Да: $n! = \prod\limits_{i=1}^{n}i$

Это что? Последовательное перемножение чисел числового ряда?

venco в сообщении #228017 писал(а):
Зависит от требуемой точности.

Обязательно первой точности.

venco в сообщении #228017 писал(а):
Возможно. Формула Стирлинга включает бесконечную сумму, которую можно посчитать с любой точностью.

И обязательной точности?

venco в сообщении #228017 писал(а):
Т.к. для факториалов есть точная формула, то можно сказать, что все значения факториалов известны.


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

venco в сообщении #228017 писал(а):
Насколько я знаю, нет способа быстрее решета Эратосфена для поиска всех простых чисел до какого-либо предела.

Есть способ, по которому мной разработан алгоритм: "Методика определения делимости чисел..." Работа показывалась и на данном форуме. К сожалению она апробирована только на таблицах Эксель. Более мощные программы мне не подвластны. Невнимание к ней удивляет меня, но увы...
Работа посвящена определению делимости чисел и их факторизации.
Нахождение новых простых чисел - задача более простая. После получения ответов на мои посты я более конкретно сообщу Вам о такой возможности.
Мне кажется, что препятствием являются временные трудозатраты при расчёте факториалов.

venco в сообщении #228017 писал(а):
Вам известен такой способ?

На этот вопрос я, вроде, ответил.

 Профиль  
                  
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 22:22 
Аватара пользователя


17/05/08
358
Анк-Морпорк
Дело в том, что необязательно $p!+1$ будет простым.

 Профиль  
                  
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 22:27 
Заслуженный участник


11/05/08
32166
Iosif1 в сообщении #227989 писал(а):
Возможно ли уточнения величин факториалов, расчитанных изначально по формуле Стирлинга?

Запросто. Например, следующий член асимптотики (так, по памяти): $\ldots\cdot(1-{1\over12n}+\ldots).$ Жаль только, что к простым числам это отношения не имеет...

 Профиль  
                  
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 22:34 


24/11/06
564
г.Донецк,Украина
General в сообщении #228023 писал(а):
Дело в том, что необязательно $p!+1$ будет простым.

Я это не утверждаю, и, по моему, venco тоже.

 Профиль  
                  
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 22:38 


09/07/09
30
Iosif1 в сообщении #227989 писал(а):
Существует ли формула, обеспечивающая точное значение искомой величины факториала?

Сломал мозг. Можно более простыми словами?

 Профиль  
                  
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 22:49 


24/11/06
564
г.Донецк,Украина
Vanuan в сообщении #228027 писал(а):
Сломал мозг. Можно более простыми словами?

Меня интересуют существующие методы расчёта факториала числа и временные трудозатраты на эти операции.

-- Сб июл 11, 2009 23:55:26 --

ewert в сообщении #228024 писал(а):
Запросто. Например, следующий член асимптотики (так, по памяти): $\ldots\cdot(1-{1\over12n}+\ldots).$ Жаль только, что к простым числам это отношения не имеет...

Если Вы пробежитесь по теме, то, при желании, сможите меня значительно просветить.
Точное определение факториала, по моему мнению, должно иметь самое непосредственное отношение к простым числам.

 Профиль  
                  
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение12.07.2009, 02:40 
Заслуженный участник


04/05/09
4582
Iosif1 в сообщении #228021 писал(а):
venco в сообщении #228017 писал(а):
Ну, например, есть такая теорема: $(p-1)!\ =\ -1$ modulo $p$ iff $p$ - простое число.

Можно это же словестно! Или примером.
Я такого не проходил
Я догадываюсь.
По простому это можно сформулитовать так:
если $p$ простое, то $(p-1)! + 1$ делится на $p$, например $(7-1)!+1=721=7 \times 103$
если $p$ составное, то $(p-1)! + 1$ не делится на $p$, например $(6-1)!+1=121=6 \times 20 + 1$

Iosif1 в сообщении #228021 писал(а):
venco в сообщении #228017 писал(а):
Да: $n! = \prod\limits_{i=1}^{n}i$

Это что? Последовательное перемножение чисел числового ряда?
Да.

Iosif1 в сообщении #228021 писал(а):
venco в сообщении #228017 писал(а):
Зависит от требуемой точности.

Обязательно первой точности.
Тогда по простому перемножить целые числа будет проще и быстрее.

Iosif1 в сообщении #228021 писал(а):
venco в сообщении #228017 писал(а):
Т.к. для факториалов есть точная формула, то можно сказать, что все значения факториалов известны.


Тогда мне не понятно, почему не определяются всё новые и новые простые числа. Сколько необходимо времени для расчёта факториала длиной, равной длине самого большого простого числа, известного в настоящее время?
Очень мало факториалов дают простые числа. См. Factorial Prime. Всего известно 23 простых числа вида $n!-1$ и 19 простых чисел вида $n!+1$. Проблема не в расчёте факториала, а в проверке простоты получившегося числа.

Iosif1 в сообщении #228021 писал(а):
venco в сообщении #228017 писал(а):
Насколько я знаю, нет способа быстрее решета Эратосфена для поиска всех простых чисел до какого-либо предела.

Есть способ, по которому мной разработан алгоритм: "Методика определения делимости чисел..." Работа показывалась и на данном форуме. К сожалению она апробирована только на таблицах Эксель. Более мощные программы мне не подвластны. Невнимание к ней удивляет меня, но увы...
Я подозреваю, у вас там либо ошибка, либо нет ничего нового.

Iosif1 в сообщении #228021 писал(а):
Работа посвящена определению делимости чисел и их факторизации.
Нахождение новых простых чисел - задача более простая. После получения ответов на мои посты я более конкретно сообщу Вам о такой возможности.
Давайте.

Iosif1 в сообщении #228021 писал(а):
Мне кажется, что препятствием являются временные трудозатраты при расчёте факториалов.
Вы ошибаетесь, главным препятствием является сложность проверки простоты большого числа.

-- Сб июл 11, 2009 19:48:34 --

Iosif1 в сообщении #228028 писал(а):
Vanuan в сообщении #228027 писал(а):
Сломал мозг. Можно более простыми словами?

Меня интересуют существующие методы расчёта факториала числа и временные трудозатраты на эти операции.
Если нужно точное значение, то наверно быстрее просто перемножить все последовательные числа. В результате получится число длины порядка $n \log(n)$, и потребует времени на вычисление порядка $n \log(n)^2$.

 Профиль  
                  
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение12.07.2009, 06:02 


20/04/09

113
К слову сказать любой $n!$ лежит в интервале от $n^{[\frac{n}{2}]}$ до $n^{[\frac{n}{2}]+1}$
Причем факториалы разных чисел прижиматся то к левому краю, то к правому, а то вообще посередине, причем без всякой закономерности 8-)

 Профиль  
                  
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение12.07.2009, 06:29 
Заслуженный участник


04/05/09
4582
Откуда вы это взяли?
$10! \notin [{10}^5,{10}^6]$

 Профиль  
                  
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение12.07.2009, 08:14 
Заслуженный участник


11/05/08
32166
LetsGOX в сообщении #228039 писал(а):
К слову сказать любой $n!$ лежит в интервале от $n^{[\frac{n}{2}]}$ до $n^{[\frac{n}{2}]+1}$

Это не только неверно, но и неправдоподобно, т.к. $\displaystyle n!\sim\sqrt{2\pi n}\left({n\over e}\right)^n.$

 Профиль  
                  
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение12.07.2009, 13:16 


24/11/06
564
г.Донецк,Украина
venco в сообщении #228038 писал(а):
Я подозреваю, у вас там либо ошибка, либо нет ничего нового.

Если Вы можете написать программу по разработанной "Методике определения делимости чисел...", с удовольствием ознакомлю с работой. Работа есть в электронном виде (файлы). Но на форум их не доставить. При согласии могу выслать на ваш почтовый адрес.
Начало работы есть в Интернете - могу дать ссылку для ознакомления. Как Вам удобней.
Лучше собственного опыта убеждений нет.

venco в сообщении #228038 писал(а):
Если нужно точное значение, то наверно быстрее просто перемножить все последовательные числа. В результате получится число длины порядка $n \log(n)$, и потребует времени на вычисление порядка $n \log(n)^2$.

Спасибо за ответы. Подскажите в каких единицах получаем время? В секундах?

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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