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

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

Уважаемые софорумники, хочу поделиться своим способом поиска простого числа в интервале, достаточно большом, чтобы содержать простые числа.
У меня есть программа факторизации, которая раскладывает на множители 30-значные числа. Чтобы найти простое число. выполняется следующий алгоритм:
1. Выбираем произвольное число в пределах нижней границы интервала.
2. Программой раскладываем на множители.
3. Если получилось простое число, процесс останавливается.
4. Если получилось составное число, то к нему прибавляем наименьший множитель без единицы.
5. С новым числом переходим в пункт 2 и цикл повторяется.

Пример. Пусть надо найти простое число в пределах интервала от 50 до 60.
выбираем число 49
$49=7\cdot7$
$49+(7-1)=55$ составное, повторяем процедуру уже с числом 55
$55=5\cdot11$
$55+(5-1)=59$ простое число

За все время использования этого алгоритма всегда получал простое число.
Возникает вопрос, а может ли такой алгоритм зациклиться? То есть, за конечное число циклов невозможно получить простое число. У меня ответа нет.

Понятно, что операция факторизации трудоемкая. Но можно предложить немного модернизированный вариант.

Алгоритм:
1. Выбирает произвольное нечетное составное число $A$
2. Построим число $B=2A+(2-1)$
3. Если получили составное число, повторяем пункт 2, но в качестве числа $A$ будет выступать число $B$.

Пример: пусть $A=49$
$B=2\cdot49+(2-1)=99$ составное число, повторяем цикл
$C=2\cdot99+(2-1)=199$ простое число

[Cash]

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

-- Чт дек 19, 2013 18:28:53 --

Ага, нашел. Такие нехорошие числа генерируются числами Ризеля

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

Cash, большое спасибо за полезную информацию! Я так понимаю, по первому алгоритму так однозначно ответить нельзя?

[Cash]

Это Вы про зацикливания что ли?
А Вы проверьте на всех числах до миллиона. Если гипотеза подтвердится (в чем есть большие сомнения) будем думать дальше.

[Someone]

Cash в сообщении #803742 писал(а):

Это Вы про зацикливания что ли?
А Вы проверьте на всех числах до миллиона. Если гипотеза подтвердится (в чем есть большие сомнения) будем думать дальше.

Метод, конечно, непрактичный из-за необходимости разложения на простые множители, тем более, что для больших чисел это нужно проделывать много раз. Для чисел порядка $10^{100}$ разложение на множители является чрезвычайно трудоёмкой задачей, и поиск простого числа такого размера в настоящее время превратится в непосильную задачу. Для чисел порядка $10^{50}$ задача вполне осуществимая, но требующая много времени.
Обычно простые числа ищут или в арифметических прогрессиях, или среди случайных чисел.
Например, в программе Mathematica 5.1 это можно сделать так. Сначала для удобства определим функцию, которая ищет простое число в заданном промежутке:

RP[a_Integer, b_Integer] := Module[{p, k}, k = 0; Label[One]; p = Random[Integer, {Min[a, b], Max[a, b]}]; k++; If[¬ PrimeQ[p], Goto[One]]; {k, p}]

А затем будем искать стозначные простые числа командой

Timing[RP[10^99, 10^100 - 1]]

Вот результаты трёх запусков:

{0.094 Second, {241, 3497272595820281454664276953652790343250146482044693148828840290142096286847097707189729132107364493}}

{0.094 Second, {416, 3931349754388581399463815401230611581102729548322447129439450981074145932969360659984645133307351533}}

{0.141 Second, {494, 9410281456082685220062615083796778093978280318062064663516867732838722427196773151704596649069031801}}

Здесь первое число — время работы функции RP, второе — количество проверенных чисел, третье — найденное простое число.

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

Timing[ProvablePrimeQ[P]]

(куда вместо буквы "P" нужно подставить проверяемое число) следующие:

{11.981 Second, True}

{6.147 Second, True}

{2.511 Second, True}

Сертификат для стозначного простого числа — это довольно длинный текст, поэтому я его не привожу.

По поводу зацикливания предложенного метода. Я проверил числа до $2000000$, зацикливания нет. Функция, которая по заданному натуральному числу $x>1$ предложенным методом находит простое число $p\geqslant x$, может быть, например, такой:

