Поиск простого числа по новому

[Побережный Александр]

Доказательство простоты большого простого числа - это отдельная задача.

Введем понятие - "скорее всего простые" числа. Это числа, которые прошли вероятностный тест на простоту, но еще не прошли процедуру доказательства простоты.

Dmitriy40, вы можете найти по одному простому ("скорее всего простому") числу с 5000, 10000, 15000 десятичных знаков? Просто чтобы оценить время поиска таких больших чисел. Поскольку перебор будет конечен, можно приблизительно знать время поиска таких простых с определенным количеством знаков.

[Dmitriy40]

Побережный Александр в сообщении #1318350 писал(а):

Dmitriy40, вы можете найти по одному простому ("скорее всего простому") числу с 5000, 10000, 15000 десятичных знаков?

По идее могу, но времени надо ... Я ошибся с оценкой, за 12ч проверены n=1405, 1406 и треть 1407 (т.е. примерно по 5-6 часов на каждый n) - и ни одной пары не найдено. А это примерно 5010 цифр. Сколько ещё оно бы искалось - не знаю, может и неделю, раз уж в интервалах 200-300 и 300-400 их всего по три было ... Столько времени жалко. С 10000 и 15000 цифр всё ещё намного медленнее (думаю минимум квадратично по количеству цифр).

[Побережный Александр]

Dmitriy40, я правильно понял, что вы искали пару простых чисел, которые в сумме дают праймориал с $n=1405$ и нашли всего три простых числа вида $1405\#/2\pm2^m$ за 6 часов?
Другими словами, на поиск одного простого числа с 5000 десятичных знака уходило приблизительно 2 часа.

[Dmitriy40]

Побережный Александр
Искал да, сразу пару, а вот нашлись ли простые не знаю, это не проверялось. Пар же не нашлось вообще. Сейчас ещё раз запущу, уже для отдельных простых, посмотрим сколько их для $p_{1405}\#/2 \pm 2^m$.

[Someone]

Побережный Александр в сообщении #1318372 писал(а):

Другими словами, на поиск одного простого числа с 5000 десятичных знака уходило приблизительно 2 часа.
Dmitriy40, я правильно понял, что вы искали пару простых чисел, которые в сумме дают праймориал с $n=1405$ и нашли всего три простых числа вида $1405\#/2\pm2^m$ за 6 часов?
Другими словами, на поиск одного простого числа с 5000 десятичных знака уходило приблизительно 2 часа.

Вы совершенно неправильно поняли. Dmitriy40 искал такие пары $n$, $m$, что оба числа $p_n\#/2\pm 2^m$ простые. Исследование двух значений $n=1405$, $n=1406$ и частичное исследование третьего $n=1407$ заняло $6$ часов времени, и никаких подходящих $m$ найдено не было.

Следующий код в программе Wolfram Mathematica

PP = 1; k = 1; While[PP < 10^5000, k++; PP = PP*Prime[k]];
 Print["k = ", k, ": ", Prime[k], ", ", Floor[Log10[PP] + 1]];
 m = 0; MM = 1; TFp = TFm = True;
 Print[Timing[While[TFp && TFm, m++; MM = 2 MM; If[MM > PP, Break[]]; 
   TFm = ¬ PrimeQ[PP - MM]; TFp = ¬ PrimeQ[PP + MM]]]];
 If[¬ TFm, Print[Prime[k], ("# - 2")^m]];
 If[¬ TFp, Print[Prime[k], ("# + 2")^m]];

выдаёт такой результат:

k = 1404: 11699, 5004
{193.066838,Null}
11699# + 2^37

Если в предыдущем коде заменить число $5000$ на $10000$, то результат будет такой:

k = 2585: 23167, 10001
{237.558323,Null}
23167# - 2^6

В фигурных скобках показано время выполнения программы в секундах. Как видите, первое "скорее всего простое" число $11699\#/2+2^{37}$ ($5004$ десятичные цифры), было найдено за $193$ секунды (после поверки $2\cdot 37=74$ чисел), а второе — $23167\#/2-2^6$ ($10001$ десятичная цифра) — за $238$ секунд (после проверки $2\cdot 6=12$ чисел).
Я подставил в показатель степени число $15000$, и программа уже $16$ часов считает и ничего не находит. Попробую дождаться результата. Можно попробовать написать скрипт для программы PFGW. Она специализированная и должна работать быстрее.

