Smooth number

In

The 3-smooth numbers have also been called "harmonic numbers", although that name has other more widely used meanings.[4] 5-smooth numbers are also called

Here, note that B itself is not required to appear among the factors of a B-smooth number. If the largest prime factor of a number is p then the number is B-smooth for any B ≥ p. In many scenarios B is prime, but composite numbers are permitted as well. A number is B-smooth if and only if it is p-smooth, where p is the largest prime less than or equal to B.

Applications

An important practical application of smooth numbers is the

5-smooth or regular numbers play a special role in Babylonian mathematics.^[8] They are also important in music theory (see Limit (music)),^[9] and the problem of generating these numbers efficiently has been used as a test problem for functional programming.^[10]

Smooth numbers have a number of applications to cryptography.

Distribution

Let ${\displaystyle \Psi (x,y)}$ denote the number of y-smooth integers less than or equal to x (the de Bruijn function).

If the smoothness bound B is fixed and small, there is a good estimate for ${\displaystyle \Psi (x,B)}$:

${\displaystyle \Psi (x,B)\sim {\frac {1}{\pi (B)!}}\prod _{p\leq B}{\frac {\log x}{\log p}}.}$

where ${\displaystyle \pi (B)}$ denotes the number of primes less than or equal to ${\displaystyle B}$.

Otherwise, define the parameter u as u = log x / log y: that is, x = y^u. Then,

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

where ${\displaystyle \rho (u)}$ is the Dickman function.

For any k, almost all natural numbers will not be k-smooth.

If ${\displaystyle n=n_{1}n_{2}}$ where ${\displaystyle n_{1}}$ is ${\displaystyle B}$-smooth and ${\displaystyle n_{2}}$ is not (or is equal to 1), then ${\displaystyle n_{1}}$ is called the ${\displaystyle B}$-smooth part of ${\displaystyle n}$. The relative size of the ${\displaystyle x^{1/u}}$-smooth part of a random integer less than or equal to ${\displaystyle x}$ is known to decay much more slowly than ${\displaystyle \rho (u)}$.^[12]

Powersmooth numbers

Further, m is called n-powersmooth (or n-ultrafriable) if all prime powers ${\displaystyle p^{\nu }}$ dividing m satisfy:

${\displaystyle p^{\nu }\leq n.\,}$

For example, 720 (2⁴ × 3² × 5¹) is 5-smooth but not 5-powersmooth (because there are several prime powers greater than 5, e.g. ${\displaystyle 3^{2}=9\nleq 5}$ and ${\displaystyle 2^{4}=16\nleq 5}$). It is 16-powersmooth since its greatest prime factor power is 2⁴ = 16. The number is also 17-powersmooth, 18-powersmooth, etc.

Unlike n-smooth numbers, for any positive integer n there are only finitely many n-powersmooth numbers, in fact, the n-powersmooth numbers are exactly the positive divisors of “the least common multiple of 1, 2, 3, …, n” (sequence A003418 in the OEIS), e.g. the 9-powersmooth numbers (also the 10-powersmooth numbers) are exactly the positive divisors of 2520.

n-smooth and n-powersmooth numbers have applications in number theory, such as in

Moreover, m is said to be smooth over a set A if there exists a factorization of m where the factors are powers of elements in A. For example, since 12 = 4 × 3, 12 is smooth over the sets A₁ = {4, 3}, A₂ = {2, 3}, and ${\displaystyle \mathbb {Z} }$, however it would not be smooth over the set A₃ = {3, 5}, as 12 contains the factor 4 = 2², and neither 4 nor 2 are in A₃.

Note the set A does not have to be a set of prime factors, but it is typically a proper subset of the primes as seen in the factor base of Dixon's factorization method and the quadratic sieve. Likewise, it is what the general number field sieve uses to build its notion of smoothness, under the homomorphism ${\displaystyle \phi :\mathbb {Z} [\theta ]\to \mathbb {Z} /n\mathbb {Z} }$.^[13]

See also

• Highly composite number
• Rough number
• Round number
• Størmer's theorem
• Unusual number

Notes and references