Average order of an arithmetic function

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 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

Arithmetic function

In number theory, an arithmetic function is a real or complex valued function ƒ defined on the set of natural numbers In number theory, an arithmetic (or arithmetical) function is a real or complex valued function ƒ(n) defined on the set of natural numbers In number theory, an arithmetic (or...

. We say that the average order of f is g if

as x tends to infinity.

It is conventional to choose an approximating function g that 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 average order of d(n), the number of divisors
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...

of n, is log(n);
The average order of σ(n), the sum of divisors of n, is nπ² / 6;
The average order of φ(n), Euler's totient function
Euler's totient function
In number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that...

of n, is 6n / π²;
The average order of r(n), the number of ways of expressing n as a sum of two squares, is π;
The average 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 average order of Ω(n), the number of prime factors of n, is log log n;
The prime number theorem
Prime number theorem
In number theory, the prime number theorem describes the asymptotic distribution of the prime numbers. The prime number theorem gives a general description of how the primes are distributed amongst the positive integers....

is equivalent to the statement that the von Mangoldt function
Von Mangoldt function
In mathematics, the von Mangoldt function is an arithmetic function named after German mathematician Hans von Mangoldt.-Definition:The von Mangoldt function, conventionally written as Λ, is defined as...

Λ(n) has average order 1.

Examples

See also