Abstract: Finding prime numbers is a complex task, and it often happens that a found prime number is found earlier on the number line than some of the prime numbers that preceded it. No known formula or algorithm for finding prime numbers guarantees that they will be found in a strict order, without missing any of them. The search for prime numbers continues, and it is an important task because it is another step towards knowledge. This paper explores various formulas and algorithms for finding prime numbers.
Ключевые слова: поиск; простое число; формула; алгоритм; числа Ферма; числа Марсенна; числа Вудала; числа Каллена; числа Прота
Keywords: search; prime number; formula; algorithm; Fermat numbers; Mersenne numbers; Woodall numbers; Cullen numbers; Proth numbers
УДК 511
Введение. Простые числа ищут по формулам, которые в дальнейшем получили названия:
числа Ферма 2^2^n +1, где n – положительное целое число;
числа Марсенна 2^n – 1, где n – натуральное число, число Марсенна может быть простым, только если n – простое число;
числа Вудала n*2^n – 1;
числа Каллена n*2^n + 1;
числа Прота k*2^n + 1, где k – нечётное и 2^n > k
Как видим, формулы для поиска простых чисел очень похожи. Формула числа Вудала n*2^n – 1 и формула числа Каллена n*2^n + 1 отличаются в (-1) и (+1), а результаты поиска отличаются очень существенно.
Числа Вудала образуют последовательность: 7, 23, 383, 32212254719, …
Кристофер Хулей в 1976 году показал, что почти все числа Каллена составные [12];
[13].
Все известные простые числа Каллена соответствуют n, равному:
1, 141, 4713, 5795, 6611, 18496, 32292, …
Простых чисел Вудала и простых чисел Каллена бесконечное множество [12]; [13].
На 2025 г известно всего 5 простых чисел Ферма: 3, 5, 17, 257, 65537 [14].
Формула поиска чисел Марсенна оказалась наиболее эффективной и работоспособной. Начало последовательности простых чисел Марсенна: 3, 7, 31, 127, 8191, 131 071, 524 287, 2 147 483 647, 2 305 843 009 213 694 000, …
На 2024 г. известно 52 простых числа Марсенна [15].
Цель этой работы заключается в том, чтобы найти новые формулы, алгоритмы для поиска простых чисел.
Актуальность этой работы обусловлена тем, что предлагаются новые формулы для поиска простых чисел, которые ускорят процесс поиска простых чисел.
Научная новизна этой работы обусловлена тем, что предложены новые формулы и способы для поиска простых чисел, работоспособность которых проверена на начальных простых числах числовой оси. А это новые высоты в криптографии и шифровании.
Простые числа по числовой оси размещены не равномерно, каждая формула, алгоритм на определённых интервалах будет показывать простые числа, на следующих интервалах их не находить, и так продвигаясь по числовой оси, на определённых интервалах, будем находить простые числа.
Числа Ферма 2^2^n +1, где n – положительное целое число
Чисел Ферма будет значительно больше, если мы изменим формулу поиска:
(2^2^n + 1) + (3*2^n +2), где n – положительное целое число
(2^2^1 + 1) + (3*2^1 + 2) = 5+8 = 13 – простое число
(2^2^2 + 1) + (3*2^2 + 2) = 17+14 = 31– простое число
(2^2^3 + 1) + (3*2^3 + 2) = 257 + 26 = 283 – простое число
(2^2^4 + 1) + (3*2^4 + 2) = 65537 + 50 = 65587 – простое число
Чисел Ферма: 3, 5, 17, 257, 65537.
Найденные простые числа по вновь предложенной формуле: 13, 31, 283, 65587…
Среди чисел Ферма нет вновь найденных простых чисел, формула рабочая и результативная.
Начало последовательности простых чисел Марсенна: 3, 7, 31, 127, 8191, 131 071, 524 287, 2 147 483 647, 2 305 843 009 213 694 000, …
числа Марсенна 2^n – 1, где n – натуральное число, число Марсенна может быть простым, только если n – простое число;
2^n – 1
Изменяем формулу, то есть создаём новую формулу:
3(2^n – 1) + 2^n, где n – натуральное число.
3(2^1 – 1) + 2^1 = 3 + 2 = 5 - простое число
3(2^2 – 1) + 2^2 = 9 + 4 =13 - простое число
3(2^3 – 1) + 2^3 = 21 + 8 = 29 - простое число
3(2^4 – 1) + 2^4 = 45 +16 = 61 - простое число
3(2^7 – 1) + 2^7 = 381 +128 = 509 - простое число
3(2^8 – 1) + 2^8 = 765 +256 = 1021 - простое число
3(2^10 – 1) + 2^10 = 3069+1024 = 4093 - простое число
3(2^12 – 1) + 2^12 = 3*4095 +4096 = 16381 - простое число
3(2^18 – 1) + 2^18 = 3* 262143 + 262144= 1048573 - простое число
3(2^20 – 1) + 2^20 = 3* 1048575 + 1048576 = 4194301 - простое число
3(2^22 – 1) + 2^22 = 3*4194303 + 4194304 = 16777213 - простое число
Начало последовательности простых чисел Марсенна: 3, 7, 31, 127, 8191, 131 071, 524 287, 2 147 483 647, 2 305 843 009 213 694 000, …
Найденные простые числа по новой формуле:
5;13;29;61;509;1021;4093;16381;1048573;40194301; 16777213….
В новой найденной последовательности в начале числовой оси среди найденных 11 простых чисел, нет не одного простого числа найденного по формуле поиска простых чисел Марсенна.
Числа Вудала образуют последовательность: 7, 23, 383, 32212254719, …
числа Вудала n*2^n – 1;
Предлагаются новая формула для поиска простых чисел:
(n*2^n – 1) + 2^n
Принимаем: n = 1; n = 2; n = 3… и т. д.:
(1*2^1 – 1) + 2^1 = 3 – простое число.
n = 2
(2*2^2 – 1) + 2^2 = 7+ 4 = 11 – простое число.
n = 3
(3*2^3 – 1) + 2^3 = 23 + 8 = 31 – простое число.
(4*2^4 – 1) + 2^4 = 63 +16 = 79 – простое число.
(5*2^5 – 1) + 2^5 = 159 + 32 = 191 – простое число.
(14*2^14 – 1) + 2^14 = 229375+16384 = 245759 – простое число.
(15*2^15 – 1) + 2^15 = 491519+32768 = 524287 – простое число.
Числа Вудала образуют последовательность: 7, 23, 383, 32212254719, …
Найденные числа по новой формуле:
3,11,31,79, 191, 245759, 524287…
Среди чисел Вудала, нет вновь найденных простых чисел, а это говорит о новых возможностях поиска простых чисел.
Все известные простые числа Каллена соответствуют n, равному:
1, 141, 4713, 5795, 6611, 18496, 32292, …
числа Каллена n*2^n + 1.
Предлагаются новая формула для поиска простых чисел:
(n*2^n + 1) + 2^n
Принимаем: n = 1; n = 2 и т.д.:
(1*2^1 + 1) + 2^1 = 3+2 = 5 – простое число.
n = 2
(2*2^2 + 1) + 2^2 = 9+ 4 = 13 – простое число.
(5*2^5 + 1) + 2^5 = 161 + 32 = 193 – простое число.
(6*2^6 + 1) + 2^6 = 385 + 64 = 449 – простое число.
(13*2^13 + 1) + 2^13 = 106497+8192 = 114689 – простое число.
Найденные простые числа по новой формуле: 5, 13, 193, 449, 114689…
Среди найденных простых чисел по новой формуле нет, не одного простого числа Каллена.
Числа Прота k*2^n + 1, где k – нечётное и 2^n > k
Предлагаются новая формула для поиска простых чисел:
(k*2^n + 1) + 2^n
k = 3; n = 2
(3*2^2 + 1) + 2^2 = 13+ 4 = 17 – простое число.
k = 3; n = 8
(3*2^8 + 1) + 2^8 = 775+ 258 = 1033 – простое число.
k = 5; n = 4
(5*2^4 + 1) + 2^4 = 81 +16 = 97 – простое число.
k = 5; n = 5
(5*2^5 + 1) + 2^5 = 161+ 32 = 193 – простое число.
k = 5; n = 7
(5*2^7 +1) + 2^7 = 641 + 128 = 769 – простое число.
k = 5; n = 8
(5*2^8 + 1) + 2^8 = 1291+ 258 = 1549 – простое число.
k = 7; n = 5
(7*2^5 + 1) + 2^5 = 225+ 32 = 257 – простое число.
Приведём простые числа Прота в начале числовой оси:
3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113…
Найденные простые числа по новой формуле:17, 97, 193, 257, 769, 1033, 1549…
Среди найденных простых чисел, в простых числах Прота нет чисел: 1033, 1549
Заключение. Все найденные новые формулы для поиска простых чисел рабочие и результативные. С помощью их найдены простые числа.
Выводы. Формулы, с изменённым интервалом поиска, на удалённых и малоисследованных интервалах числовой оси, могут оказаться очень результативными.
Библиографический список.
1. Простые числа: история и факты / Хабр [электронный ресурс] https://habr.com/ru/articles/276037/ (Дата обращения: 06.06.2025 г.)
2. Простые числа — все самое интересное на ПостНауке [электронный ресурс]
https://postnauka.org/longreads/155310 (Дата обращения: 06.06.2025 г.)
3. Простое число — Википедия [электронный ресурс] https://ru.wikipedia.org/wiki/Простое_число (Дата обращения: 06.06.2025 г.)
4. Prime number – Wikipedia [электронный ресурс] https://en.wikipedia.org/wiki/Prime_number: (Дата обращения 06.06.2025 г.)
5. Список простых чисел — Википедия [электронный ресурс]
https://ru.wikipedia.org/wiki/Список_простых_чисел (Дата обращения 06.06.2025 г.)
6. Интервалы между простыми числами — Википедия [электронный ресурс]
https://ru.wikipedia.org/wiki/Интервалы_между_простыми_числами (Дата обращения 06.06.2025 г.)
7. Теория простых чисел: от истоков до современности – тема научной статьи по математике читайте бесплатно текст научно-исследовательской работы в электронной библиотеке КиберЛенинка [электронный ресурс]
https://cyberleninka.ru/article/n/teori ... remennosti (Дата обращения 06.06.2025 г.)
8. Простые числа. Что о них известно сегодня? | Мир вокруг нас | ШколаЖизни.ру [электронный ресурс]
https://www.shkolazhizni.ru/world/articles/69538/ (Дата обращения 06.06.2025 г.)
9. Наибольшее известное простое число — Википедия [электронный ресурс]
https://ru.wikipedia.org/wiki/Наибольшее_известное_простое_число (Дата обращения 06.06.2025 г.)
10. List of largest known primes and probable primes – Wikipedia [электронный ресурс]
https://en.wikipedia.org/wiki/List_of_l ... ble_primes (Дата обращения 06.06.2025 г.)
11. является ли число простым [электронный ресурс]
https://www.calc.ru/yavlyayetsya-li-chislo-prostym.html (Дата обращения 11.06.2025 г.)
12. Число Вудала — Википедия [электронный ресурс]
https://ru.wikipedia.org/wiki/Число_Вудала (Дата обращения 12.07.2025 г.)
13.Числа Каллена — Википедия [электронный ресурс]
https://ru.wikipedia.org/wiki/Числа_Каллена (Дата обращения 12.07.2025 г.)
14. Число Ферма — Википедия [электронный ресурс]
https://ru.wikipedia.org/wiki/Число_Ферма (Дата обращения 12.07.2025 г.)
15. Число Мерсенна — Википедия [электронный ресурс]
https://ru.wikipedia.org/wiki/Число_Мерсенна (Дата обращения 01. 07. 2025 г.)
16. Число Прота — Википедия [электронный ресурс]
https://ru.wikipedia.org/wiki/Число_Прота (Дата обращения 12.07.2025 г.)
Добавлено спустя 22 дня 1 час 39 минут 24 секунды:
Допустил ошибку, надо правильно писать: Мерсенна.
2^8 = 256
Предлагаются новая формула для поиска простых чисел:
(k*2^n + 1) + 2^n
k = 3; n = 2
(3*2^2 + 1) + 2^2 = 13+ 4 = 17 – простое число.
k = 5; n = 4
(5*2^4 + 1) + 2^4 = 81 +16 = 97 – простое число.
k = 5; n = 5
(5*2^5 + 1) + 2^5 = 161+ 32 = 193 – простое число.
k = 5; n = 7
(5*2^7 +1) + 2^7 = 641 + 128 = 769 – простое число.
k = 7; n = 5
(7*2^5 + 1) + 2^5 = 225+ 32 = 257 – простое число.
Приведём простые числа Прота в начале числовой оси:
3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113…
Найденные простые числа по новой формуле:17, 97, 193, 257, 769…
Среди найденных простых чисел, в простых числах Прота, не найдено новых простых чисел.
С уважением А.Т. Дудин.
- Код ссылки на тему, для размещения на персональном сайте | Показать
