Гладкое число

Гладкое число — целое число, все простые делители которого не превышают заданного (малого числа) $B$ (например, при $B=7$ говорят о 7-гладких числах). Гладкие числа особенно важны в алгоритмах факторизации.

Например, число 2000 имеет следующее разложение на множители: 2⁴ × 5³, поэтому оно 5-гладкое, но не 3-гладкое.

Если граница гладкости $B$ фиксирована и достаточно мала, то верна следующая оценка для $\Psi (x,B)$ — количества $B$-гладких чисел, не превосходящих $x$:

$\Psi (x,B)\sim {\frac {1}{\pi (B)!}}\prod _{p\leqslant B}{\frac {\log x}{\log p}}.$

С введением $u=\log x/\log B$ (то есть $x=B^{u}$) имеет место:

$\Psi (x,B)=x\cdot \rho (u)+O\left({\frac {x}{\log B}}\right)$,

где $\rho$ — функция Дикмана.

Литература

• A. Granville. Smooth numbers: Computational number theory and beyond // Proc. of MSRI workshop. — 2008.

Ссылки

• 3-гладкие числа: последовательность A003586 в OEIS (2ⁱ3^j)
• 5-гладкие числа: последовательность A051037 в OEIS (2ⁱ3^j5^k)
• 7-гладкие числа: последовательность A002473 в OEIS (2ⁱ3^j5^k7^l)
• 11-гладкие числа: последовательность A051038 в OEIS
• 13-гладкие числа: последовательность A080197 в OEIS
• 17-гладкие числа: последовательность A080681 в OEIS
• 19-гладкие числа: последовательность A080682 в OEIS
• 23-гладкие числа: последовательность A080683 в OEIS