2014 dxdy logo

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

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




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

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

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

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

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

 
 
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 19:41 
venco в сообщении #227990 писал(а):
Как вам может помочь "метод определения простых чисел, основанный на использовании значений факториалов", если "Самостоятельно рассчитать требуемые значения факториалов, у меня возможности нет"?

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

 
 
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 20:38 
Ну, например, есть такая теорема: $(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 
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 
Аватара пользователя
Дело в том, что необязательно $p!+1$ будет простым.

 
 
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 22:27 
Iosif1 в сообщении #227989 писал(а):
Возможно ли уточнения величин факториалов, расчитанных изначально по формуле Стирлинга?

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

 
 
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 22:34 
General в сообщении #228023 писал(а):
Дело в том, что необязательно $p!+1$ будет простым.

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

 
 
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 22:38 
Iosif1 в сообщении #227989 писал(а):
Существует ли формула, обеспечивающая точное значение искомой величины факториала?

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

 
 
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение11.07.2009, 22:49 
Vanuan в сообщении #228027 писал(а):
Сломал мозг. Можно более простыми словами?

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

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

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

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

 
 
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение12.07.2009, 02:40 
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 
К слову сказать любой $n!$ лежит в интервале от $n^{[\frac{n}{2}]}$ до $n^{[\frac{n}{2}]+1}$
Причем факториалы разных чисел прижиматся то к левому краю, то к правому, а то вообще посередине, причем без всякой закономерности 8-)

 
 
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение12.07.2009, 06:29 
Откуда вы это взяли?
$10! \notin [{10}^5,{10}^6]$

 
 
 
 Re: Закон возникновения простых чисел в натуральном ряду чисел
Сообщение12.07.2009, 08:14 
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 
venco в сообщении #228038 писал(а):
Я подозреваю, у вас там либо ошибка, либо нет ничего нового.

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

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

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

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


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