- Smooth number
number theory, a positive integeris 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 ifit 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 algorithmthat 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.)
Further, "m" is called "B"-powersmooth if all prime "powers" dividing "m" satisfy:
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 algorithmfor computing discrete logarithms has a running time of O("B"1/2) for groups of "B"-smooth order.
Let 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 :
Otherwise, define the parameter "u" as "u" = log "x" / log "y": that is, "x" = "y""u". Then we have
where is the
Dickman-de Bruijn function.
* 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
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