Гладке число

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

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

Визначення

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

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

Приклад

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

Розподіл

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

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

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

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

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

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

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

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

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

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

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

Посилання

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

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

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