Normal order of an arithmetic function

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 ƒ be a function on the natural numbers. We say that g is a normal order of ƒ 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 nx 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[edit]

  • 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[edit]

References[edit]

External links[edit]