Smooth number

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

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 $scriptstylepsi(x,B)$:

:$Psi(x,B)\; sim\; frac\{1\}\{pi(B)!\}\; prod\_\{ple\; 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)\; =\; xcdot\; ho(u)\; +\; Oleft(frac\{x\}\{log\; y\}\; ight)$

where $scriptstyle\; ho(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, [http://www.dms.umontreal.ca/~andrew/PDF/msrire.pdf "Smooth numbers: Computational number theory and beyond"] , Proc. of MSRI workshop, 2004

External links

*The On-Line Encyclopedia of Integer Sequences (OEIS)lists "B"-smooth numbers for small "B"'s:
* 2-smooth numbers: (2^"i")
* 3-smooth numbers: (2^"i"3^"j")
* 5-smooth numbers: (2^"i"3^"j"5^"k")
* 7-smooth numbers: (2^"i"3^"j"5^"k"7^"l")
* 11-smooth numbers: (etc...)
* 13-smooth numbers:
* 17-smooth numbers:
* 19-smooth numbers:
* 23-smooth numbers: