Binary Algorithm for Finding Prime Numbers on Segments of Large Dimensions
A matrix model of subsequence of natural numbers with a multiplicative basis from the first prime numbers is proposed. The matrix model is a square matrix, where vector columns are arithmetic progressions with difference and number of progressions equal to product of base elements. By crossing out a...
Gespeichert in:
| Datum: | 2024 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Кам'янець-Подільський національний університет імені Івана Огієнка
2024
|
| Online Zugang: | http://mcm-math.kpnu.edu.ua/article/view/313241 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Mathematical and computer modelling. Series: Physical and mathematical sciences |
Institution
Mathematical and computer modelling. Series: Physical and mathematical sciences| _version_ | 1856543276024201216 |
|---|---|
| author | Абрамчук, Василь Абрамчук, Ігор |
| author_facet | Абрамчук, Василь Абрамчук, Ігор |
| author_sort | Абрамчук, Василь |
| baseUrl_str | |
| collection | OJS |
| datestamp_date | 2024-10-13T20:43:33Z |
| description | A matrix model of subsequence of natural numbers with a multiplicative basis from the first prime numbers is proposed. The matrix model is a square matrix, where vector columns are arithmetic progressions with difference and number of progressions equal to product of base elements. By crossing out arithmetic progressions with first terms which are multiples of base elements, we obtain a symmetric sparse matrix that contains all the prime numbers of subsequence of natural numbers, except for the base ones, which increases the density of prime numbers in sparse matrices. Sparse matrices are not formed clearly, only the vector of first terms of arithmetic progressions is formed. Properties of sparse matrices have been proven. Formulas that speed up the calculation of compound numbers in arithmetic progressions have been derived, the structures of vector elements of first terms of arithmetic progressions have been determined, the connectivity of symmetric parts of sparse matrices has been investigated. With the expansion of the base the number of pairs of elements with the difference equal to the power of two («twins», «fours», etc.) increases in the vector of first terms. This is a necessary condition for the existence of constants for which linear equations of two variables can have an infinite set of solutions in prime numbers. The irregularity of distribution of prime numbers in subsequences of natural numbers is related to the structure of elements of the vector of first terms. An algorithm for finding prime numbers on segments of large dimensions with a parallel calculation process has been built. The proposed algorithm is binary to algorithms for sifting subsequences of natural numbers by prime divisors. In these algorithms, it is not possible to parallelize the calculation process, since screening procedure requires storing the numerical information from the preceding steps (vector model of array processing).
The binary algorithm calculates compound numbers in each pair of arithmetic progressions with symmetric first terms simultaneously, using only vector of the first terms of arithmetic progressions, which makes possible processing of large-dimensional arrays. |
| first_indexed | 2025-07-17T10:44:01Z |
| format | Article |
| id | mcm-mathkpnueduua-article-313241 |
| institution | Mathematical and computer modelling. Series: Physical and mathematical sciences |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:44:01Z |
| publishDate | 2024 |
| publisher | Кам'янець-Подільський національний університет імені Івана Огієнка |
| record_format | ojs |
| spelling | mcm-mathkpnueduua-article-3132412024-10-13T20:43:33Z Binary Algorithm for Finding Prime Numbers on Segments of Large Dimensions Двоїстий алгоритм пошуку простих чисел на відрізках великих розмірностей Абрамчук, Василь Абрамчук, Ігор A matrix model of subsequence of natural numbers with a multiplicative basis from the first prime numbers is proposed. The matrix model is a square matrix, where vector columns are arithmetic progressions with difference and number of progressions equal to product of base elements. By crossing out arithmetic progressions with first terms which are multiples of base elements, we obtain a symmetric sparse matrix that contains all the prime numbers of subsequence of natural numbers, except for the base ones, which increases the density of prime numbers in sparse matrices. Sparse matrices are not formed clearly, only the vector of first terms of arithmetic progressions is formed. Properties of sparse matrices have been proven. Formulas that speed up the calculation of compound numbers in arithmetic progressions have been derived, the structures of vector elements of first terms of arithmetic progressions have been determined, the connectivity of symmetric parts of sparse matrices has been investigated. With the expansion of the base the number of pairs of elements with the difference equal to the power of two («twins», «fours», etc.) increases in the vector of first terms. This is a necessary condition for the existence of constants for which linear equations of two variables can have an infinite set of solutions in prime numbers. The irregularity of distribution of prime numbers in subsequences of natural numbers is related to the structure of elements of the vector of first terms. An algorithm for finding prime numbers on segments of large dimensions with a parallel calculation process has been built. The proposed algorithm is binary to algorithms for sifting subsequences of natural numbers by prime divisors. In these algorithms, it is not possible to parallelize the calculation process, since screening procedure requires storing the numerical information from the preceding steps (vector model of array processing). The binary algorithm calculates compound numbers in each pair of arithmetic progressions with symmetric first terms simultaneously, using only vector of the first terms of arithmetic progressions, which makes possible processing of large-dimensional arrays. Запропоновано матричну модель підпослідовності натуральних чисел з мультиплікативним базисом з перших простих чисел. Матрична модель – квадратна матриця, вектор-стовпці якої є арифметичними прогресіями з різницею і кількістю прогресій, що дорівнює добутку елементів базису. Викресливши арифметичні прогресії з першими членами, кратними елементам базису, дістанемо симетричну розріджену матрицю, яка містить усі прості числа підпослідовності натуральних чисел, крім базисних, що підвищує щільність простих чисел у розріджених матрицях. Розріджені матриці явно не формуються. Формується лише вектор перших членів арифметичних прогресій. Доведені властивості розріджених матриць, виведені формули, що прискорюють обчислення складених чисел в арифметичних прогресіях, визначена структура елементів вектора перших членів арифметичних прогресій, досліджена зв’язність симетричних частин розріджених матриць. З розширенням базису зростає у векторі перших членів кількість пар елементів з різницею, що дорівнює степеню двійки («близнята», «четвірки» тощо). Це є необхідною умовою існування констант, для яких лінійні рівняння двох змінних можуть мати нескінченну множину розв’язків у простих числах. Іррегулярність розподілу простих чисел у підпослідовностях натуральних чисел пов’язана з структурою елементів вектора перших членів. Побудовано алгоритм пошуку простих чисел на відрізках великих розмірностей з паралельним процесом обчислень. Запропонований алгоритм є двоїстим до алгоритмів просіювання підпослідовностей натуральних чисел за простими дільниками. У цих алгоритмах не можна розпаралелити процес обчислень, оскільки процедура просіювання вимагає зберігання числової інформації попередніх кроків (векторна модель обробки масивів). Двоїстий алгоритм паралельно обчислює складені числа в кожній парі арифметичних прогресій з симетричними першими членами, використовуючи лише вектор перших членів арифметичних прогресій, що дозволяє обробляти масиви великих розмірностей. Кам'янець-Подільський національний університет імені Івана Огієнка 2024-06-26 Article Article Рецензована Стаття application/pdf http://mcm-math.kpnu.edu.ua/article/view/313241 10.32626/2308-5878.2024-25.6-19 Mathematical and computer modelling. Series: Physical and mathematical sciences; 2024: Mathematical and computer modelling. Series: Physical and mathematical sciences. Issue 25; 6-19 Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки; 2024: Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки. Випуск 25; 6-19 2308-5878 10.32626/2308-5878.2024-25 uk http://mcm-math.kpnu.edu.ua/article/view/313241/304251 |
| spellingShingle | Абрамчук, Василь Абрамчук, Ігор Binary Algorithm for Finding Prime Numbers on Segments of Large Dimensions |
| title | Binary Algorithm for Finding Prime Numbers on Segments of Large Dimensions |
| title_alt | Двоїстий алгоритм пошуку простих чисел на відрізках великих розмірностей |
| title_full | Binary Algorithm for Finding Prime Numbers on Segments of Large Dimensions |
| title_fullStr | Binary Algorithm for Finding Prime Numbers on Segments of Large Dimensions |
| title_full_unstemmed | Binary Algorithm for Finding Prime Numbers on Segments of Large Dimensions |
| title_short | Binary Algorithm for Finding Prime Numbers on Segments of Large Dimensions |
| title_sort | binary algorithm for finding prime numbers on segments of large dimensions |
| url | http://mcm-math.kpnu.edu.ua/article/view/313241 |
| work_keys_str_mv | AT abramčukvasilʹ binaryalgorithmforfindingprimenumbersonsegmentsoflargedimensions AT abramčukígor binaryalgorithmforfindingprimenumbersonsegmentsoflargedimensions AT abramčukvasilʹ dvoístijalgoritmpošukuprostihčiselnavídrízkahvelikihrozmírnostej AT abramčukígor dvoístijalgoritmpošukuprostihčiselnavídrízkahvelikihrozmírnostej |