Гладке число

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Визначення[ред.ред. код]

Натуральне число називається 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-гладке.

Розподіл[ред.ред. код]

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

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

 \Psi(x,B) \sim  \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log x}{\log p}.

де \scriptstyle{\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)

де \scriptstyle\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-степенево-гладке.

Посилання[ред.ред. код]

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

  • 2-гладкі числа: A000079 (2i)
  • 3-гладкі числа: A003586 (2i3j)
  • 5-гладкі числа: A051037 (2i3j5k)
  • 7-гладкі числа: A002473 (2i3j5k7l)
  • 11-гладкі числа: A051038 (і т.д. ...)
  • 13-гладкі числа: A080197
  • 17-гладкі числа: A080681
  • 19-гладкі числа: A080682
  • 23-гладкі числа: A080683