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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Определение[править | править исходный текст]

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

Пример[править | править исходный текст]

Число 2000 имеет следующее разложение на множители 24 × 53. Поэтому 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 = yu. Тогда,

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

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

Ссылки[править | править исходный текст]

  • 5-гладкие числа: A051037 (2i3j5k)