Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Average order of an arithmetic function
Summary
In number theory, an average order of an arithmetic function is some simpler or better-understood function which takes the same values "on average".
Let be an arithmetic function. We say that an average order of is if
as tends to infinity.
It is conventional to choose an approximating function that is continuous and monotone. But even so an average order is of course not unique.
In cases where the limit
exists, it is said that has a mean value (average value) .
An average order of d(n), the number of divisors of n, is log n;
An average order of σ(n), the sum of divisors of n, is nπ26;
An average order of φ(n), Euler's totient function of n, is 6nπ2;
An average order of r(n), the number of ways of expressing n as a sum of two squares, is π;
The average order of representations of a natural number as a sum of three squares is 4πn3;
The average number of decompositions of a natural number into a sum of one or more consecutive prime numbers is n log2;
An average order of ω(n), the number of distinct prime factors of n, is loglog n;
An average order of Ω(n), the number of prime factors of n, is loglog n;
The prime number theorem is equivalent to the statement that the von Mangoldt function Λ(n) has average order 1;
An average value of μ(n), the Möbius function, is zero; this is again equivalent to the prime number theorem.
In case is of the form
for some arithmetic function , one has,
Generalized identities of the previous form are found here. This identity often provides a practical way to calculate the mean value in terms of the Riemann zeta function. This is illustrated in the following example.
For an integer the set of k-th-power-free integers is
We calculate the natural density of these numbers in N, that is, the average value of , denoted by , in terms of the zeta function.
The function is multiplicative, and since it is bounded by 1, its Dirichlet series converges absolutely in the half-plane , and there has Euler product
By the Möbius inversion formula, we get
where stands for the Möbius function.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.