2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Поиск простого числа в интервале
Сообщение19.12.2013, 16:23 


29/07/08
536
Уважаемые софорумники, хочу поделиться своим способом поиска простого числа в интервале, достаточно большом, чтобы содержать простые числа.
У меня есть программа факторизации, которая раскладывает на множители 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$ простое число

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


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

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

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

 Профиль  
                  
 
 Re: Поиск простого числа в интервале
Сообщение19.12.2013, 21:14 


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

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


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

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


23/07/05
17973
Москва
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$, и найти его. На нём алгоритм, предложенный в первом сообщении, будет зацикливаться.

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

 Профиль  
                  
 
 Re: Поиск простого числа в интервале
Сообщение23.12.2013, 13:31 


29/07/08
536
Someone в сообщении #804111 писал(а):
Побережный Александр, я всё это написал, чтобы Вы мне позавидовали, обзавелись системой компьютерной математики, способной выполнять нужные Вам вычисления, и сами проверяли свои идеи с её помощью.

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

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

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


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

 Профиль  
                  
 
 Re: Поиск простого числа в интервале
Сообщение25.12.2013, 20:33 


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


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

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


23/07/05
17973
Москва
Побережный Александр в сообщении #806121 писал(а):
я уже нашел простое число с более чем 30000 десятичных знаков.
Откуда Вы совершенно точно знаете, что оно простое? Оно какого-то специального вида, для которого это доказывается сравнительно быстро?
На сайте http://primes.utm.edu/ можно много узнать о поиске больших простых чисел и найти ссылки на программы, предназначенные для такого поиска.

Побережный Александр в сообщении #806121 писал(а):
Это число как раз вписывается в таблицу, приведенную в вашей ссылке.
Не вписывается. Там наименьшее число вот прямо сейчас, когда я пишу ответ, есть
Код:
5000  8067*2^1076571+1                 324085 L2241 2013
Оно содержит 324085 цифр в десятичной записи. В таблице есть существенно меньшие числа (их номера больше 5000), но это числа каких-то специальных видов, которые признаны "особо интересными".

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

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



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

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


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

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