Это Вы про зацикливания что ли?
А Вы проверьте на всех числах до миллиона. Если гипотеза подтвердится (в чем есть большие сомнения) будем думать дальше.
Метод, конечно, непрактичный из-за необходимости разложения на простые множители, тем более, что для больших чисел это нужно проделывать много раз. Для чисел порядка
![$10^{100}$ $10^{100}$](https://dxdy-01.korotkov.co.uk/f/4/0/f/40f92fd1553ca05a6465c8d79275a86a82.png)
разложение на множители является чрезвычайно трудоёмкой задачей, и поиск простого числа такого размера в настоящее время превратится в непосильную задачу. Для чисел порядка
![$10^{50}$ $10^{50}$](https://dxdy-01.korotkov.co.uk/f/4/a/2/4a22bde622f93101435146673c0295de82.png)
задача вполне осуществимая, но требующая много времени.
Обычно простые числа ищут или в арифметических прогрессиях, или среди случайных чисел.
Например, в программе 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$ $2000000$](https://dxdy-03.korotkov.co.uk/f/a/5/3/a538d02ad8ead8f7e1de72450ea9994e82.png)
, зацикливания нет. Функция, которая по заданному натуральному числу
предложенным методом находит простое число
![$p\geqslant x$ $p\geqslant x$](https://dxdy-01.korotkov.co.uk/f/8/d/9/8d986a9f408abf947bb741f9da486e5a82.png)
, может быть, например, такой:
Код:
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$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
— наименьший простой делитель проверяемого числа,
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
— новое проверяемое число, полученное прибавлением
![$p-1$ $p-1$](https://dxdy-02.korotkov.co.uk/f/5/8/5/585cf0d6605a58bb5df9e272ae37244a82.png)
. Последнее значение
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
— найденное простое число.
Для использования в цикле операторы печати нужно убрать, поэтому функция будет выглядеть так:
Код:
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$ $2000000$](https://dxdy-03.korotkov.co.uk/f/a/5/3/a538d02ad8ead8f7e1de72450ea9994e82.png)
и отыскивающий число, требующее наибольшего числа шагов, выглядит так:
Код:
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$ $59$](https://dxdy-03.korotkov.co.uk/f/2/3/a/23a831e7dff417a176b23e5bd8b8de9482.png)
) требует число
![$900660$ $900660$](https://dxdy-01.korotkov.co.uk/f/0/8/e/08ea8f2f6da6598addf75c07aacb83c182.png)
. С помощью приведённой выше функции DP можно выяснить, что после
![$59$ $59$](https://dxdy-03.korotkov.co.uk/f/2/3/a/23a831e7dff417a176b23e5bd8b8de9482.png)
шагов получится простое число
![$904601$ $904601$](https://dxdy-04.korotkov.co.uk/f/b/4/c/b4cda65abbdba56f4416b635012b31a482.png)
. (Наименьшее простое число, которое следует за
![$900660$ $900660$](https://dxdy-01.korotkov.co.uk/f/0/8/e/08ea8f2f6da6598addf75c07aacb83c182.png)
, есть
![$900671$ $900671$](https://dxdy-01.korotkov.co.uk/f/0/4/6/046d7d21d77b6cb34cc126ce73b3bef782.png)
.)
Побережный Александр, я всё это написал, чтобы Вы мне позавидовали, обзавелись системой компьютерной математики, способной выполнять нужные Вам вычисления, и сами проверяли свои идеи с её помощью.
Возможность зацикливания мне представляется маловероятной. Предположим, что цикл наименьших простых делителей есть
![$\{p_1,p_2,\ldots,p_m\}$ $\{p_1,p_2,\ldots,p_m\}$](https://dxdy-02.korotkov.co.uk/f/5/b/9/5b9c03acc531b2b6026d08450858b3eb82.png)
. Ясно, что число
![$2$ $2$](https://dxdy-04.korotkov.co.uk/f/7/6/c/76c5792347bb90ef71cfbace628572cf82.png)
в этом цикле встретиться не может, так как чётным может быть только самое первое число, а все следующие автоматически нечётные. Далее, если
![$p=\max\{p_1,p_2,\ldots,p_m\}$ $p=\max\{p_1,p_2,\ldots,p_m\}$](https://dxdy-04.korotkov.co.uk/f/3/4/6/3462bd4eca3f883d74b61c0f50baba4982.png)
, то сумма
![$T=\sum\limits_{i=1}^m(p_i-1)=\sum\limits_{i=1}^mp_i-m$ $T=\sum\limits_{i=1}^m(p_i-1)=\sum\limits_{i=1}^mp_i-m$](https://dxdy-03.korotkov.co.uk/f/2/0/9/209948eb8ebd51fa82e2ff635e4e0b5682.png)
должна делиться на все простые числа, не превосходящие
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
. Например, если
![$p=17$ $p=17$](https://dxdy-02.korotkov.co.uk/f/5/0/5/5059a2881c6d9b7c0a3bd516adcd070682.png)
, то
![$T$ $T$](https://dxdy-03.korotkov.co.uk/f/2/f/1/2f118ee06d05f3c2d98361d9c30e38ce82.png)
должно делиться на
![$17\#=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17=510510$ $17\#=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17=510510$](https://dxdy-02.korotkov.co.uk/f/5/a/0/5a04172997df2684b4469d18113cd04d82.png)
. Ясно также, что одно и то же простое число в периоде не может встретиться дважды подряд, поэтому должно быть не менее двух различных нечётных простых чисел. В частности, поэтому
![$p\geqslant 5$ $p\geqslant 5$](https://dxdy-04.korotkov.co.uk/f/7/a/a/7aa94ccddbac07c6639dd46da2bd0ac482.png)
и
![$T$ $T$](https://dxdy-03.korotkov.co.uk/f/2/f/1/2f118ee06d05f3c2d98361d9c30e38ce82.png)
делится на
![$5\#=2\cdot 3\cdot 5=30$ $5\#=2\cdot 3\cdot 5=30$](https://dxdy-04.korotkov.co.uk/f/3/6/6/366f01d1155038c3f9bed9596621a72c82.png)
. Мы также можем считать, что первый делитель в периоде равен
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
. Искать период можно следующими рассуждениями.
Пусть
![$p=5$ $p=5$](https://dxdy-04.korotkov.co.uk/f/3/c/a/3ca231d3f2808398c86dfb41c007113382.png)
. Тогда, как уже сказано,
![$T$ $T$](https://dxdy-03.korotkov.co.uk/f/2/f/1/2f118ee06d05f3c2d98361d9c30e38ce82.png)
должно делиться на
![$30$ $30$](https://dxdy-01.korotkov.co.uk/f/0/8/f/08f4ed92f27cec32cdd7a6ecd580f9e782.png)
. Пусть мы начинаем с нечётного числа
![$x_1=x$ $x_1=x$](https://dxdy-04.korotkov.co.uk/f/7/b/d/7bd5a2f9811dbbe79e16d1741b027b6f82.png)
, делящегося на
![$p_1=p=5$ $p_1=p=5$](https://dxdy-01.korotkov.co.uk/f/0/8/6/0864a32ba353b269b5c0874a07c9541182.png)
(и не делящегося на
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
). Тогда следующее число
![$x_2=x_1+5-1=x+4$ $x_2=x_1+5-1=x+4$](https://dxdy-03.korotkov.co.uk/f/6/2/5/6256acb35434c56acc05b9ab713f432582.png)
должно делиться на
![$p_2=3$ $p_2=3$](https://dxdy-02.korotkov.co.uk/f/5/9/0/5908962cf6acdf709773807a495e44e882.png)
. Третье число
![$x_3=x_2+3-1=x+6$ $x_3=x_2+3-1=x+6$](https://dxdy-02.korotkov.co.uk/f/d/0/d/d0da3ffaea648051d1a0ed26d5e7f6c982.png)
должно делиться на
![$p_3=5$ $p_3=5$](https://dxdy-04.korotkov.co.uk/f/3/d/1/3d18f01921fca0fa8217799291ac0f1f82.png)
, но это невозможно, так как
![$x$ $x$](https://dxdy-04.korotkov.co.uk/f/3/3/2/332cc365a4987aacce0ead01b8bdcc0b82.png)
по предположению делится на
![$p_1=5$ $p_1=5$](https://dxdy-03.korotkov.co.uk/f/2/2/3/22385ca566080a9cef0e80ae647e0aa482.png)
.
Пусть
![$p=7$ $p=7$](https://dxdy-04.korotkov.co.uk/f/b/a/7/ba746a72ef35fe3153e6e9011711350f82.png)
. Тогда
![$T$ $T$](https://dxdy-03.korotkov.co.uk/f/2/f/1/2f118ee06d05f3c2d98361d9c30e38ce82.png)
делится на
![$7\#=210$ $7\#=210$](https://dxdy-04.korotkov.co.uk/f/b/4/e/b4eabd0794a51b6c04c9c7151fffb1a082.png)
. Начинаем с нечётного числа
![$x_1=x$ $x_1=x$](https://dxdy-04.korotkov.co.uk/f/7/b/d/7bd5a2f9811dbbe79e16d1741b027b6f82.png)
, делящегося на
![$p_1=p=7$ $p_1=p=7$](https://dxdy-02.korotkov.co.uk/f/5/4/8/5483586719bed9efdf1bf6ae64208c6b82.png)
и не делящегося на меньшие нечётные простые числа
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
и
![$5$ $5$](https://dxdy-02.korotkov.co.uk/f/9/6/1/9612eecfec9dadf1a81d296bd247377782.png)
. Получаем
![$x_2=x_1+7-1=x+6$ $x_2=x_1+7-1=x+6$](https://dxdy-04.korotkov.co.uk/f/3/6/e/36e7343a4194ef4a2074b658dc95bcdc82.png)
. Оно не может делиться на
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
, так как иначе и
![$x_1$ $x_1$](https://dxdy-03.korotkov.co.uk/f/2/7/7/277fbbae7d4bc65b6aa601ea481bebcc82.png)
делилось бы на
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
, тогда как у
![$x_1$ $x_1$](https://dxdy-03.korotkov.co.uk/f/2/7/7/277fbbae7d4bc65b6aa601ea481bebcc82.png)
наименьший простой делитель равен
![$7$ $7$](https://dxdy-04.korotkov.co.uk/f/b/7/a/b7afe912ac7ed280f96e7cfb0f35a02782.png)
. Поэтому
![$x_2$ $x_2$](https://dxdy-02.korotkov.co.uk/f/9/5/d/95d239357c7dfa2e8d1fd21ff6ed5c7b82.png)
должно делиться на
![$p_2=5$ $p_2=5$](https://dxdy-04.korotkov.co.uk/f/f/9/c/f9cf7585ab8ebb04cb77a2511574c14a82.png)
. Следующее число равно
![$x_3=x_2+5-1=x+10$ $x_3=x_2+5-1=x+10$](https://dxdy-02.korotkov.co.uk/f/5/8/b/58b7e9c2553e7ceb01191591727f3c2d82.png)
. Оно должно делиться либо на
![$3$ $3$](https://dxdy-02.korotkov.co.uk/f/5/d/c/5dc642f297e291cfdde8982599601d7e82.png)
, либо на
![$7$ $7$](https://dxdy-04.korotkov.co.uk/f/b/7/a/b7afe912ac7ed280f96e7cfb0f35a02782.png)
. На
![$7$ $7$](https://dxdy-04.korotkov.co.uk/f/b/7/a/b7afe912ac7ed280f96e7cfb0f35a02782.png)
оно делиться не может, так как
![$x_1$ $x_1$](https://dxdy-03.korotkov.co.uk/f/2/7/7/277fbbae7d4bc65b6aa601ea481bebcc82.png)
делится на
![$7$ $7$](https://dxdy-04.korotkov.co.uk/f/b/7/a/b7afe912ac7ed280f96e7cfb0f35a02782.png)
, а разность
![$x_3-x_1$ $x_3-x_1$](https://dxdy-04.korotkov.co.uk/f/f/6/7/f6750330e4df5ca14a6ae9881a44db8482.png)
на
![$7$ $7$](https://dxdy-04.korotkov.co.uk/f/b/7/a/b7afe912ac7ed280f96e7cfb0f35a02782.png)
не делится. Если
![$x_3$ $x_3$](https://dxdy-03.korotkov.co.uk/f/2/c/5/2c52641cc5fa73cbbdf887c89d82f0de82.png)
делится на
![$p_3=3$ $p_3=3$](https://dxdy-04.korotkov.co.uk/f/f/7/4/f742faf84d9af7de7f8ca28dd2630a2f82.png)
, то
![$x_4=x_3+3-1=x+12$ $x_4=x_3+3-1=x+12$](https://dxdy-02.korotkov.co.uk/f/1/2/6/126df806dc44b146fad52f641ec2f9bb82.png)
. Оно не может делиться на
![$5$ $5$](https://dxdy-02.korotkov.co.uk/f/9/6/1/9612eecfec9dadf1a81d296bd247377782.png)
, так как
![$x_2$ $x_2$](https://dxdy-02.korotkov.co.uk/f/9/5/d/95d239357c7dfa2e8d1fd21ff6ed5c7b82.png)
делится на
![$5$ $5$](https://dxdy-02.korotkov.co.uk/f/9/6/1/9612eecfec9dadf1a81d296bd247377782.png)
, а
![$x_4-x_2=6$ $x_4-x_2=6$](https://dxdy-01.korotkov.co.uk/f/0/c/f/0cf0592b5100392111eee9d70d118fd682.png)
не делится на
![$5$ $5$](https://dxdy-02.korotkov.co.uk/f/9/6/1/9612eecfec9dadf1a81d296bd247377782.png)
. Число
![$x_4$ $x_4$](https://dxdy-02.korotkov.co.uk/f/9/8/2/98281ac06ae64c568765342739c6722082.png)
не может делиться также на
![$7$ $7$](https://dxdy-04.korotkov.co.uk/f/b/7/a/b7afe912ac7ed280f96e7cfb0f35a02782.png)
, так как
![$x_1$ $x_1$](https://dxdy-03.korotkov.co.uk/f/2/7/7/277fbbae7d4bc65b6aa601ea481bebcc82.png)
делится на
![$7$ $7$](https://dxdy-04.korotkov.co.uk/f/b/7/a/b7afe912ac7ed280f96e7cfb0f35a02782.png)
, а разность
![$x_4-x_1=12$ $x_4-x_1=12$](https://dxdy-02.korotkov.co.uk/f/9/7/9/9792d71e266a95f6896ea9875dd9333682.png)
не делится на
![$7$ $7$](https://dxdy-04.korotkov.co.uk/f/b/7/a/b7afe912ac7ed280f96e7cfb0f35a02782.png)
.
Далее нужно рассматривать
![$p=11$ $p=11$](https://dxdy-03.korotkov.co.uk/f/a/d/8/ad87857476742636f1bfd15101afdcff82.png)
и так далее. Рассуждения выглядят вполне программируемыми. В процессе добавления нового элемента цикла
![$p_i$ $p_i$](https://dxdy-01.korotkov.co.uk/f/0/d/1/0d19b0a4827a28ecffa01dfedf5f5f2c82.png)
возникают коллизии двух типов:
1) при некотором
![$k<i$ $k<i$](https://dxdy-03.korotkov.co.uk/f/6/2/3/623a83a5151552b052efb50957caf03d82.png)
оказывается, что
![$p_k=p_i$ $p_k=p_i$](https://dxdy-04.korotkov.co.uk/f/3/9/2/392fa6eb987446152bd650d21516c13082.png)
, в то время как
![$x_i-x_k$ $x_i-x_k$](https://dxdy-04.korotkov.co.uk/f/f/5/c/f5c60ca733273ffaeb383c3b564d595582.png)
не делится на
![$p_i$ $p_i$](https://dxdy-01.korotkov.co.uk/f/0/d/1/0d19b0a4827a28ecffa01dfedf5f5f2c82.png)
;
2) при некотором
![$k<i$ $k<i$](https://dxdy-03.korotkov.co.uk/f/6/2/3/623a83a5151552b052efb50957caf03d82.png)
оказывается, что
![$x_i-x_k$ $x_i-x_k$](https://dxdy-04.korotkov.co.uk/f/f/5/c/f5c60ca733273ffaeb383c3b564d595582.png)
делится на
![$p_i$ $p_i$](https://dxdy-01.korotkov.co.uk/f/0/d/1/0d19b0a4827a28ecffa01dfedf5f5f2c82.png)
, в то время как
![$p_i<p_k$ $p_i<p_k$](https://dxdy-04.korotkov.co.uk/f/b/0/8/b087e2289843059733162032382ee42482.png)
.
Если этих коллизий удалось избежать, и цепочка продолжилась до такого
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
, что
![$x_m-x_1$ $x_m-x_1$](https://dxdy-02.korotkov.co.uk/f/d/7/0/d70dfea3dcc73f6fabf83ebbd8109df582.png)
делится на
![$p\#$ $p\#$](https://dxdy-03.korotkov.co.uk/f/2/2/6/226bdc701e775389f01a775b8b239f0982.png)
(произведение всех простых чисел, не превосходящих выбранного
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
), то цикл закончен, но необходимо проверить ещё одно условие.
3) Если простое число
![$q<p$ $q<p$](https://dxdy-02.korotkov.co.uk/f/1/2/7/1275c008e9e68a3df6e0908c9cfc350382.png)
не встречается в цикле
![$\{p_1,p_2,\ldots,p_m\}$ $\{p_1,p_2,\ldots,p_m\}$](https://dxdy-02.korotkov.co.uk/f/5/b/9/5b9c03acc531b2b6026d08450858b3eb82.png)
, то множество остатков
![$\{(x_i-x_1)\pmod{q}:p_i>q\}$ $\{(x_i-x_1)\pmod{q}:p_i>q\}$](https://dxdy-03.korotkov.co.uk/f/6/1/0/61073c769d54b3adc7425c14dd57044a82.png)
не должно совпадать с множеством
![$\{0,1,2,\ldots,q-1\}$ $\{0,1,2,\ldots,q-1\}$](https://dxdy-01.korotkov.co.uk/f/0/b/2/0b2104413b625f59f8cce3fa4f80a0bd82.png)
.
Проверку этого условия также можно осуществлять в процессе построения, постепенно исключая из проверяемого списка те числа, которые включаются в цикл. Это позволит сократить перебор.
Если это условие тоже выполняется (например, если чисел, упомянутых в последнем условии, вообще нет), то остаётся только выяснить, какие остатки при делении на простые числа, не превосходящие
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
, может давать начальное число
![$x_1$ $x_1$](https://dxdy-03.korotkov.co.uk/f/2/7/7/277fbbae7d4bc65b6aa601ea481bebcc82.png)
, и найти его. На нём алгоритм, предложенный в первом сообщении, будет зацикливаться.
Мне как-то не верится, что такой цикл удастся найти, но чем чёрт не шутит… Идей по доказательству отсутствия такого цикла у меня нет.