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

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

Например, число 2000 имеет следующее разложение на множители: 2⁴ × 5³, поэтому оно 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 (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