Average order of an arithmetic function: Difference between revisions
Jump to navigation
Jump to search
imported>Richard Pinch (New article, my own wording from Wikipedia) |
mNo edit summary |
||
(4 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
{{subpages}} | |||
In [[mathematics]], in the field of [[number theory]], the '''average order of an arithmetic function''' is some simpler or better-understood function which takes the same values "on average". | In [[mathematics]], in the field of [[number theory]], the '''average order of an arithmetic function''' is some simpler or better-understood function which takes the same values "on average". | ||
Line 10: | Line 11: | ||
==Examples== | ==Examples== | ||
* The average order of ''d''(''n''), the number of divisors of ''n'', is log(''n''); | * The average order of ''d''(''n''), the [[number of divisors function|number of divisors]] of ''n'', is log(''n''); | ||
* The average order of σ(''n''), the sum of divisors of ''n'', is <math> \frac{\pi^2}{6} n</math>; | * The average order of σ(''n''), the [[Sum-of-divisors function|sum of divisors]] of ''n'', is <math> \frac{\pi^2}{6} n</math>; | ||
* The average order of φ(''n'')), [[Euler's totient function]] of ''n'', is <math> \frac{6}{\pi^2} n</math>; | * The average order of φ(''n'')), [[Euler's totient function]] of ''n'', is <math> \frac{6}{\pi^2} n</math>; | ||
* The average order of ''r''(''n'')), the number of ways of expressing ''n'' as a [[sum of two squares]], 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. | * The [[Prime Number Theorem]] is equivalent to the statement that the [[von Mangoldt function]] Λ(''n'') has average order 1. | ||
==References== | ==References== | ||
* {{cite book | author=G.H. Hardy | authorlink=G. H. Hardy | coauthors=E.M. Wright | title=An Introduction to the Theory of Numbers | edition=6th ed. | publisher=[[Oxford University Press]] | pages=347-360 | year=2008 | isbn=0-19-921986-5 }} | * {{cite book | author=G.H. Hardy | authorlink=G. H. Hardy | coauthors=E.M. Wright | title=An Introduction to the Theory of Numbers | edition=6th ed. | publisher=[[Oxford University Press]] | pages=347-360 | year=2008 | isbn=0-19-921986-5 }} | ||
* {{cite book | title=Introduction to Analytic and Probabilistic Number Theory | author=Gérald Tenenbaum | series=Cambridge studies in advanced mathematics | volume=46 | publisher=[[Cambridge University Press]] | pages=36-55 | year=1995 | isbn=0-521-41261-7 }} | * {{cite book | title=Introduction to Analytic and Probabilistic Number Theory | author=Gérald Tenenbaum | series=Cambridge studies in advanced mathematics | volume=46 | publisher=[[Cambridge University Press]] | pages=36-55 | year=1995 | isbn=0-521-41261-7 }}[[Category:Suggestion Bot Tag]] | ||
[[Category: | |||
Latest revision as of 06:00, 15 July 2024
In mathematics, in the field of 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 a function on the natural numbers. We say that the average order of f is g if
as x tends to infinity.
It is conventional to assume that the approximating function g is continuous and monotone.
Examples
- 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.
References
- G.H. Hardy; E.M. Wright (2008). An Introduction to the Theory of Numbers, 6th ed.. Oxford University Press, 347-360. ISBN 0-19-921986-5.
- Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge University Press, 36-55. ISBN 0-521-41261-7.