- Smooth number
In

number theory , a positiveinteger is called "B"-**smooth**if none of itsprime factor s are greater than "B". For example, 1,620 has prime factorization 2^{2}× 3^{4}× 5; therefore 1,620 is 5-smooth since none of its prime factors are greater than 5. 5-smooth numbers are also calledregular number s or Hamming numbers and arise in the study ofBabylonian mathematics ,music theory , and as a test problem forfunctional 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 number s work as well. A number is "B"-smoothif 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 theCooley-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 asBluestein'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

^{4}3^{2}5^{1}is 16-powersmooth since its greatest prime factor power is 2^{4}= 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 computingdiscrete logarithm s 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