In number theory

Number theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

, the 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 number

Natural number

In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s. We say that the normal order of ƒ is g if for every ε > 0, the inequalities


hold for almost all

Almost all

In mathematics, the phrase "almost all" has a number of specialised uses."Almost all" is sometimes used synonymously with "all but finitely many" or "all but a countable set" ; see almost....

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

Continuous function

In mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...

 and monotone

Monotonic function

In mathematics, a monotonic function is a function that preserves the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory....

.

Examples

• The Hardy–Ramanujan theorem
  Hardy–Ramanujan theorem
  In mathematics, the Hardy–Ramanujan theorem, proved by , states that the normal order of the number ω of distinct prime factors of a number n is log...
  
  : the normal order of ω(n), the number of distinct prime factor
  Prime factor
  In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's...
  
  s of n, is log(log(n));
• The normal order of Ω(n), the number of prime factors of n counted with multiplicity
  Multiplicity (mathematics)
  In mathematics, the multiplicity of a member of a multiset is the number of times it appears in the multiset. For example, the number of times a given polynomial equation has a root at a given point....
  
  , 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
  Average order of an arithmetic function
  In number theory, the average order of an arithmetic function is some simpler or better-understood function which takes the same values "on average".Let f be an arithmetic function...
  
  
• Divisor function
  Divisor function
  In mathematics, and specifically in number theory, a divisor function is an arithmetical function related to the divisors of an integer. When referred to as the divisor function, it counts the number of divisors of an integer. It appears in a number of remarkable identities, including relationships...
  
  
• Extremal orders of an arithmetic function