Гладке число

У теорії чисел B-гладким числом (англ. smooth number) називається число, всі прості дільники якого не перевищують B.

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

Визначення

Натуральне число називається $B$-гладким (або гладким щодо межі $B$), якщо всі його прості дільники не більші від $B$.

$B$ не обов'язково має бути простим дільником такого числа. Якщо найбільшим дільником числа є $p$, тоді число $B$-гладке для будь-якого $B\geq p.$ Зазвичай $B$ подається як просте, але складене число спрацьовує так само добре. Число є $B$-гладке тоді і тільки тоді, коли воно є $p$-гладким, де $p$ є найбільшим простим дільником меншим або рівним $B$.

Приклад

Число 1620 розкладається на множники так: $2^{2}\times 3^{4}\times 5.$ Отже це число 5-гладке, а також 6-гладке, 7-гладке і так далі, але не 4-гладке.

Розподіл

Нехай $\Psi (x,y)$ позначають число $y$-гладких цілих менших або рівних $x$ (функція де Брюїна, англ. de Bruijn).

Якщо межа гладкості $B$ зафіксована і мала, існує хороша оцінка для $\Psi (x,B)$:

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

де $\pi (B)$ позначає кількість простих чисел менших або рівних до $B$.

Інакше, визначимо параметр $u$ як $u={\frac {\log x}{\log y}}$: так що $x=y^{u}.$ Тоді,

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

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

Степенево-гладкі числа

Далі, $m$ називається $B$-степенево-гладким (англ. powersmooth), якщо всі прості степені $\scriptstyle p_{i}^{n_{i}}$, що ділять $m$:

$p_{i}^{n_{i}}\leq B.\,$

Наприклад, $2^{4}\times 3^{2}\times 5$ є 5-гладким, але не 5-степенево-гладким. Воно 16-степенево-гладке, бо $2^{4}=16$ і також 17-, 18-степенево-гладке.

Посилання

• Weisstein, Eric W. Гладкі числа(англ.) на сайті Wolfram MathWorld. (англ.)

Енциклопедія послідовностей цілих чисел (OEIS) списки $B$-гладких чисел для малих $B$:

• 2-гладкі числа: A000079 (2ⁱ)
• 3-гладкі числа: A003586 (2ⁱ3^j)
• 5-гладкі числа: A051037 (2ⁱ3^j5^k)
• 7-гладкі числа: A002473 (2ⁱ3^j5^k7^l)
• 11-гладкі числа: A051038 (і т.д. ...)
• 13-гладкі числа: A080197
• 17-гладкі числа: A080681
• 19-гладкі числа: A080682
• 23-гладкі числа: A080683