Предположим, вы выбираете 100-значное число случайным образом. Как вы думаете, сколько различных простых множителей оно должно иметь?
Ответ меньше, чем вы могли подумать: скорее всего, от 5 до 6.
Функция ω(n) возвращает количество различных простых множителей числа n. Теорема Харди-Рамануджана гласит, что по мере того, как n стремится к бесконечности, среднее значение ω (n) для натуральных чисел с точностью до n равно log log n.
Поскольку log log 10^100 = 5,43 ..., мы ожидаем, что 100-значные числа будут иметь от 5 до 6 различных множителей.
Приведенный выше расчет дает среднее количество различных простых множителей для всех чисел, содержащих до 100 цифр. Но если бы мы переделали вычисление, рассматривая числа от 10^99 до 10^100, разница была бы только в третьем знаке после запятой.
Давайте рассмотрим гораздо меньший пример, где мы можем подсчитать значения ω (n) для чисел от 2 до 1 000 000.
- Большинство чисел, состоящих до шести цифр, имеют два или три различных простых множителя, что согласуется с log log 106 ≈ 2.6.
- Существует 2285 шестизначных чисел, которые имеют шесть различных простых множителей. Поскольку это одно из миллиона чисел, оно соответствует едва заметной полоске на графике выше.
- Существует 8 шестизначных чисел с 7 различными простыми множителями и ни одно с большим количеством множителей.
Теорема Харди-Рамануджана установила среднее значение ω (n) для больших чисел. Теорема Эрдеша–Каца идет дальше и грубо утверждает, что ω (n) обычно распределяется со средним значением и логарифмом дисперсии n. Подробнее об этом здесь.
Иначе говоря, возвращаясь к нашему примеру со 100-значными числами, теорема Харди-Рамануджана подразумевает, что эти числа будут иметь в среднем от 5 до 6 простых множителей, а теорема Эрдеша–Каца подразумевает, что около 95% таких чисел имеют 10 или менее различных простых множителей. Максимальное количество различных простых множителей для таких чисел равно 54.