Hardy–Ramanujan theorem

In mathematics, the Hardy–Ramanujan theorem, proved by Hardy & Ramanujan (1917), states that the normal order of the number ω(n) of distinct prime factors of a number n is log(log(n)).

Roughly speaking, this means that most numbers have about this number of distinct prime factors.

Precise statement

A more precise version states that for any real-valued function ψ(n) that tends to infinity as n tends to infinity

|\omega(n)-\log(\log(n))|<\psi(n)\sqrt{\log(\log(n))}

or more traditionally

|\omega(n)-\log(\log(n))|<{(\log(\log(n)))}^{\frac12 +\varepsilon}

for almost all (all but an infinitesimal proportion of) integers. That is, let g(x) be the number of positive integers n less than x for which the above inequality fails: then g(x)/x converges to zero as x goes to infinity.

History

A simple proof to the result Turán (1934) was given by Pál Turán, who used the Turán sieve to prove that

\sum_{n \le x} | \omega(n) - \log\log n|^2 \ll x \log\log x \ .

Generalizations

The same results are true of Ω(n), the number of prime factors of n counted with multiplicity. This theorem is generalized by the Erdős–Kac theorem, which shows that ω(n) is essentially normally distributed.

References

This article is issued from Wikipedia - version of the Wednesday, March 30, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.