Гладке число

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

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

Визначення

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

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

Приклад

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

Розподіл

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

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

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

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

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

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

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

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

Далі, $m$ називається $B$-степенево-гладким (Шаблон:Lang-en), якщо всі прості степені $p_i^{n_i}$, що ділять $m$:

$p_i^{n_i}\le B.$

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

Посилання

• Шаблон:Mathworld Шаблон:Ref-en

Енциклопедія послідовностей цілих чисел (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