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

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

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

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

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

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

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

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

Литература

• Шаблон:Статья

Ссылки

• 3-гладкие числа: Шаблон:OEIS (2ⁱ3^j)
• 5-гладкие числа: Шаблон:OEIS (2ⁱ3^j5^k)
• 7-гладкие числа: Шаблон:OEIS (2ⁱ3^j5^k7^l)
• 11-гладкие числа: Шаблон:OEIS
• 13-гладкие числа: Шаблон:OEIS
• 17-гладкие числа: Шаблон:OEIS
• 19-гладкие числа: Шаблон:OEIS
• 23-гладкие числа: Шаблон:OEIS