Normal order of an arithmetic function: Difference between revisions
Jump to navigation
Jump to search
imported>Richard Pinch (remove WPmarkup; subpages) |
imported>Richard Pinch m (→Examples: link) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
In [[mathematics]], in the field of [[number theory]], the '''normal order of an arithmetic function''' is some simpler or better-understood function which "usually" takes the same or closely approximate values. | In [[mathematics]], in the field of [[number theory]], the '''normal order of an arithmetic function''' is some simpler or better-understood function which "usually" takes the same or closely approximate values. | ||
Let ''f'' be a function on the [[natural number]]s. We say that the ''normal order'' of ''f'' is ''g'' if for every &epsilon > 0, the inequalities | Let ''f'' be a function on the [[natural number]]s. We say that the ''normal order'' of ''f'' is ''g'' if for every ε > 0, the inequalities | ||
:<math> (1-\epsilon) g(n) \le f(n) \le (1+\epsilon) g(n) \, </math> | :<math> (1-\epsilon) g(n) \le f(n) \le (1+\epsilon) g(n) \, </math> | ||
| Line 12: | Line 12: | ||
==Examples== | ==Examples== | ||
* The [[Hardy–Ramanujan theorem]]: the normal order of ω(''n''), the number of distinct [[prime factor]]s of ''n'', is log(log(''n'')); | * The [[Hardy–Ramanujan theorem]]: the normal order of ω(''n''), the number of distinct [[prime factor]]s of ''n'', is log(log(''n'')); | ||
* The normal order of log(''d''(''n'')), where ''d''(''n'') is the number of divisors of ''n'', is log(2) log log(''n''). | * The normal order of log(''d''(''n'')), where ''d''(''n'') is the [[number of divisors function|number of divisors]] of ''n'', is log(2) log log(''n''). | ||
==See also== | ==See also== | ||
| Line 22: | Line 22: | ||
* {{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=473 | 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=473 | 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=299-324 | 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=299-324 | year=1995 | isbn=0-521-41261-7 }} | ||
Latest revision as of 16:53, 6 December 2008
In mathematics, in the field of number theory, the normal order of an arithmetic function is some simpler or better-understood function which "usually" takes the same or closely approximate values.
Let f be a function on the natural numbers. We say that the normal order of f is g if for every ε > 0, the inequalities
hold for almost all n: that is, if the proportion of n ≤ x for which this does not hold tends to 0 as x tends to infinity.
It is conventional to assume that the approximating function g is continuous and monotone.
Examples
- The Hardy–Ramanujan theorem: the normal order of ω(n), the number of distinct prime factors of n, is log(log(n));
- The normal order of log(d(n)), where d(n) is the number of divisors of n, is log(2) log log(n).
See also
References
- G.H. Hardy; S. Ramanujan (1917). "The normal number of prime factors of a number". Quart. J. Math. 48: 76–92.
- G.H. Hardy; E.M. Wright (2008). An Introduction to the Theory of Numbers, 6th ed.. Oxford University Press, 473. ISBN 0-19-921986-5.
- Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge University Press, 299-324. ISBN 0-521-41261-7.