Метод проверки на простоту, который использует Wolfram Mathematica, корректно работает только для чисел, меньших $10^{16}$, а для бо́льших чисел он иногда (очень редко) может ошибаться, поэтому это те самые "скорее всего простые". То же самое касается программы PFGW: она может доказать простоту очень большого числа, если это число удовлетворяет определённым условиям, но ваши числа к таким не относятся; однако проверку она устраивает серьёзную.

В принципе простоту чисел (до $10^{40000}$, если не ошибаюсь) может доказывать программа PRIMO, о которой я писал.

[Dmitriy40]

Someone в сообщении #1318432 писал(а):

Исследование двух значений $n=1405$, $n=1406$ и частичное исследование третьего $n=1407$ заняло $6$ часов времени, и никаких подходящих $m$ найдено не было.

Не совсем так, 12ч на всё, по 5-6ч на каждый $n$ (учитывая быстрое возрастание предела для $m$ время заметно растёт с каждым $n$ и отдельно для каждого $n$ я не отследил).

Спасибо за наводку на $n=1404, \, 2585$, сейчас перезапущу свою для проверки.
Да, для $n=1404$ минимальное $+2^{37}$. За 74с, проверено очевидно $2\cdot37=74$ чисел, практически по секунде на число.
Для $n=2585$ тоже подтверждаю $-2^6$, за 73с, проверено $11$ чисел, уже почти по 7с на число.

Побережный Александр
Для $n=1405$ найдены простые: $-2^{57}, +2^{336}, +2^{472}, +2^{548}, +2^{559}$. Считалось 2 минуты для первого и 26 минут всего (просчитано далеко не до конца, остановил сам).

-- 09.06.2018, 16:17 --

Someone
Смотрю в Ваш код и не вижу деления $p_n\#$ пополам. Как так? У меня в коде деления нет потому что я пропускаю $p_{n=1}=2$ при начальном умножении и получаю в $p$ сразу половину нужной величины, а Вы?

[Someone]

Dmitriy40 в сообщении #1318439 писал(а):

Смотрю в Ваш код и не вижу деления $p_n\#$ пополам. Как так? У меня в коде деления нет потому что я пропускаю $p_{n=1}=2$ при начальном умножении и получаю в $p$ сразу половину нужной величины, а Вы?

Точно так же. Начальное значение $k=1$, а тело цикла начинается с $k++$.

Dmitriy40 в сообщении #1318439 писал(а):

Не совсем так, 12ч на всё, по 5-6ч на каждый $n$

Даже так…

Dmitriy40 в сообщении #1318439 писал(а):

Да, для $n=1404$ минимальное $+2^{37}$. За 74с, проверено очевидно $2\cdot37=74$ чисел, практически по секунде на число.
Для $n=2585$ тоже подтверждаю $-2^6$, за 73с, проверено $11$ чисел, уже почти по 7с на число.

Либо PARI/GP для таких расчётов эффективнее, чем Wolfram Mathematica, либо у Вас компьютер быстрее. Надо попробовать ваш код на моём компьютере. Этот код — тот самый?

[Dmitriy40]

Someone в сообщении #1318444 писал(а):

Точно так же.

А, понял, ступил, спасибо.

Someone в сообщении #1318444 писал(а):

Этот код — тот самый?

Не, тот сильно избыточный, лучше вот этот (считает прямо сейчас для $n=3707$ уже почти час, первая строка формирует p и n, вторая ищет наименьшее m):

p=1;n=1;while(p<10^15001,n++;p*=prime(n));
print1("n=",n,", m:");m=2;while(m<p,if(ispseudoprime(p-m),print1(" -2^",logint(m,2));break);if(ispseudoprime(p+m),print1(" +2^",logint(m,2));break);m*=2);print

Время автоматом не выдаст, я его получаю командой ## в консоли PARI/GP после остановки счёта.

Someone в сообщении #1318444 писал(а):

либо у Вас компьютер быстрее

У меня Core i5-4690 @3.6ГГц, Win7x64 и PARI/GP (gp64.exe) идёт на одном ядре.

[Someone]

(Dmitriy40)

Вложение:

Proc.gif [ 3.78 Кб | Просмотров: 2511 ]

Спасибо, попробую для сравнения.

[Dmitriy40]

Ну вот поэтому наверное и примерно вдвое медленнее, частоты ж. Но проверьте, интересно сравнить математику и пари.

Для $n=3707$ проверены $m<213$ за 1ч46м, практически по 4 числа в минуту. При этом $m$ может быть почти до 50 тысяч, т.е. полная проверка одного этого $n$ у меня займёт более 200-х часов. Это перебор.

