View source for Normal order of an arithmetic function

{{TEX|done}}{{MSC|11A}}

A function, perhaps simpler or better-understood, which "usually" takes the same or closely approximate values as a given [[arithmetic function]].


Let $f$ be a function on the [[natural number]]s.  We say that the ''normal order'' of $f$ is $g$ if for every $\epsilon > 0$, the inequalities
$$
(1-\epsilon) g(n) \le f(n) \le (1+\epsilon) g(n)
$$
hold for ''[[almost all]]'' $n$: that is, 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 function|continuous]] and [[Monotone function|monotone]].

===Examples===
* The [[Hardy–Ramanujan theorem]]: the normal order of $\omega(n)$, the number of distinct [[prime factor]]s of $n$, is $\log\log n$;
* The normal order of $\log d(n))$, where $d(n)$  is the [[number of divisors|number of divisors function]] of $n$, is $\log 2 \log\log n$.

===See also===
* [[Asymptotics of arithmetic functions]]
* [[Average order of an arithmetic function]]

===References===
* G.H. Hardy; S. Ramanujan; The normal number of prime factors of a number, Quart. J. Math., 48 (1917), pp. 76–92
* G.H. Hardy; E.M. Wright; An Introduction to the Theory of Numbers, Oxford University Press (2008), pp. 473. {{ISBN|0-19-921986-5}}
* Gérald Tenenbaum; Introduction to Analytic and Probabilistic Number Theory, ser. Cambridge studies in advanced mathematics '''46''' , Cambridge University Press (1995), pp. 299-324. {{ISBN|0-521-41261-7}}