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

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

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

Определение

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

Пример

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

Распределение

Пусть [math]\displaystyle{ \Psi(x,y) }[/math] обозначает количество y-гладких целых чисел, не превосходящих x.

Если граница гладкости B фиксирована и мала, верна следующая оценка для [math]\displaystyle{ \Psi(x,B) }[/math]:

[math]\displaystyle{ \Psi(x,B) \sim \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log x}{\log p}. }[/math]

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

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

где [math]\displaystyle{ \rho(u) }[/math] — функция Дикмана.

Ссылки

• 3-гладкие числа: A003586 (2ⁱ3^j)
• 5-гладкие числа: A051037 (2ⁱ3^j5^k)
• 7-гладкие числа: A002473 (2ⁱ3^j5^k7^l)
• 11-гладкие числа: A051038 (etc…)
• 13-гладкие числа: A080197
• 17-гладкие числа: A080681
• 19-гладкие числа: A080682
• 23-гладкие числа: A080683