Average order of an arithmetic function
Jump to navigation Jump to search
Revision as of 08:27, 19 December 2011 by
Let f be a function on the natural numbers. We say that the average order of f is g if
as x tends to infinity.
- The average order of d(n), the number of divisors of n, is log(n);
- The average order of σ(n), the sum of divisors of n, is ;
- The average order of φ(n)), Euler's totient function of n, is ;
- The average order of r(n)), the number of ways of expressing n as a sum of two squares, is π ;
- The Prime Number Theorem is equivalent to the statement that the von Mangoldt function Λ(n) has average order 1.