Меню Главная Случайная статья Настройки Гладкое число Материал из https://ru.wikipedia.org Гладкое число — целое число, все простые делители которого не превышают заданного (малого числа) ${\displaystyle B}$ (например, при ${\displaystyle B=7}$ говорят о 7-гладких числах). Гладкие числа особенно важны в алгоритмах факторизации. Например, число 2000 имеет следующее разложение на множители: 24  53, поэтому оно 5-гладкое, но не 3-гладкое. Если граница гладкости ${\displaystyle B}$ фиксирована и достаточно мала, то верна следующая оценка для ${\displaystyle \Psi (x,B)}$ — количества ${\displaystyle B}$-гладких чисел, не превосходящих ${\displaystyle x}$: ${\displaystyle \Psi (x,B)\sim {\frac {1}{\pi (B)!}}\prod _{p\leqslant B}{\frac {\log x}{\log p}}.}$ С введением ${\displaystyle u=\log x/\log B}$ (то есть ${\displaystyle x=B^{u}}$) имеет место: ${\displaystyle \Psi (x,B)=x\cdot \rho (u)+O\left({\frac {x}{\log B}}\right)}$, где ${\displaystyle \rho }$ — функция Дикмана. Литература A. Granville. Smooth numbers: Computational number theory and beyond // Proc. of MSRI workshop. — 2008. Ссылки 3-гладкие числа: последовательность A003586 в OEIS (2i3j) 5-гладкие числа: последовательность A051037 в OEIS (2i3j5k) 7-гладкие числа: последовательность A002473 в OEIS (2i3j5k7l) 11-гладкие числа: последовательность A051038 в OEIS 13-гладкие числа: последовательность A080197 в OEIS 17-гладкие числа: последовательность A080681 в OEIS 19-гладкие числа: последовательность A080682 в OEIS 23-гладкие числа: последовательность A080683 в OEIS