DP[x_Integer] := Module[{f, k, n}, n = x; k = 0;
While[¬ PrimeQ[n], f = FactorInteger[n]; n = n + f[[1, 1]] - 1; k++; Print["p = ", f[[1, 1]], ", n = ", n]]; k]

Пример:

DP[115]
p = 5, n = 119
p = 7, n = 125
p = 5, n = 129
p = 3, n = 131
4

Первая строчка — это команда, последняя — число шагов алгоритма. В промежуточных строчках $p$ — наименьший простой делитель проверяемого числа, $n$ — новое проверяемое число, полученное прибавлением $p-1$. Последнее значение $n$ — найденное простое число.

Для использования в цикле операторы печати нужно убрать, поэтому функция будет выглядеть так:

DPP[x_Integer] := Module[{f, k, n}, n = x; k = 0; While[¬ PrimeQ[n], f = FactorInteger[n]; n = n + f[[1, 1]] - 1; k++]; k]

Цикл, проверяющий натуральные числа до $2000000$ и отыскивающий число, требующее наибольшего числа шагов, выглядит так:

K = 0; For[m = 2, m ≤ 2000000, m++, KK = DPP[m]; If[KK > K, K = KK; M = m]]; Print["K = ", K, ", M = ", M]

Запустив его и подождав некоторое время, получим результат:

K = 59, M = 900660

Это означает, что среди чисел, не превышающих двух миллионов, наибольшее число шагов (а именно, $59$) требует число $900660$. С помощью приведённой выше функции DP можно выяснить, что после $59$ шагов получится простое число $904601$. (Наименьшее простое число, которое следует за $900660$, есть $900671$.)

Побережный Александр, я всё это написал, чтобы Вы мне позавидовали, обзавелись системой компьютерной математики, способной выполнять нужные Вам вычисления, и сами проверяли свои идеи с её помощью.

Возможность зацикливания мне представляется маловероятной. Предположим, что цикл наименьших простых делителей есть $\{p_1,p_2,\ldots,p_m\}$. Ясно, что число $2$ в этом цикле встретиться не может, так как чётным может быть только самое первое число, а все следующие автоматически нечётные. Далее, если $p=\max\{p_1,p_2,\ldots,p_m\}$, то сумма $T=\sum\limits_{i=1}^m(p_i-1)=\sum\limits_{i=1}^mp_i-m$ должна делиться на все простые числа, не превосходящие $p$. Например, если $p=17$, то $T$ должно делиться на $17\#=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17=510510$. Ясно также, что одно и то же простое число в периоде не может встретиться дважды подряд, поэтому должно быть не менее двух различных нечётных простых чисел. В частности, поэтому $p\geqslant 5$ и $T$ делится на $5\#=2\cdot 3\cdot 5=30$. Мы также можем считать, что первый делитель в периоде равен $p$. Искать период можно следующими рассуждениями.

Пусть $p=5$. Тогда, как уже сказано, $T$ должно делиться на $30$. Пусть мы начинаем с нечётного числа $x_1=x$, делящегося на $p_1=p=5$ (и не делящегося на $3$). Тогда следующее число $x_2=x_1+5-1=x+4$ должно делиться на $p_2=3$. Третье число $x_3=x_2+3-1=x+6$ должно делиться на $p_3=5$, но это невозможно, так как $x$ по предположению делится на $p_1=5$.

Пусть $p=7$. Тогда $T$ делится на $7\#=210$. Начинаем с нечётного числа $x_1=x$, делящегося на $p_1=p=7$ и не делящегося на меньшие нечётные простые числа $3$ и $5$. Получаем $x_2=x_1+7-1=x+6$. Оно не может делиться на $3$, так как иначе и $x_1$ делилось бы на $3$, тогда как у $x_1$ наименьший простой делитель равен $7$. Поэтому $x_2$ должно делиться на $p_2=5$. Следующее число равно $x_3=x_2+5-1=x+10$. Оно должно делиться либо на $3$, либо на $7$. На $7$ оно делиться не может, так как $x_1$ делится на $7$, а разность $x_3-x_1$ на $7$ не делится. Если $x_3$ делится на $p_3=3$, то $x_4=x_3+3-1=x+12$. Оно не может делиться на $5$, так как $x_2$ делится на $5$, а $x_4-x_2=6$ не делится на $5$. Число $x_4$ не может делиться также на $7$, так как $x_1$ делится на $7$, а разность $x_4-x_1=12$ не делится на $7$.

