2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: Поиск простого числа по новому
Сообщение13.06.2018, 14:15 
Заслуженный участник


20/08/14
11066
Россия, Москва
Спасибо Someone за формулу для $M_n$, теперь оказалось возможным подсчитать средний выигрыш от использования формулы $p_n\#/2\pm2^m$ для поиска простых вместо последовательной проверки. Выигрыш есть и медленно растёт с увеличением $n$. Например для $n=2975$ с 11718 цифр до нахождения первого простого в среднем надо проверить 1470 чисел вместо 26980 (которые сократятся в лучшем случае до 5 тысяч исключением проверки кратных малым простым). А для $n=899769$ с количеством цифр уже более 6 млн, проверить надо почти 470 тысяч вместо почти 14 млн (сокращаемых лишь до 2.2 млн). О времени проверки даже одного числа умолчу. :-)

 Профиль  
                  
 
 Re: Поиск простого числа по новому
Сообщение13.06.2018, 17:57 


29/07/08
536
Someone в сообщении #1318912 писал(а):
Можно оценить ожидаемое количество простых чисел в вашем методе. Как обычно, $p_n$ обозначает $n$-ое простое число.
При большом $n$ почти все числа вида $p_n\#/2\pm 2^m$, где $2^m<p_n\#/2$, расположены вблизи числа $p_n\#/2$.
Плотность множества простых чисел вблизи большого числа $A=p_n\#/2$ оценивается выражением $\frac 1{\ln A}$. Количество проверяемых Вами чисел оценивается выражением $2\log_2A$.
Все проверяемые числа лежат в множестве чисел, взаимно простых с $p_n\#$; плотность этого множества можно оценить как $d_n=\prod\limits_{k=1}^n\left(1-\frac 1{p_k}\right)$. Например, получаем $d_{1404}\approx 0{,}0599066$, $d_{2585}\approx 0{,}0558193$, $d_{3707}\approx 0{,}0536692$.
Поэтому ожидаемое количество простых чисел можно оценить выражением $$M_n=\frac{2\log_2A}{d_n\ln A}=\frac 2{d_n\ln 2}.$$ Например, $M_{1404}\approx 48$, $M_{2585}\approx 52$, $M_{3707}\approx 54$ (результаты округлены до ближайшего целого).

Попробую оценить снизу количество простых.
По неравенству Чебышёва $0,92(\frac{A}{\ln(A)})<\pi(A)<1,11(\frac{A}{\ln(A)})$
Максимальная плотность простых чисел вблизи числа $A=p_n\#/2$ оценивается выражением $\frac{1,11}{\ln(A)}$
Отклонение от ожидаемого выражения оценивается выражением $\log_2A$
Максимальное отклонение от ожидаемого будет выражаться $\Delta M_n=\frac{1,11}{d_n\ln{2}}$
Следовательно, ожидаемое количество простых чисел будет лежать в интервале $[M_n-\Delta M_n;M_n+\Delta M_n]$
Другими словами $[\frac{2-1,11}{d_n\ln{2}};\frac{2+1,11}{d_n\ln{2}}]$
Нижняя граница всегда больше единицы. Соответственно, в праймориале простое число вида $p_n\#/2\pm2^m$ всегда найдется.

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


23/07/05
17973
Москва
Побережный Александр в сообщении #1319598 писал(а):
Максимальное отклонение от ожидаемого будет выражаться $\Delta M_n=\frac{1,11}{d_n\ln{2}}$
Не пройдёт. Если бы такие вещи доказывались подобными рассуждениями…

 Профиль  
                  
 
 Re: Поиск простого числа по новому
Сообщение17.06.2018, 19:23 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Затратив примерно $100$ часов, программа OpenPFGW закончила проверку $n=2585$, $1\leqslant m\leqslant 33222$. Найдено $55$ кандидатов в простые числа (прогнозировалось $52$). Файл со списком прилагается.

Dmitriy40 в сообщении #1318564 писал(а):
Для $n=3707$ проверены $m<1130$ за 9.5ч, ничего не найдено, надоело, закрыл.
Запустил проверку для $n=3707$. Спустя примерно $11{,}5$ часов было найдено псевдопростое число (по основанию $3$): $34703\#/2-2^{1420}$. Полная проверка для данного $n$, как ожидается, займёт примерно $400$ часов.


Вложения:
pfgw.log [968 байт]
Скачиваний: 183
 Профиль  
                  
 
 Re: Поиск простого числа по новому
Сообщение18.06.2018, 07:55 


29/07/08
536
Someone, я вас поздравляю!
Вы попутно установили рекордный результат среди праймориальных простых чисел (7 место) и рекордный результат среди факториальных (12 место). :D

 Профиль  
                  
 
 Re: Поиск простого числа по новому
Сообщение18.06.2018, 11:02 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Это Вы про что? Подробнее, пожалуйста. Со ссылками, если таковые имеются.

 Профиль  
                  
 
 Re: Поиск простого числа по новому
Сообщение18.06.2018, 12:01 


