Normal order of an arithmetic function

In 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 ƒ be a function on the natural numbers. We say that the normal order of ƒ is g if for every ε > 0, the inequalities

$(1-\varepsilon) g(n) \le f(n) \le (1+\varepsilon) g(n) \,$

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 Ω(n), the number of prime factors of n counted with multiplicity, 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

• Average order of an arithmetic function
• Divisor function
• Extremal orders of an arithmetic function

References

• G.H. Hardy; S. Ramanujan (1917). "The normal number of prime factors of a number". Quart. J. Math. 48: 76–92. http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper35/page1.htm. 
• G.H. Hardy; E.M. Wright (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press. pp. 473. ISBN 0-19-921986-5. 
• Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics. 46. Cambridge University Press. pp. 299–324. ISBN 0-521-41261-7. 

External links

• Weisstein, Eric W., "Normal Order" from MathWorld.

This number theory-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Arithmetic functions Number theory stubs Wikimedia Foundation. 2010. Игры ⚽ Нужна курсовая? Edward Harraden House Green Velvet (album) Look at other dictionaries: Average order of an arithmetic function — 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 : sum {n le x} f(n)… …   Wikipedia Normal order (disambiguation) — Normal order may refer to: Normal order of creation and annihilation operators in theoretical physics Normal order evaluation in computer science Normal order of an arithmetic function in number theory This disambiguation page lists articles… …   Wikipedia Extremal orders of an arithmetic function — In mathematics, in number theory, the extremal orders of an arithmetic function are best possible bounds of the given arithmetic function. Specifically, if f(n) is an arithmetic function and m(n) is a non decreasing function that is ultimately… …   Wikipedia Arithmetic function — In number theory, an arithmetic (or arithmetical) function is a real or complex valued function ƒ(n) defined on the set of natural numbers (i.e. positive integers) that expresses some arithmetical property of n. [1] An example of an arithmetic… …   Wikipedia Normal distribution — This article is about the univariate normal distribution. For normally distributed vectors, see Multivariate normal distribution. Probability density function The red line is the standard normal distribution Cumulative distribution function …   Wikipedia Arithmetic mean — In mathematics and statistics, the arithmetic mean, often referred to as simply the mean or average when the context is clear, is a method to derive the central tendency of a sample space. The term arithmetic mean is preferred in mathematics and… …   Wikipedia First-order logic — is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic (a less… …   Wikipedia Interval arithmetic — Interval arithmetic, also called interval mathematics , interval analysis , and interval computation , is a method in mathematics. It has been developed by mathematicians since the 1950s and 1960s as an approach to putting bounds on rounding… …   Wikipedia Ordinal arithmetic — In the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an… …   Wikipedia Ordinal collapsing function — In mathematical logic and set theory, an ordinal collapsing function (or projection function) is a technique for defining (notations for) certain recursive large countable ordinals, whose principle is to give names to certain ordinals much larger …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”