Average order of an arithmetic function: Difference between revisions

Revision as of 08:50, 17 December 2009

Revision as of 01:02, 10 November 2010

Line 1:

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]]. We say that the ''average order'' of ''f'' is ''g'' if

:<math> \sum_{n \le x} f(n) \sim \sum_{n \le x} g(n) </math>

Line 13:

* The average order of σ(''n''), the sum of divisors of ''n'', is ''n''π² / 6;

* The average order of φ(''n''), [[Euler's totient function]] of ''n'', is 6''n'' / π²;

* 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]]s of ''n'', is log log ''n'';

* The average order of Ω(''n''), the number of [[prime factor]]sfactors of ''n'', is log log ''n'';

* The [[prime number theorem]] is equivalent to the statement that the [[von Mangoldt function]] Λ(''n'') has average order 1.

Line 24:

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