29/07/08
536
http://primes.utm.edu/top20/page.php?id=5 - рекорды по праймориальным простым числам.
http://primes.utm.edu/top20/page.php?id=30 - рекорды по факториальным простым числам.

-- Пн июн 18, 2018 12:04:44 --

Ваше "скорее всего" простое число имеет $15000$ десятичных знаков.

 Профиль  
                  
 
 Re: Поиск простого числа по новому
Сообщение18.06.2018, 12:10 


16/10/14

667

(Оффтоп)

Разрешите задать вопрос: каково сейчас наибольшее простое число такое, что все простые числа меньшие его найдены?

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


23/07/05
17973
Москва
Побережный Александр в сообщении #1320766 писал(а):
Ваше "скорее всего" простое число имеет $15000$ десятичных знаков.
Это: $34703\#/2-2^{1420}$? $15004$. Но оно не праймориальное и не факториальное. Первые имеют вид $n\#\pm 1$, вторые — вид $n!\pm 1$. Кроме того, имеющихся у меня вычислительных ресурсов не хватит, чтобы доказать, что оно простое, а не только псевдопростое (для праймориальных и факториальных чисел хватило бы, поскольку для таких чисел существуют эффективные тесты).

-- Пн июн 18, 2018 13:41:17 --

SpiderHulk в сообщении #1320768 писал(а):

(Оффтоп)

Разрешите задать вопрос: каково сейчас наибольшее простое число такое, что все простые числа меньшие его найдены?
Понятия не имею. И в каком смысле "известны"? Имеется полный список в печатном виде или в виде набора файлов на каком-нибудь компьютерном носителе?
И для чего Вы хотите это знать? Чтобы взять самое большое число в этом списке и, запустив какой-нибудь пакет компьютерной математики, за ничтожную долю секунды побить этот рекорд? Например, Wolfram Mathematica:
Код:
Timing[NextPrime[10^50]]
{0.015600, 100000000000000000000000000000000000000000000000151}
Потом запустить PRIMO и за $0{,}02$ с получить сертификат простого числа. Файлы сюда не загрузились, поэтому их содержимое приведу в тексте.

(Входной файл: 10^50.in)

Код:
[Candidate]
N=100000000000000000000000000000000000000000000000151

(Отчёт о выполнении задачи: primo-B3E5F02D7CC7C.tr)

Код:
[PRIMO - Task Report]
Version=3.0.9
WebSite=http://www.ellipsa.eu/
Task=Certification
ID=B3E5F02D7CC7C
Created=06.18.2018 01:14:57 PM

[Common]
Path=D:\D\Programming\Primo 3.0.9\work\
Selected=1
Processed=1
Certified=1
Candidate #1=Certified, 0.02s

