In number theory, a positive integer m is called B-smooth if all prime factors p_i of m are such that To meet Wikipedias quality standards, this article or section may require cleanup. ... A negative number is a number that is less than zero, such as −3. ... The integers are commonly denoted by the above symbol. ... In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ...

.

For example, 2²³3⁵⁶5⁴ is 5-smooth since none of its prime factors are greater than 5.

Obviously, a number n is B-smooth if and only if it is p-smooth, where p is the largest prime less than or equal to B.

7-smooth numbers are sometimes called highly composite (although this conflicts with another meaning of that term: see highly composite number). A highly composite number is a positive integer which has more divisors than any positive integer below it. ...

An important practical application of smooth numbers is for fast Fourier transform (FFT) algorithms such as the Cooley-Tukey FFT algorithm that operate by recursively breaking down a problem of a given size n into problems the size of its factors. By using B-smooth numbers, one ensures that the base cases of this recursion are small primes, for which efficient algorithms exist. (Large prime sizes require less-efficient algorithms such as Bluestein's FFT algorithm.) A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. ... The Cooley-Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. ... Bluesteins FFT algorithm (1968), commonly called the chirp-z algorithm (1969), is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of arbitrary sizes (including prime sizes) by re-expressing the DFT as a linear convolution. ...

Powersmooth numbers

Further, m is called B-powersmooth if all prime powers dividing m satisfy:

.

For example, 2⁴3²5¹ is 16-powersmooth since its greatest prime factor power is 2⁴ = 16. The number is also 17-powersmooth, 18-powersmooth, 19-powersmooth, etc.

B-smooth and B-powersmooth numbers have applications in number theory, such as Pollard's p-1 algorithm. Such applications are often said to work with "smooth numbers," with no B specified; this means the numbers involved must be B-smooth for some unspecified small number B; as B increases, the performance of the algorithm or method in question degrades rapidly. For example, the Pohlig-Hellman algorithm for computing discrete logarithms has a running time of O(B^1/2) for groups of B-smooth order. Pollards p − 1 algorithm is a number theoretic integer factorization algorithm, invented by John Pollard in 1974. ... In mathematics, the Pohlig-Hellman algorithm is an algorithm for the computation of discrete logarithms in a multiplicative group whose order is a smooth integer. ... In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. ... In mathematical analysis, and in particular in the analysis of algorithms, to classify the growth of functions one has recourse to asymptotic notations. ... In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ...

Distribution

Let Ψ(x,y) denote the number of y-smooth integers less than or equal to x.

If the smoothness bound B is fixed, there is a good estimate for ψ(x,B):

.

Otherwise, define the parameter u as u = logx / logy: that is, x = y^u. Then we have

where ρ(u) is the Dickman-de Bruijn function. The Dickman – de Bruijn function satisfies a delay differential equation with initial conditions for . ...

External links

• Weisstein, Eric W., Smooth Number at MathWorld.

The On-Line Encyclopedia of Integer Sequences (OEIS) lists B-smooth numbers for small B's: MathWorld is an online mathematics reference work, sponsored by Wolfram Research Inc. ... The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

• 2-smooth numbers: A000079 (2ⁱ)
• 3-smooth numbers: A003586 (2ⁱ3^j)
• 5-smooth numbers: A051037 (2ⁱ3^j5^k)
• 7-smooth numbers: A002473 (2ⁱ3^j5^k7^l)
• 11-smooth numbers: A51038 (etc...)
• 13-smooth numbers: A80197
• 17-smooth numbers: A80681
• 19-smooth numbers: A80682
• 23-smooth numbers: A80683

References

• G. Tenenbaum, Introduction to analytic and probabilistic number theory, (CUP, 1995) ISBN 0-521-41261-7