Двоїстий алгоритм пошуку простих чисел на відрізках великих розмірностей

Анотація

Запропоновано матричну модель підпослідовності натуральних чисел з мультиплікативним базисом з перших простих чисел. Матрична модель – квадратна матриця, вектор-стовпці якої є арифметичними прогресіями з різницею і кількістю прогресій, що дорівнює добутку елементів базису. Викресливши арифметичні прогресії з першими членами, кратними елементам базису, дістанемо симетричну розріджену матрицю, яка містить усі прості числа підпослідовності натуральних чисел, крім базисних, що підвищує щільність простих чисел у розріджених матрицях. Розріджені матриці явно не формуються. Формується лише вектор перших членів арифметичних прогресій. Доведені властивості розріджених матриць, виведені формули, що прискорюють обчислення складених чисел в арифметичних прогресіях, визначена структура елементів вектора перших членів арифметичних прогресій, досліджена зв’язність симетричних частин розріджених матриць. З розширенням базису зростає у векторі перших членів кількість пар елементів з різницею, що дорівнює степеню двійки («близнята», «четвірки» тощо). Це є необхідною умовою існування констант, для яких лінійні рівняння двох змінних можуть мати нескінченну множину розв’язків у простих числах. Іррегулярність розподілу простих чисел у підпослідовностях натуральних чисел пов’язана з структурою елементів вектора перших членів. Побудовано алгоритм пошуку простих чисел на відрізках великих розмірностей з паралельним процесом обчислень. Запропонований алгоритм є двоїстим до алгоритмів просіювання підпослідовностей натуральних чисел за простими дільниками. У цих алгоритмах не можна розпаралелити процес обчислень, оскільки процедура просіювання вимагає зберігання числової інформації попередніх кроків (векторна модель обробки масивів). Двоїстий алгоритм паралельно обчислює складені числа в кожній парі арифметичних прогресій з симетричними першими членами, використовуючи лише вектор перших членів арифметичних прогресій, що дозволяє обробляти масиви великих розмірностей.