Долго размышляя над созданием эффективного алгоритма факторизации чисел, я наткнулся на довольно интересную проблему - проблему оценки вероятности существования делителя на конкретном промежутке для произвольного натурального числа. Разрешение данного вопроса, на мой взгляд, способно продвинуть создание вероятностного алгоритма разложения числа на простые множители.
Формулировка
Пусть у нас есть произвольное число из множества натуральных чисел, тогда с какой вероятностью p(x) у числа есть делитель на отрезке от 2 до f(x)? Стоит заметить, что для данной задачи работает формула включений-исключений:
где p - это простое число, а его индекс - это порядковый номер, так, например, p1 = 2, а p2 = 3 и так далее, а n - количество простых чисел от 2до f(x).
Пример
Для большего понимания рассмотрим частный случай при f(x) = 3:
Представим себе множество натуральных чисел выберем из множество всех чисел, которые делятся на 2. Вероятность того произвольное число делится на 2 равна 1/2. Аналогично и числами, которые делятся на три. Однако неверно будет полагать, что p(x) = 1/2+1/3, так как и в множество кратных 2 входят некоторые числа кратные 3, и в множество кратных 3 входят некоторые числа кратные 2. Тогда, чтобы получить вероятность того, что произвольное натуральное число кратно 2 или 3, нужно будет сложить эти вероятности и вычесть их пересечение, то есть всё как с множествами:
Несмотря на то, что общая формула p(x) является верной, высчитывать эту вероятность - достаточно трудоёмкая задача, так как предварительно необходимо иметь список простых чисел от 2 до f(x).
Следовательно, для удобства подсчёта вероятности и для практической пользы неплохо было бы иметь какую-то оценку снизу, которая не будет требовать поиска всего множества простых чисел.
Оценка
Для начала по другому распишем ранее полученную формулу:
Распишем ряд Тейлора экспоненты в нуле:
Тогда можем заключить следующее:
Теперь используем улучшенный результат Эйлера оценки ряда обратных простых чисел:
В итоге получается следующая оценка:
На графике это выглядит следующим образом:
Стоит заметить, что на больших значениях разность между оценкой и реальным значением вероятности - бесконечно мала.
Заключение
Таким образом, оценка приведённая выше является корректной и позволяет свободно, не затрачивая большие вычислительные ресурсы, изучать свойства целых чисел, а также полученные результаты можно использовать вместе или при создании рандомизированных алгоритмов для факторизации.
Впоследствии на основании этих результатов мною планируется изучить вопрос: с какой вероятностью для конкретного числа x найдётся делитель от 2 до f(x), то есть значение функции будет напрямую зависеть от выбранного числа.
Читайте также
- Отзыв на книгу М. Лонэ «Большой роман о математике»
- Тезисы о математических началах человека
#математика #теориячисел #ряды #доказательства #алгоритмы
