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
\( {\displaystyle (1-\varepsilon )g(n)\leq f(n)\leq (1+\varepsilon )g(n)} \)
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
Average order of an arithmetic function
Divisor function
Extremal orders of an arithmetic function
References
Hardy, G.H.; Ramanujan, S. (1917). "The normal number of prime factors of a number n". Quart. J. Math. 48: 76–92. JFM 46.0262.03.
Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001.. p. 473
Sándor, Jozsef; Crstici, Borislav (2004), Handbook of number theory II, Dordrecht: Kluwer Academic, p. 332, ISBN 1-4020-2546-7, Zbl 1079.11001
Tenenbaum, Gérald (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics. 46. Translated from the 2nd French edition by C.B.Thomas. Cambridge University Press. pp. 299–324. ISBN 0-521-41261-7. Zbl 0831.11001.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
