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

:$(1-\varepsilon) g(n) \le f(n) \le (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

*
* . p. 473
*
*

External links

*

Arithmetic functions

{{numtheory-stub