smooth number

A $k$-smooth number $n$ is an integer such that its prime divisors are less than $k$. For example, 14824161510814728 is 7-smooth since its prime factors are just 2 and 3 (and thus its divisors are all either powers of those two primes or multiples of 6).

For small $k$, the number of smooth numbers less than a given $x$ can be estimated with the formula

$$\frac{1}{\pi (k)!}\prod _{i=1}^{\pi (k)}\frac{\log x}{\log p_i},$$

where $\pi (x)$ is the prime counting function and $p_i$ is the $i$th prime.

Smooth numbers have many applications, such as the many classic factorization algorithms which specifically call for smooth numbers in their initialization steps, as well as fast Fourier transform algorithms that also require smooth numbers.

Title	smooth number
Canonical name	SmoothNumber
Date of creation	2013-03-22 13:20:25
Last modified on	2013-03-22 13:20:25
Owner	CompositeFan (12809)
Last modified by	CompositeFan (12809)
Numerical id	5
Author	CompositeFan (12809)
Entry type	Definition
Classification	msc 11A05
Related topic	RoughNumber