John Grieve: Smooth Numbers    
 Smooth Numbers5 comments
8 Jun 2010 @ 05:40, by John Grieve

Number #/ Music/ Pythagorean

Smooth number
From Wikipedia, the free encyclopediaJump to:navigation, search
In number theory, a smooth number is an integer which factors completely into small prime numbers; the term seems coined by Leonard Adleman.[1] Smooth numbers are especially important in cryptography relying on factorization.

Contents [hide]
1 Definition
2 Applications
3 Distribution
4 Powersmooth numbers
5 See also
6 Notes
7 References
8 External links

[edit] Definition
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 because none of its prime factors are greater than 5. 5-smooth numbers are also called regular numbers or Hamming numbers; 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.

[edit] Applications
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.)

5-smooth or regular numbers play a special role in Babylonian mathematics.[2] They are also important in music theory,[3] and the problem of generating these numbers efficiently has been used as a test problem for functional programming.[4]

[edit] Distribution
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 = yu. Then we have

where is the Dickman–de Bruijn function.

[edit] Powersmooth numbers
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 algorithm for computing discrete logarithms has a running time of O(B1/2) for groups of B-smooth order.

[edit] See also
Rough number
Størmer's theorem
[edit] Notes
1.^ M. E. Hellman, J. M. Reyneri, "Fast computation of discrete logarithms in GF (q)", in Advances in Cryptology: Proceedings of CRYPTO '82 (eds. D. Chaum, R. Rivest, A. Sherman), New York: Plenum Press, 1983, p. 3–13, online quote at Google Scholar: "Adleman refers to integers which factor completely into small primes as “smooth” numbers."
2.^ Aaboe, Asger (1965), "Some Seleucid mathematical tables (extended reciprocals and squares of regular numbers)", Journal of Cuneiform Studies 19 (3): 79–86, doi:10.2307/1359089, MR0191779 .
3.^ Longuet-Higgins, H. C. (1962), "Letter to a musical friend", Music Review (August): 244–248 .
4.^ Dijkstra, Edsger W. (1981), Hamming's exercise in SASL, Report EWD792. Originally a privately-circulated handwitten note, [link] .
[edit] References
G. Tenenbaum, Introduction to analytic and probabilistic number theory, (CUP, 1995) ISBN 0-521-41261-7
A. Granville, Smooth numbers: Computational number theory and beyond, Proc. of MSRI workshop, 2004
[edit] External links
Weisstein, Eric W., "Smooth Number" from MathWorld.
The On-Line Encyclopedia of Integer Sequences (OEIS) lists B-smooth numbers for small B's:

2-smooth numbers: A000079 (2i)
3-smooth numbers: A003586 (2i3j)
5-smooth numbers: A051037 (2i3j5k)
7-smooth numbers: A002473 (2i3j5k7l)
11-smooth numbers: A051038 (etc...)
13-smooth numbers: A080197
17-smooth numbers: A080681
19-smooth numbers: A080682
23-smooth numbers: A080683
[show]v • d • eDivisibility-based sets of integers

Overview Integer factorization · Divisor · Unitary divisor · Divisor function · Prime factor · Fundamental theorem of arithmetic

Forms of factorization Prime number · Composite number · Semiprime number · Pronic number · Sphenic number · Square-free number · Powerful number · Perfect power · Achilles number · Smooth number · Regular number · Rough number · Unusual number

Constrained divisor sums Perfect number · Almost perfect number · Quasiperfect number · Multiply perfect number · Hyperperfect number · Superperfect number · Unitary perfect number · Semiperfect number · Primitive semiperfect number · Practical number

Numbers with many divisors Abundant number · Primitive abundant number · Highly abundant number · Superabundant number · Colossally abundant number · Highly composite number · Superior highly composite number · Weird number

Numbers related
to aliquot sequences Untouchable number · Amicable number · Sociable number

Other Deficient number · Friendly number · Solitary number · Sublime number · Harmonic divisor number · Frugal number · Equidigital number · Extravagant number

Retrieved from ""
Categories: Analytic number theory | Integer sequencesPersonal tools
New featuresLog in / create accountNamespaces
ReadEditView historyActions

Main pageContentsFeatured contentCurrent eventsRandom articleInteraction
About WikipediaCommunity portalRecent changesContact WikipediaDonate to WikipediaHelpToolbox
What links hereRelated changesUpload fileSpecial pagesPermanent linkCite this page
Create a bookDownload as PDFPrintable version

[< Back] [John Grieve]



15 Dec 2010 @ 05:53 by me @ : 1620
your prime factorization of 1620 is misleadind  

19 Mar 2015 @ 05:19 by natickhouse @ : I just wanted to let you know that what
I just wanted to let you know that what you do really affects peoples lives and that people - like me - truly appreciate it.  

21 Oct 2015 @ 06:10 by zhengjunxia @ : zhengjx
2015-10-21 zhengjx  

15 Jan 2016 @ 12:57 by 20160116caihuali @ : 20160116caihuali  

6 Jul 2016 @ 03:28 by king king @ : king  

Your Name:
Your URL: (or email)
For verification, please type the word you see on the left:

Other entries in
26 Feb 2017 @ 20:56: Trump versus the Media
26 Jan 2017 @ 18:53: Women's Marches the beginning of the Fightback
7 Jan 2017 @ 20:11: Now's the End Times
15 Nov 2016 @ 22:48: Theory of Civilization-- Part 3
15 Nov 2016 @ 22:20: Theory of Civilization-- Part 2
15 Nov 2016 @ 21:52: Theory of Civilization-- Part 1
14 Nov 2016 @ 22:11: Global march of the right in the context of the dynamics of civilization
12 May 2016 @ 21:47: SuperCivilization, The Second Axial Age and not-so-enlightened Despots Cont.
12 May 2016 @ 21:20: SuperCivilization, The Second Axial Age and not-so-enlightened Despots
28 Feb 2016 @ 18:55: Economic Evolution

[< Back] [John Grieve] [PermaLink]?