Normal order of an arithmetic function
{{Short description|Type of asymptotic behavior useful in number theory}}
In number theory, a normal order of an arithmetic function is some simpler or better-understood function which "usually" takes the same or closely approximate values.
Let f be a function on the natural numbers. We say that g is a normal order of f if for every ε > 0, the inequalities
:
hold for almost all n: that is, if the proportion of n ≤ x for which this does not hold tends to 0 as x tends to infinity.
It is conventional to assume that the approximating function g is continuous and monotone.
Examples
- The Hardy–Ramanujan theorem: the normal order of ω(n), the number of distinct prime factors of n, is log(log(n));
- The normal order of Ω(n), the number of prime factors of n counted with multiplicity, is log(log(n));
- The normal order of log(d(n)), where d(n) is the number of divisors of n, is log(2) log(log(n)).
See also
References
- {{cite journal| first1=G.H. | last1=Hardy| author1-link=G. H. Hardy| first2=S. | last2=Ramanujan | author2-link=S. Ramanujan |title=The normal number of prime factors of a number n |journal= Quart. J. Math. | volume= 48 | year=1917 | pages= 76–92 | url=http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper35/page1.htm | jfm=46.0262.03 }}
- {{Hardy and Wright | citation=cite book | page=473 }}. p. 473
- {{citation | last1=Sándor | first1=Jozsef | last2=Crstici | first2=Borislav | title=Handbook of number theory II | location=Dordrecht | publisher=Kluwer Academic | year=2004 | isbn=1-4020-2546-7 | page=332 | zbl=1079.11001 }}
- {{cite book | title=Introduction to Analytic and Probabilistic Number Theory | first=Gérald | last=Tenenbaum | others=Translated from the 2nd French edition by C.B.Thomas | series=Cambridge studies in advanced mathematics | volume=46 | publisher=Cambridge University Press | year=1995 | isbn=0-521-41261-7 | zbl=0831.11001 | pages=299–324 }}
External links
- {{MathWorld|urlname=NormalOrder|title=Normal Order}}
{{numtheory-stub}}