Smooth number


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 22 × 34 × 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, 243251 is 16-powersmooth since its greatest prime factor power is 24 = 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:


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Smooth — could mean many things, including:* Draught beer served with nitrogen. * Smooth (magazine) * Smooth function, a function that is infinitely differentiable, used in calculus and topology. * Smooth Island (disambiguation) * Smooth number, a number… …   Wikipedia

  • Smooth muscle tissue — Smooth muscle …   Wikipedia

  • Smooth Criminal — «Smooth Criminal» Сингл Майкла Джексона …   Википедия

  • Smooth Criminal (chanson) — Smooth Criminal Smooth Criminal Single par Michael Jackson extrait de l’album Bad Face B Instrumentale A cappella Dance Mix Sortie octobre 1988 Enregistrement 1985 1986 Durée …   Wikipédia en Français

  • Smooth criminal (chanson) — Smooth Criminal Smooth Criminal Single par Michael Jackson extrait de l’album Bad Face B Instrumentale A cappella Dance Mix Sortie octobre 1988 Enregistrement 1985 1986 Durée …   Wikipédia en Français

  • Smooth muscle — is a type of non striated muscle, found within the tunica media layer of large and small arteries and veins, the bladder, uterus, male and female reproductive tracts, gastrointestinal tract, respiratory tract, the ciliary muscle, and iris of the… …   Wikipedia

  • Smooth Criminal — Single par Michael Jackson extrait de l’album Bad Face B Instrumentale A cappella Dance Mix Sortie octobre 1988 Enregistrement 1985 1986 Durée …   Wikipédia en Français

  • Smooth Criminal — «Smooth Criminal» Sencillo de Michael Jackson del álbum Bad Formato 5 CD single 3 CD single 12 vinilo 7 single Cassette single Grabación 1987 Género(s) Funk, dance pop …   Wikipedia Español

  • Smooth infinitesimal analysis — is a mathematically rigorous reformulation of the calculus in terms of infinitesimals. Based on the ideas of F. W. Lawvere and employing the methods of category theory, it views all functions as being continuous and incapable of being expressed… …   Wikipedia

  • Number Ones — Album par Michael Jackson Sortie 18 novembre 2003 Enregistrement 1978 2003 Durée 79:01 Genre Pop rock,Pop …   Wikipédia en Français