Иллюстрированный самоучитель по Mathematica 5

Простые числа вида k * 2 n +1

Сначала определим функцию, которая по заданному номеру п простого числа q находит t – решение сравнения 3*2n +1^0 (mod q) и 5 – показатель 2 по модулю q, если такое решение существует.

f3[n_] :=
Block[(q= Prime[n],
s=MultiplicativeOrder[2,q],
t=MultiplicativeOrder[2,q,{-PowerMod[3, -1,q]}]},
If[NumberQ[t],fs,t}]]

Теперь с помощью этой функции можно сгенерировать таблицу остатков и соответствующих им модулей.

Иллюстрированный самоучитель по Mathematica 5 › Модулярная арифметика: деление с остатком, вычеты, сравнения и китайская теорема об остатках › Простые числа вида k * 2 n +1

Чтобы в таблице сначала шли меньшие модули s (они помогают отбраковать больше кандидатов), таблицу пришлось отсортировать, предварительно вычеркнув из нее элементы NULL, которые соответствуют тем простым модулям д, для которых сравнение 3*2n +1 = 0 (mod q) неразрешимо.

Каждая пара в этой таблице описывает арифметическую профессию из показателей, для которых выполняется некоторое тождественное сравнение. Пусть, например, в таблице имеется пара (s, t). Она была получена для некоторого простого числа q. Ее наличие в таблице означает, что 3*2n+1 +1 = 0 (mod q) для любых натуральных k.

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

fx[n_,t_] :=
Block[{1= Length[t],i=1,c=(i<=1) }, While[c,
{s,r}=t[[i]]; answer= (Mod [M, s]!=r); i++;
c=(i<=1)S&answer]; answer]

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

prog :=
Block[{nn=100000,Yes=0,No=0,j=1}, While[j]=nn,
If[fx[j,t],Yes++,No++]; J++1;
Print["Yes=",Yes,"; No=",No]]

Заметьте, что программа отличается от аналогичной программы для чисел вида 5*2n + 1. Отличие связано с тем, что на этот раз перебор не ограничивается только нечетными показателями. Конечно, как и для чисел вида 5-2n + 1, количество отбракованных чисел и время отбраковки зависят от размера таблицы t. Сначала давайте сгенерируем совсем небольшую таблицу.

t=Sort[DeleteCases[Array[f3.10.3],Null]]
{{3.1},{4.3},{10.7},{12.2],{18.14],{28.9),{36.28}}

Теперь запускаем программу.

prog //Timing 
Yes= 33650; No= 66350
{4.937 Second, Null}
Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.