Smooth numbers.html

In number theory, a positive integer is called B-smooth if none of its prime factors are greater than B. For example, 1,620 has prime factorization 2² × 3⁴ × 5; therefore 1,620 is 5-smooth since none of its prime factors are greater than 5. 5-smooth numbers are also called regular numbers or Hamming numbers and arise in the study of Babylonian mathematics, music theory, and as a test problem for functional programming. 7-smooth numbers are sometimes called highly composite, although this conflicts with another meaning of that term.

Note that B does not have to be a prime factor. If the largest prime factor of a number is p then the number is B-smooth for any B ≥ p. Usually B is given as a prime, but composite numbers work 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.

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.)

1 Powersmooth numbers
2 Distribution
3 See Also
4 References
5 External links

Powersmooth numbers

Further, m is called B-powersmooth if all prime powers $\scriptstyle p_i^{n_i}$ dividing m satisfy:

$p_i^{n_i} \leq B.\,$

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 in 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.

Distribution

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

If the smoothness bound B is fixed and small, there is a good estimate for $\scriptstyle\psi(x,B)$ :

$\Psi(x,B) \sim \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log x}{\log p}.$

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

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

where $\scriptstyle\rho(u)$ is the Dickman-de Bruijn function.

References

G. Tenenbaum, Introduction to analytic and probabilistic number theory, (CUP, 1995) ISBN 0-521-41261-7
A. Granville, Smooth numbers: Computational number theory and beyond, Proc. of MSRI workshop, 2004

External links

Eric W. Weisstein, Smooth Number at MathWorld.

The On-Line Encyclopedia of Integer Sequences (OEIS) lists B-smooth numbers for small B's:

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

Smooth numbers.html

Contents

Powersmooth numbers

Distribution

See Also

References

External links