Далее нужно рассматривать $p=11$ и так далее. Рассуждения выглядят вполне программируемыми. В процессе добавления нового элемента цикла $p_i$ возникают коллизии двух типов:
1) при некотором $k<i$ оказывается, что $p_k=p_i$, в то время как $x_i-x_k$ не делится на $p_i$;
2) при некотором $k<i$ оказывается, что $x_i-x_k$ делится на $p_i$, в то время как $p_i<p_k$.
Если этих коллизий удалось избежать, и цепочка продолжилась до такого $m$, что $x_m-x_1$ делится на $p\#$ (произведение всех простых чисел, не превосходящих выбранного $p$), то цикл закончен, но необходимо проверить ещё одно условие.
3) Если простое число $q<p$ не встречается в цикле $\{p_1,p_2,\ldots,p_m\}$, то множество остатков $\{(x_i-x_1)\pmod{q}:p_i>q\}$ не должно совпадать с множеством $\{0,1,2,\ldots,q-1\}$.
Проверку этого условия также можно осуществлять в процессе построения, постепенно исключая из проверяемого списка те числа, которые включаются в цикл. Это позволит сократить перебор.
Если это условие тоже выполняется (например, если чисел, упомянутых в последнем условии, вообще нет), то остаётся только выяснить, какие остатки при делении на простые числа, не превосходящие $p$, может давать начальное число $x_1$, и найти его. На нём алгоритм, предложенный в первом сообщении, будет зацикливаться.

Мне как-то не верится, что такой цикл удастся найти, но чем чёрт не шутит… Идей по доказательству отсутствия такого цикла у меня нет.

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

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

Побережный Александр, я всё это написал, чтобы Вы мне позавидовали, обзавелись системой компьютерной математики, способной выполнять нужные Вам вычисления, и сами проверяли свои идеи с её помощью.

Someone, я в самом деле вам завидую и эта зависть белая-белая! ))
Спасибо за такой развернутый ответ.

В алгоритме ключевой элемент - это наименьший множитель.
Обязательное ли это условие? можно ли с любым множителем проводить подобные выкладки?

[Someone]

Как определите свой алгоритм, так и будет. А уж как он будет работать — разбирайтесь сами. Но лучше всё-таки не гробить компьютерное время разложением на множители и искать простые числа в арифметической прогрессии. Вот результаты таких поисков: http://primes.utm.edu/primes/download.php.

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

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

Здесь есть ещё одна проблема. Дело в том, что использованная функция PrimeQ является простой (и потому быстрой), и не даёт гарантии, что проверенное и "объявленное простым" число обязательно является простым, хотя вероятность ошибки очень мала. Но на такой случай есть функция ProvablePrimeQ, которая проверяет, действительно ли число простое, и, если её "попросить", печатает сертификат, удостоверяющий, что число действительно простое (или, наоборот, составное). Сертификат потом может быть проверен другой программой.

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

[Someone]

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

я уже нашел простое число с более чем 30000 десятичных знаков.

Откуда Вы совершенно точно знаете, что оно простое? Оно какого-то специального вида, для которого это доказывается сравнительно быстро?
На сайте http://primes.utm.edu/ можно много узнать о поиске больших простых чисел и найти ссылки на программы, предназначенные для такого поиска.

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

Это число как раз вписывается в таблицу, приведенную в вашей ссылке.

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

5000  8067*2^1076571+1                 324085 L2241 2013

Оно содержит 324085 цифр в десятичной записи. В таблице есть существенно меньшие числа (их номера больше 5000), но это числа каких-то специальных видов, которые признаны "особо интересными".

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

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

Не знаю такую программу. Я пользовался программой Primo, но она ограничена размером 10000 цифр, причём, для таких чисел нужны месяцы работы программы, чтобы вычислить сертификат. Primo использует теорию эллиптических кривых.