Normal order of an arithmetic function
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 ω, the number of distinct prime factors of n, is log;
- The normal order of Ω, the number of prime factors of n counted with multiplicity, is log;
- The normal order of log, where d is the number of divisors of n, is log log.