[Candidate #1]
Input=10^50.in
Report=primo-B3E5F02D7CC7C-001.cr
Output=primo-B3E5F02D7CC7C-001.out
Status=Candidate certified prime

(Отчёт о сертификации: primo-B3E5F02D7CC7C-001.cr)

Код:
[PRIMO - Certification Report]
Version=3.0.9
WebSite=http://www.ellipsa.eu/
ID=B3E5F02D7CC7C
Created=06.18.2018 01:14:57 PM
Certificate=D:\D\Programming\Primo 3.0.9\work\primo-B3E5F02D7CC7C-001.out
TestCount=8

[Backtrack]
Count=0

[1]
Type=1
Run=1
Gain=32

[2]
Type=3
Run=1
Gain=16
D=-3
H=1
G=1

[3]
Type=3
Run=1
Gain=20
D=-4
H=1
G=1

[4]
Type=1
Run=1
Gain=30

[5]
Type=1
Run=1
Gain=14

[6]
Type=1
Run=1
Gain=4

[7]
Type=3
Run=1
Gain=15
D=-3
H=1
G=1

[8]
Type=0
Run=1
Gain=36

(Сертификат: primo-B3E5F02D7CC7C-001.out)

Код:
[PRIMO - Primality Certificate]
Version=3.0.9
WebSite=http://www.ellipsa.eu/
Format=3
ID=B3E5F02D7CC7C
Created=06.18.2018 01:14:57 PM
TestCount=8
Status=Candidate certified prime

[Comments]
No comment in the input file

[Running Times]
Initialization=0.00s
1stPhase=0.01s
2ndPhase=0.01s
Total=0.02s

[Candidate]
File=D:\D\Programming\Primo 3.0.9\work\10^50.in
N$=446C3B15F9926687D2C40534FDB564000000000097
HexadecimalSize=42
DecimalSize=51
BinarySize=167

[1]
Type=1
S$=E0346076
R$=4E20481A8728DF37D5933642A6D1B6FF31
B$=2

[2]
Type=3
S$=106B1
R$=4C22D3141D8F14CDA9DED5997D3F85
A$=0
B$=-13881206A1CA37CDF564CD90A9B46DBFAD
T$=3

[3]
Type=3
S$=F02D2
R$=5126F45C0B8E726787E7BB981
A$=2
B$=0
T$=1

[4]
Type=1
S$=369AAE80
R$=17C76D7D644EA5C30F
B$=2

[5]
Type=1
S$=5D36
R$=414EDE905D3185
B$=2

[6]
Type=1
S$=C
R$=5713D36B26ECB
B$=2

[7]
Type=3
S$=8DC9
R$=9D38F973F
A$=0
B$=10
T$=2

[8]
Type=0

[Signature]
1$=6782DA2102C31C70770ACB0AA87BF9463205A4A7
2$=A495D6CC53173CE0A2E2ABE11C9E0AF0231DDF3D

 Профиль  
                  
 
 Re: Поиск простого числа по новому
Сообщение18.06.2018, 14:37 
Заслуженный участник


20/08/14
11066
Россия, Москва
SpiderHulk в сообщении #1320768 писал(а):
каково сейчас наибольшее простое число такое, что все простые числа меньшие его найдены?
Тут надо смотреть научные результаты, мне немного лень, потому опишу простой способ получить оценку снизу: посмотреть в вики интервалы между простыми, докуда они проверены и известны, значит все числа меньшие уже определены. В английской вики приведено число 15 570 628 755 536 096 243, плюс я где-то видел что проверены все числа до $2^{64}\approx 2\cdot10^{19}$. Ещё где-то видел о проверке всех простых до $10^{22}$ (но интервалы при этом не проверялись и в вики не вошли, тут кажется проверяли аппроксимацию функции количества простых), но совсем не уверен в точности цифры.
Если нужна более точная оценка - надо искать научные публикации.

Напомню, полный список нигде в интернете не получить (вероятно, я могу не знать как именно выкладывали результаты научные группы), он слишком велик (порядка 400 миллионов миллиардов простых чисел до $2^{64}$) и жалко места на серверах и трафика по сети. Ну и обычно быстрее его насчитать заново чем откуда-то скачивать. Для оценки скорости можно взять данные самой быстрой программы, она выдаёт простые числа около $10^{19}$ со скоростью миллиард простых чисел за 150 секунд (на 3.7ГГц процессоре в один поток). Перекачать по сети этот список надо скорость 20ГБ/150с, т.е. примерно гигабит в секунду, инет пока ещё почти у всех медленнее, а вот многопоточные (многоядерные) процессоры есть уже у всех, а уж про видеокарты совсем молчу.

 Профиль  
                  
 
 Re: Поиск простого числа по новому
Сообщение18.06.2018, 15:03 


16/10/14

667
Someone в сообщении #1320783 писал(а):
И для чего Вы хотите это знать? Чтобы взять самое большое число в этом списке и, запустив какой-нибудь пакет компьютерной математики, за ничтожную долю секунды побить этот рекорд?

Скорее всего кто то этим уже занимается и считает программой простые числа подряд. Вот и интересно, докуда досчитано
Dmitriy40 в сообщении #1320836 писал(а):
Ещё где-то видел о проверке всех простых до $10^{22}$

Спасибо

 Профиль  
                  
 
 Re: Поиск простого числа по новому
Сообщение18.06.2018, 15:32 
Аватара пользователя


29/04/13
7128
Богородский
SpiderHulk
Можно действовать и по-другому. Есть способы находить Prime counting function($pi(n)$) аналитически. Значения $pi(n)$ уже найдены до $n=10^{27}$ включительно. Например, посмотрите ссылки к A006880.

Сможете найти $pi(n)$ для $n=10^{27}-100$ ? Если количество будет отличаться ровно на единицу, значит в этой сотне ровно одно простое число.

 Профиль  
                  
 
 Re: Поиск простого числа по новому
Сообщение18.06.2018, 15:42 
Заслуженный участник


20/08/14
11066
Россия, Москва
Yadryara в сообщении #1320854 писал(а):
Есть способы находить Prime counting function($pi(n)$) аналитически. Значения $pi(n)$ уже найдены до $n=10^{27}$ включительно.
Вот спасибо, значит я таки ошибся с порядком цифры, он не 22, а 27 (до $pi(n)$ в вики не добрался по ссылкам).

 Профиль  
                  
 
 Re: Поиск простого числа по новому
Сообщение19.06.2018, 04:07 


10/03/16
3871
Aeroport
Someone в сообщении #1320783 писал(а):
И для чего Вы хотите это знать? Чтобы взять самое большое число в этом списке и, запустив какой-нибудь пакет компьютерной математики, за ничтожную долю секунды побить этот рекорд?


А это противозаконно?

 Профиль  
                  
 
 Re: Поиск простого числа по новому
Сообщение19.06.2018, 10:03 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
ozheredov в сообщении #1321017 писал(а):
А это противозаконно?
Нет, побитие рекордов не противозаконно. Но в данном случае совершенно не интересно: если уже где-то имеется "список всех простых чисел, не превосходящих $n$", то нахождение "наименьшего простого числа, бо́льшего $n$", требует столь ничтожных усилий, что это можно делать хоть сто раз в день. А если запрограммировать это в цикле, то уж и не знаю, сколько раз.

А вот поиск простого числа, достойного включения в список "5000 наибольших известных простых чисел", уже требует весьма серьёзных усилий. Ну так флаг Вам в руки и танк навстречу.

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

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



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

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


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

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