Гладке число

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

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

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

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

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

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

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

Число 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