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

В теории чисел гладким числом называется целое число, все простые делители которого малы.

Гладкие числа особенно важны в алгоритмах факторизации.

Определение

Натуральное число называется B-гладким, если все его простые делители не превосходят B.

Пример

Число 2000 имеет следующее разложение на множители 2⁴ × 5³. Поэтому 2000 — это 5-гладкое число, а также 6-гладкое число и т. д., но не 4-гладкое.

Распределение

Пусть $\scriptstyle \Psi (x,y)$ обозначает количество y-гладких целых чисел не превосходящих x.

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

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

Иным образом, определим u как u = log x / log y: то есть, x = y^u. Тогда,

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

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

Ссылки

• 5-гладкие числа: A051037 (2ⁱ3^j5^k)