Разделы: Математика
Размещена 15.06.2025.
Просмотров - 298

Простое число

Дудин Александр Тимофеевич

нет

не работаю

пенсионер

УДК 511

Введение. Что такое простое число? Это такое число, которое делиться на единицу и само себя. Других делителей у него нет. Среди чётных чисел нет простых чисел за исключением числа 2. Поэтому поиск простых чисел ведётся среди нечётных чисел. Простые числа по числовой оси располагаются не равномерно. Простых чисел бесконечное множество. У древнеегипетских математиков были некоторые представления о простых числах, о чём нам известно из папируса Райнда и других источников [3]. Это второе тысячелетие до нашей эры.

Самые ранние свидетельства об изучении простых чисел дошли к нам от математиков Древней Греции (500 – 300 лет до н.э.)[1].

В книге «Начал» Эвклид доказал, что простых чисел бесконечное множество.

Так же он доказал, что любое целое число можно представить произведением простых чисел.

Древне Греческий математик Эратосфен (200 лет до н.э) для поиска простых чисел  придумал алгоритм , который получил название «Решето Эратосфена».

Следующие известные открытия в теории простых чисел были сделаны в 17 веке, так например: математик Ферма (родился 17 августа 1601 г., умер 12 января 1665 г.)  в письме  Марен Марсенну высказал гипотезу, что числа 2^n + 1 всегда будут простыми.

Через 100 лет Эйлер опроверг эту гипотезу, он показал, что: 2^31 +1 = 4294967297 делиться на 641 и не является простым числом.

Марен Марсенн активно занимался простыми числами вида: 2^n – 1, где n –простое число.

Оказалось, что не все числа Марсенна являются простыми числами, например:

2^11 – 1 = 2047 = 23 * 89.

В дальнейшем алгоритм и числа Марсенна оказались наиболее востребованными в поиске простых чисел.

Количество простых чисел Марсенна к 2005 г. найдено 42 числа, из них наибольшее:

2^ 25964951, число состоит из 7816230 цифр.

Наибольшее простое известное число: 2^ 136 279 841  - 1 [9].

При написании статьи опирался на следующие источники: [1]; [2]; [3]; [4]; [5]; [6]; [7]; [8]; [9]; [10].

Цель этой работы, найти алгоритм для поиска простых чисел.

Актуальность этой работы обусловлена тем, что поиск простых чисел продолжается, и каждое новое найденное простое число, это событие, которое регистрируется. И это событие свидетельствует о развитии вычислительной техники и программирования.

Научная новизна этой работы обусловлена тем, что найден новый алгоритм для поиска простых чисел, а это есть новый математический инструмент.

С помощью нового алгоритма можно предположить новое наибольшее простое число.

Математик Голфри Харольд Харди утверждал, что простые числа не имеют реального применения, а сегодня без них невозможно использование интернета [2].

Поиск простых чисел возможен с применением специальных алгоритмов.

Наиболее применяемые и известные алгоритмы, приведём ниже.

Числа вида: 2^n – 1 – числа Марсенна, где n – натуральное число, число Марсенна может быть простым, только если n – простое число.

Число вида: 2^2^n +1 – числа Ферма, где n – положительное целое число. На февраль 2015 г. известно только 5 чисел Ферма для n = 0, 1, 2, 3, 4.

Число вида: n*2^n – 1 – числа Вудала.

Число вида: n*2^n + 1 – числа Каллена.

Число вида: k*2^n + 1 – числа Прота, k – нечётное и 2^n > k

Прежде чем переходить к составлению алгоритмов для поиска простых чисел, проанализируем количество простых чисел на интервалах каждой сотни в источнике [5].

Интервал от 2 до 100 содержит 25 простых чисел. Простые числа находятся только среди нечётных чисел, то получается, что их в первой сотне более 50 %.

В интервале от 100 до 200 простых чисел 21.

В интервале от 200 до 300 простых чисел 18.

В интервале от 300 до 400 простых чисел 16.

