Гладкое число

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории чисел гладким числом называется целое число, все простые делители которого малы. Поскольку понятие «делители малы» может быть истрактовано вольно, чаще всего гладким числом называют такое, чьи простые делители не превосходят 10 (то есть, по сути равны 2,3,5 или 7).

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

Определение[править | править вики-текст]

Натуральное число называется B-гладким, если все его простые делители не превосходят B.

Пример[править | править вики-текст]

Число 2000 имеет следующее разложение на множители 24 × 53. Поэтому 2000 — это 5-гладкое число, а также 6-гладкое число и т. д., но не 4-гладкое.

Распределение[править | править вики-текст]

Пусть обозначает количество y-гладких целых чисел не превосходящих x.

Если граница гладкости B фиксирована и мала, верна следующая оценка для :

Иным образом, определим u как u = log x / log y: то есть, x = yu. Тогда,

где  — функция Дикмана.

Ссылки[править | править вики-текст]

  • 5-гладкие числа: A051037 (2i3j5k)