Простые числа вида k * 2 n +1
Поскольку проверка малых значений выполняется весьма быстро, о времени ее выполнения можно не беспокоиться. Может возникнуть и противоположный вопрос" не слишком ли рано мы запускаем отбраковку? Но мы видели, что даже отбраковка 100 000 нечетных чисел с помощью огромной таблицы, построенной с использованием первых 25 000 простых чисел, занимает всего лишь чуть более 20 минут. Так что на предварительную отбраковку одного числа требуется совсем немного времени. Ну а выигрыш отбраковка дает уже при весьма малых значениях и. Поэтому не стоит беспокоиться из-за того, что на некотором, весьма малом отрезке отбраковка может оказаться менее эффективной, чем прямая проверка. Для таблицы, построенной с использованием первых 25 000 простых чисел, перерасход времени, например, не превысит 12 секунд. Так что беспокойство по поводу того, что временные затраты на отбраковку малых значений и могут быть больше, чем на прямую проверку, необоснованно. Но перед запуском отбраковки нужно сгенерировать таблицу t. Даже если таблица строится с использованием первых 10 000 простых чисел, генерация таблицы занимает более минуты. Хотя это время (и даже большее) окупается, поведение программы из-за временных затрат на построение таблицы может показаться несколько неожиданным.
Действительно, сначала очень быстро печатаются первые значения п, затем происходит весьма заметная (но необъяснимая, если не знать причину) задержка из-за генерации таблицы, после чего опять довольно быстро печатается следующая серия небольших значений и и лишь затем (на моем компьютере после и = 5947) опять происходит весьма существенная задержка. Она связана как с отсутствием искомых значений я вплоть до n= 13165, так и с тем, что для части чисел (менее 10%) приходится выполнять полную проверку, которая теперь уже требует весьма ощутимых временных затрат. В приведенной ниже программе учтено все, о чем говорилось выше.
M5n[n_] :=Block[{j=1,nnprime=25000,primen=Prime[nnprime],nn=Min[n,primen]}, While [5*2^j+1<=primen&& j<=n,{If[MknPrime[5,j],Print[j]],j+=2}]; If[j<n, t=Sort[DeleteCases[Array[f,nnprime,4],Null]];While[j<=nn, If[fx[j,t],If[MknPrime[5,j],Print[j]]]; j+=2]]]Эта программа существенно быстрее первоначальной, и даже за короткую летнюю ночь она сможет на весьма слабеньком ПК (по нынешним представлениям, конечно) найти n = 26607.
Ну и, наконец, мораль этой истории. Хотя поначалу казалось, что предварительная отбраковка сильно усложнит программу, оказалось, что в системе Mathematica есть все необходимые функции для того, чтобы компактно записать построение необходимой таблицы и тем самым ускорить выполнение программы более чем в 10 раз!
Случай k = 3
Критерий простоты чисел вида 3*2n + 1 несколько сложнее. Впрочем, вся сложность заключается в выборе основания а, для которого проверяется сравнение аm =-1(mod k2n +1). Если и не делится на 4, то в качестве а достаточно взять 5. Иными словами, если п не делится на 4, то 3*2n + 1 будет простым тогда и только тогда, когда 52"~'* 3-1 (mod £-2"+1).
Вот как можно реализовать этот способ. Сначала определим вспомогательную функцию:
MMkn[k_, n_] := k*2^n+1Теперь запишем критерий простоты.
MM3nPrime01[n_] := Module[{t=3*2^n+1}, If[Mod[n,4]!=0,PowerMod[5,(t-1)/2,t]==t-1,PrimeQ[t]]]После этого можем написать программу поиска тех и, при которых число 3*2n +1 является простым.
MM3n[n_] :=Block[{i=l}, While [i<=n, {If[MM3nPrime01[i],Print[i]], i++}]];Конечно, данная программа работает существенно быстрее, чем написанная нами ранее для той же цели. Но все же давайте попробуем применить предварительный отсев.
Конечно, метод перебора можно усовершенствовать, если найти арифметическую прогрессию таких показателей п, для которых число 3*2n +1 делится на некоторое простое число д. Тогда показатели n, являющиеся членами этой прогрессии, при переборе можно пропустить, если 3*2n +1< q. Иными словами, можно пропустить те показатели п из этой прогрессии, для которых число 3*2n +1>q. Можно, конечно, пойти и дальше. Можно, например, взять несколько небольших нечетных простых чисел <?, для которых существует решение сравнения 3*2n +1^0 (mod q). Пусть s – показатель 2 по модулю q: T=\1(mod q). (Такое s можно найти с помощью функции MultiplicativeOrder [2, q].) Тогда при всех tmt (mod s) число 3-2n +1 = 0 (mod q). Если q не является числом вида 3*2n +1, все числа и=/ (mod s) можно опустить при переборе. Если же q является числом вида 3*2n +1, то нужно оставить только то число n=t (mod 5), при котором 3-2n +1 – q.
Иными словами, мы сможем отбраковать все те показатели п, которые принадлежат хотя бы одной из построенных нами указанным выше способом арифметических прогрессий. Как мы видели на примере чисел вида 5-2n +1, эта идея значительно повышает быстродействие программы и практически не усложняет перебор. Однако в данном случае таблицы получатся, конечно, совсем другие, и потому оптимальные параметры (главный из них – размер таблицы) придется подбирать заново.