Гладке число

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

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

Визначення

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

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

Приклад

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

Розподіл

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

Якщо межа гладкості зафіксована і мала, існує хороша оцінка для :

де позначає кількість простих чисел менших або рівних до .

Інакше, визначимо параметр як : так що Тоді,

де функція Дікмана.

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

Далі, називається -степенево-гладким (англ. powersmooth), якщо всі прості степені , що ділять :

Наприклад, є 5-гладким, але не 5-степенево-гладким. Воно 16-степенево-гладке, бо і також 17-, 18-степенево-гладке.

Посилання

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

  • 2-гладкі числа: A000079 (2i)
  • 3-гладкі числа: A003586 (2i3j)
  • 5-гладкі числа: A051037 (2i3j5k)
  • 7-гладкі числа: A002473 (2i3j5k7l)
  • 11-гладкі числа: A051038 (і т.д. ...)
  • 13-гладкі числа: A080197
  • 17-гладкі числа: A080681
  • 19-гладкі числа: A080682
  • 23-гладкі числа: A080683
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.