SMOOTH NUMBER

In number theory, a positive integer is called ''B''-'smooth' if none of its prime factors are greater than B. For example, 2²³3⁵⁶5⁴ 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 functional programming. 7-smooth numbers are sometimes called highly composite, although this conflicts with another meaning of that term.
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.)

Contents

Powersmooth numbers

Distribution

External links

References

Powersmooth numbers

Further, ''m'' is called ''B''-'powersmooth' if all prime ''powers'' $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 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 $Psi(x,y)$ denote 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 $psi(x,B)$:
: .
Otherwise, define the parameter ''u'' as $u\; =\; log\; x\; /\; log\; y$: that is, $x\; =\; y^u$. Then we have
:$Psi(x,y)\; =\; x.$
ho(u) + OBig(rac{x}{log y}Big)
where $$
ho(u) is the Dickman-de Bruijn function.

External links

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

★ 2-smooth numbers: (2ⁱ)

★ 3-smooth numbers: (2ⁱ3^j)

★ 5-smooth numbers: (2ⁱ3^j5^k)

★ 7-smooth numbers: (2ⁱ3^j5^k7^l)

★ 11-smooth numbers: (etc...)

★ 13-smooth numbers:

★ 17-smooth numbers:

★ 19-smooth numbers:

★ 23-smooth numbers:

References

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