Часто в олимпиадных задачах, чтобы оценить асимптотику алгоритма, требуется знать примерное число делителей поступающего на вход числа. Точнее, требуется знать максимальное число делителей среди всех чисел до, скажем, миллиарда.
Самая грубая оценка - O (sqrt(N)), а именно, не более двух квадратных корней из N.
Но часто это оказывается слишком грубой оценкой, неоправданно завышенной.
Обычная используемая мной оценка - O(кубического корня из N). Эту таинственную оценку я услышал когда-то давно от кого-то, и никогда её не понимал, но пользовался ей, и она работала.
Совсем недавно мы делали стресс-тест, и на числах до миллиарда она подтвердилась - число делителей не превосходит двух кубических корней из числа. Этого "доказательства" вполне достаточно, чтобы и дальше применять эту оценку на практике. Но найти ей математическое объяснение ну никак не получалось.
Сегодня в очередной раз решил поискать на эту тему в интернете. На этот раз нашёл то. что нужно, на удивление быстро: en.wikipedia.org/wiki/Divisor_function. Здесь много всякого интересного, но вот главная вещь, поразительная для меня формула:
"для любого eps>0 выполняется: d(n) = o(n^eps)"
Выходит, на самом деле число делителей ведёт себя на бесконечности не только лучше квадратного, кубического и прочего корней из числа n; оно вообще является субполиномиальной величиной!
Другие оценки:
- Wigert: "d(n) ~ n ^ (log2 / log log n)" (ну я примерно передал порядок, на самом деле там формула посложнее)
- Дирихле: "СУММА_{i=1..n} d(i) / n ~ log n + 2 gamma - 1"
P.S. Некоторым это может показаться бояном, но я знаю, что многие до сих пор даже не знают, что число делителей меньше квадратного корня, не говоря уже о таких "крутых" оценках :)
P.P.S. Для олимпиад, где обычно в таких задачах мы имеем дело с числами до 10^9 - 10^12, эти оценки малополезны (здесь надо по-прежнему брать корень кубический), но они интересны чисто как математический факт.
Bad previous comment