В интервале от 400 до 500 простых чисел 17.

В интервале от 500 до 600 простых чисел 14.

В интервале от 600 до 700 простых чисел 16.

В интервале от 700 до 800 простых чисел 14.

В интервале от 800 до 900 простых чисел 15.

В интервале от 900 до 1000 простых чисел 14.

В интервале от 1000 до 1100 простых чисел 16.

В интервале от 1100 до 1200 простых чисел 12.

В интервале от 1200 до 1300 простых чисел 15.

В интервале от 1300 до 1400 простых чисел 11.

В интервале от 1400 до 1500 простых чисел 17.

В интервале от 1500 до 1600 простых чисел 12.

В интервале от 1600 до 1700 простых чисел 15.

В интервале от 1700 до 1800 простых чисел 12.

В интервале от 1800 до 1900 простых чисел 12.

В интервале от 1900 до 2000 простых чисел 13.

В интервале от 2 до 3571 простых чисел 500.

На интервале от 2 до 3571 из 1785 нечётных чисел всего 500 простых чисел, это 28,01 %.

Как видим, создание любого алгоритма приводит только к случайному попаданию на простые числа. Проверка алгоритма в начале числовой оси не даёт гарантии, что можно  попасть на простое число. Но если алгоритм настроен на поиск простых чисел среди нечётных чисел и мы попали на составное число, то появляется шанс измерить интервал между простыми числами. Известные наибольшие интервалы между простыми числами по источнику [6].

Наибольший интервал между простыми числами в первых 10 тысячах 36 чисел (9551 -9587).  

Наибольший найденный интервал на 2022 г. между 208095 – значащими цифрами, определёнными, как вероятно простыми, имеет длину 1113196 [6].

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

Наибольшее простое известное число: 2^ 136 279 841  - 1 [9]. 

В этой работе назовём вероятное наибольшее просто число, которое равно:

(2^ 136 279 841  - 1)^4 + (2^ 136 279 841)^4 

Можно записать: (2^ 136 279 841  - 1)^4 + 2^545119364 

Для предположения о вероятном наибольшем простом числе есть основания, получен новый алгоритм и проверен на поиск простых чисел.  Известен «Список самых больших известных простых чисел и вероятных простых чисел» [10].

В данном случае используем наибольшее простое число 2^ 136 279 841  - 1 и рядом стоящее чётное число 2^ 136 279 841, возводим то и другое число в четвёртую степень и складываем результаты, получаем вероятное простое число.

Методы и алгоритмы получения простых чисел.

В квадратных скобочках [] указан источник и метод определения простых чисел, в источнике [5], поиск в таблице, в источнике [11], калькулятор поиска простых чисел. 

3^4 +4^4 = 337[5].

81 + 256 = 337

Алгоритм:

N – Простое число

N + 1 – рядом стоящее чётное число.

N^4 + (N + 1)^4 = С

С – вероятное простое число.

На первый взгляд предложен одноразовый алгоритм, предназначенный для поиска наибольшего вероятного простого числа. Если бы это было так, то и в этом нет, не чего плохого. Дальнейшее развитие таких алгоритмов будет показано ниже.

4^4 + 5^4 = 881[5].

256 + 625 = 881

Алгоритм:

N – Простое число

N – 1 – рядом стоящее чётное число.

(N – 1)^4 + N^4 = С

С – вероятное простое число.

Есть новый алгоритм, следовательно, его можно применить на поиск нового вероятного простого числа.

Используем тоже наибольшее простое число 2^ 136 279 841  - 1 и рядом стоящее чётное число 2^ 136 279 841 - 2, в первом случае чётное число рядом с простым было на 1 больше, а в этом случае чётное число рядом с простым числом на единицу меньше. Возводим то и другое число в четвёртую степень и складываем результаты, получаем вероятное простое число.

Вероятное наибольшее простое число будет:

(2^ 136 279 841  - 1)^4 + (2^ 136 279 841 – 2)^4