[Dmitriy40]

Для $n=3707$ проверены $m<1130$ за 9.5ч, ничего не найдено, надоело, закрыл.

[Побережный Александр]

Если предположить выполнение гипотезы и одно простое число существует, то спустя двадцать суток вычислений его найдем. Начинает влиять временной фактор. Так как будет конечное число вариантов перебора, возможны такие варианты: либо одна машина считает 20 суток, либо 50 машин считают по 10 часов в своем интервале, чтобы покрыть весь заданный интервал. На мой взгляд, это определенный "плюс" метода.

Можно для простых вида $p_n\#/2\pm2^m$ ограничиться поиском простых до 10000 десятичных знаков.

Для больших чисел искать простые вида $p_n\#/2\pm2(p_{n+1})^m$ или другие виды задания числа. Это уменьшает количество вариантов перебора.

[Someone]

Побережный Александр в сообщении #1318682 писал(а):

Так как будет конечное число вариантов перебора, возможны такие варианты: либо одна машина считает 20 суток, либо 50 машин считают по 10 часов в своем интервале, чтобы покрыть весь заданный интервал. На мой взгляд, это определенный "плюс" метода.

Вы воображаете, что Вы первым додумались до идеи распараллеливания вычислений? Например, программа PRIMO, доказывая простоту большого числа, может распараллелить вычисления на 48 процессоров. Проект поиска простых чисел Мерсенна распараллелен на тысячи компьютеров (можете тоже присоединиться к этому проекту, тогда и ваш компьютер будет участвовать в этих вычислениях). И я также не вижу никакого "плюса" в том, что метод поиска простых чисел даёт лишь конечное число кандидатов для проверки.

[Dmitriy40]

Можно многое. Вопросов два:
1) Собственно зачем?
2) Что эффективнее (в среднем; в конкретной точке; для чисел конкретного вида)?
На 2) есть соображения: учитывая вероятность простых порядка $1/ \ln x$, для чисел около $10^{10000}$ надо проверить порядка 23 тысяч чисел для нахождения первого простого. С учётом эвристик (кратные 2,3,5,7,11,13,17,19 не проверять, требуется всего 600КБ памяти и полсекунды на все 23 тысячи) количество уменьшится до 4 тысяч. $m$ же может быть более 33 тысяч, т.е. проверить надо до 66 тысяч чисел. Разница в 16 раз, правда первое число в среднем, а второе максимум, но распределение второго числа пока и неизвестно. В общем эффективность под вопросом.
На 1) соображений нет. В криптографии применять такие числа опасно (их слишком мало, легко быстро проверить все).

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

[Побережный Александр]

Dmitriy40 в сообщении #1318715 писал(а):

1) Собственно зачем?

Dmitriy40, я не рекорды предлагаю делать. Я пытаюсь понять законы появления простых чисел. Не могу доказать, почему в праймориале будут обязателно два простых числа. Но они появляются. Вы сами этому удивлялись. Мне потому и интересно было рассмотреть большие простые числа. Будут ли там появляться простые определенного вида. Для $n<1000$ вы простым перебором убедились в этом. Но это не доказательство, что так будет всегда.

Dmitriy40 в сообщении #1318715 писал(а):

учитывая вероятность простых порядка $1/ \ln x$

Это средняя вероятность появления простого числа. Но чтобы найти следующее простое число больше заданного $N$, надо искать в интервале$[N;N+(lnN)^2]$. Для чисел порядка $10^{10000}$ надо проверить не $23000$ чисел, как вы считаете, а $(23000)^2$. Это число намного больше. Здесь простым перебором уже не справиться. Надо придумывать другие способы вычислений.

Someone в сообщении #1318700 писал(а):

Вы воображаете, что Вы первым додумались до идеи распараллеливания вычислений?

Ни в коем случае я так не думаю! Я просто подчеркнул, о его возможной применимости.
Кстати, по поводу чисел Мерсенна. Их всего нашли 50 штук, тем не менее проект продолжается, хотя для меня это бессмысленная гонка. Закон появления чисел Мерсенна неизвестен, может вообще их конечное число. )
В моей гипотезе хоть какая-то закономерность есть в появлении простых чисел. Уже то, что они лежат в определенном интервале говорит о многом. Например можно оценить время их поиска. Это нам с успехом продемонстрировал Dmitriy40 при работе с числом порядка $10^{15000}$.