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

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

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

Определение

Натуральное число называется 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\le 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)