Рассмотрим, как можно использовать вышеприведённые алгоритмы:

3^4 +4^4 = 337[5].

81 + 256 = 337

Алгоритм:

N – Простое число

N + 1 – рядом стоящее чётное число.

N^4 + (N + 1)^4 = С

С – вероятное простое число.

С помощью этого алгоритма делаем второй шаг:

Полученное число 337 возводим в 4 степень и рядом стоящее чётное число (337 + 1) возводим в четвёртую степень. Результаты складываем, получаем С(1).

337^4 + 338^4 = 12897917761 + 13051691536 = 25949609297 – это число является простым. Проверено с помощью калькулятора простых чисел[11].

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

С(1)^4 + (C(1) + 1)^4 = C(2) следующий шаг

С(2)^4 + (C(2) + 1)^4 = C(3) и т.д.
 

Заключение. В этой работе найден новый алгоритм для поиска простых чисел. Приведённый алгоритм проверен на работоспособность на известных простых числах.

Выводы. Найден работоспособный алгоритм для поиска простых чисел. Работоспособность алгоритма проверена на известных простых числах. С помощью вновь найденного алгоритма найдено вероятное наибольшее число:

(2^ 136 279 841  - 1)^4 + 2^545119364

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/teoriya-prostyh-chisel-ot-istokov-do-sovremennosti (Дата обращения 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_largest_known_primes_and_probable_primes (Дата обращения 06.06.2025 г.)
11. Является ли число простым [электронный ресурс] https://www.calc.ru/yavlyayetsya-li-chislo-prostym.html (Дата обращения 11.06.2025 г.)

Комментарии пользователей:

15.06.2025, 21:54 Харт Алекс Отзыв: Усов вспомнил, что он «рецензент», а Дудин написал очередную «математическую» работу. Александр Тимофеевич, Ваши работы как научные очень слабы, и я не сразу понял Ваше амплуа, когда критиковал Вас. Ваше амплуа в стиле юмористических рассказов очень артистично и гениально. Я с радостью ознакомился с Вашей новой юмористической работой, которую Вы написали в Блокноте. Браво, Александр Тимофеевич. Мне очень понравилось. Несомненно рекомендую ее к печати в разделе «Научный юмор». Буду ждать Ваших новых работ в этом стиле.

17.06.2025, 21:30 Цорин Борис Иосифович Отзыв: Автор, видимо, путает "вероятно простое число" с "числом, имеющим ненулевую вероятность оказаться простым". Предложенный г-ном Дудиным "алгоритм" дает гарантированно нечетные числа, - ну что ж, это победа, случайное нечетное число действительно имеет вероятность оказаться простым. Ну что ж, я могу алаверды предложить "алгоритм" с результативностью всего в пару раз хуже: random(int)*6+-1. P.S. Специально проверил: из первых 20 чисел, полученных по "алгоритму" г-на Дудина из нечетных простых чисел, простых оказалось 9. Из первых 20 чисел, полученных по тем же формулам из нечетных составных чисел, простых оказалось 10. P.P.S. В принципе, хотя г-ну Дудину это вряд ли под силу вывести, числа вида N^4+(N+1)^4 вне зависимости от N из простых чисел в пределах 100 могут делиться только на 17, 73, 89 и 97, что увеличивает шанс такого числа оказаться простым в 7,5 раза относительно абсолютно случайного целого и в 2,5 раза относительно случайных чисел вида 6k+-1. Но, увы г-ну Дудину, этого недостаточно, чтоб объявить такое число "вероятно простым".

17.06.2025, 22:04 Цорин Борис Иосифович Отзыв: P.P.P.S. А если вместо N+1 брать N+17, то делимость на 73 и 89 исключается сама, а для исключения делимости на 17 достаточно будет не брать N, делящиеся на 17. И тогда минимально возможным простым делителем будет 97. Толку от этого столько же, сколько от "статьи", то есть ноль, так что дарю идею.

Оставить комментарий