2014 dxdy logo

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

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




 
 Таблицы Менделеева простых чисел
Сообщение12.12.2008, 14:10 
Занимаясь простыми числами обнаружил интересное свойство: все простые числа укладываются в табличные формы, своеобразные таблицы Менделеева простых чисел.
Как следствие, возможность предсказывать местоположение простых чисел.
Используя такие таблицы я легко (относительно) нашел простое число с 20000 десятичных знаков.
Обоснование смотрите здесь: http://paii1.narod.ru/ideya/simple1.htm
В приложении приведены сами таблицы.

 
 
 
 
Сообщение15.12.2008, 09:26 
Увы, в народе это называется "вариации на тему "Решето Эратосфена"".
Я все это сам когда-то находил.

Не совсем понятно про простое число с 20000 знаков. Можете написать подробно, как Вы его нашли?

 
 
 
 Местоположение простых
Сообщение15.12.2008, 13:42 
Я даже не спорю, что предложенный метод есть разновидность "решета Эратосфена".
Интересно другое, что в расположении простых существует определенная система.
Любое простое число можно записать в виде a*П(p(i))+b, где 0<a<p(i+1), b не делится на 2,3,...,p(i), П(p(i))-праймориал. Соответственно, можно предположить, что задавая a и b можно получить простое число. Посмотрите на мои примеры:
2*П(p(3535))+1, 2*П(p(3535))+p(3695), 446*П(p(3535))+1 это простые числа.
p(3535)=32983, p(3695)=34591
Причем первые два числа это подряд идущие простые числа.
А вот и мое простое, которое имеет 20000 десятичных знака:
П(p(4792))+p(5201), где p(4792)=46337, p(5201)=50767

 
 
 
 
Сообщение15.12.2008, 14:11 
Аватара пользователя
Побережный Александр в сообщении #167801 писал(а):
А вот и мое простое, которое имеет 20000 десятичных знака:
П(p(4792))+p(5201), где p(4792)=46337, p(5201)=50767

И доказательство есть, что число простое?

 
 
 
 
Сообщение15.12.2008, 15:42 
В расчетах я использовал математический пакет Mathematica. Проверял неоднократно.
Нашел еще простое число с 31000 десятичных знаков. Правда другим способом.
Если интересно могу выложить.

 
 
 
 
Сообщение15.12.2008, 16:15 
Аватара пользователя
Побережный Александр в сообщении #167819 писал(а):
В расчетах я использовал математический пакет Mathematica. Проверял неоднократно.

Я спрашивала, есть ли доказательство, что число простое. Вы что, проверяли МАТЕМАТИКОЙ делимость на все числа, меньшие корня из Вашего? Если не так, то как? Выкладывать число не нужно, расскажите как проверяли.

 
 
 
 
Сообщение16.12.2008, 03:31 
Наверное в пакете есть функция от числа, но даже в этом случае достоверность результата не равна 100 процентам, а несколько меньше. Много результатов будет правильными, но какие то ошибочными.

 
 
 
 
Сообщение17.12.2008, 00:33 
Аватара пользователя
Побережный Александр в сообщении #167801 писал(а):
П(p(4792))+p(5201), где p(4792)=46337, p(5201)=50767


Так Вы каким образом доказывали простоту? Например, программа PrimeForm выдаёт такой отчёт:

Код:
Primality testing 46337#+50767 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 5
Running N-1 test using base 7
Running N+1 test using discriminant 13, base 8+sqrt(13)
Calling N-1 BLS with factored part 0.03% and helper 0.02% (0.11% proof)
46337#+50767 is Fermat and Lucas PRP! (667.3604s+0.0135s)


То есть, до доказательства простоты этого числа ей как до Луны пешком.

P.S. По-английски простые числа называются prime, а не simple.

 
 
 
 Опа!
Сообщение17.12.2008, 21:00 
Прошу прощения, но я с такой постановкой вопроса не знаком. Подскажите, пожалуйста, каким образом доказывается простота числа? Я считал, что математический пакет дает точный ответ: простое число или нет.

 
 
 
 
Сообщение17.12.2008, 21:29 
Аватара пользователя
Если у нас есть число N, то, чтобы доказать, что онол простое, нужно пробовать его делить на все простые числа от 2 до $\left[\sqrt{n}\right]$

В случае отрицательных ответов, число будет простым однозначно. Но для больших чисел такая проверка даже на современных компьютерах займёт огромное количество времени. (тем более, что перед проверкой числа n нужно иметь предварительно построенную таблицу всех простых, не превосходящих корня из него, чтобы знать, на что делить. Ну или тогда уж деля на все нечётные, обоётись без таблицы)

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

 
 
 
 
Сообщение17.12.2008, 22:04 
Аватара пользователя
А каким пакетом Вы пользуетесь? Скорее всего, в нём заложен так называемый вероятностный алгоритм проверки, который не доказывает, что число простое, но делает это утверждение весьма вероятным.

Вообще, доказательство простоты такого большого числа требует колоссальных вычислительных ресурсов. Программа OpenPFGW (бывшая PrimeForm) специально предназначена для этого, но она справляется с доказательством только в том случае, когда может найти (или ей сообщат) разложение на простые множители достаточно большой части числа $N-1$ или $N+1$. Практически это ограничивает её применимость числами достаточно специальных видов. На сайте The Prime Pages можно найти список 5000 наибольших известных простых чисел, посмотрите, какие числа в этом списке. На этом же сайте найдёте описание методов проверки простоты.
Для "произвольных" чисел доказательство простоты использует более трудоёмкие методы, например, метод эллиптических кривых, реализованный в программе Primo. Но эта программа ограничена числами, содержащими не более 10000 цифр в десятичной записи, так как для бóльших чисел требуются годы расчётов. Рекорд для этой программы - число $18517\#+39317$ (7993 десятичные цифры).

Цитата:
The certification of this number, done by Pierre Cami with Primo 2.2.0 beta 4, took eight months using a PC with an AMD 2GHz processor. ("N#" stands for "Primorial(N)", i.e., the product of all the primes less than or equal to N.)


Что касается Вашего числа, то оно почти наверняка простое, но PrimeForm не смогла это доказать, а для Primo оно слишком большое.

 
 
 
 Значит простое?
Сообщение18.12.2008, 14:41 
Значит я могу считать свое число простым, пока не доказано обратное? Я так понимаю, что речь идет о сертификации простого числа. Я слышал такой термин.

 
 
 
 
Сообщение18.12.2008, 15:34 
Аватара пользователя
Побережный Александр в сообщении #168715 писал(а):
Значит я могу считать свое число простым, пока не доказано обратное?
Нет, Вы не можете считать это число простым, пока простоту полностью не докажете. Это называется презумпция виновности в математике.

 
 
 [ Сообщений: 13 ] 


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