Hardy–Ramanujan Theorem

In mathematics, the Hardy–Ramanujan theorem, proved by Ramanujan and checked by Hardy states that the normal order of the number $\omega(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 every real-valued function $\psi(n)$ that tends to infinity as $n$ tends to infinity
$, \omega(n)-\log\log n, <\psi(n)\sqrt$
or more traditionally
$, \omega(n)-\log\log n, <^$
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 was given by Pál Turán, who used the Turán sieve to prove that

$\sum_ , \omega(n) - \log\log x, ^2 \ll x \log\log x .$

Generalizations

The same results are true of $\Omega(n)$, the number of prime factors of $n$ counted with multiplicity.
This theorem is generalized by the Erdős–Kac theorem, which shows that $\omega(n)$ is essentially normally distributed. There are many proofs of this, including the method of moments (Granville & Soundararajan) and Stein's method (Harper). It was shown by Durkan that a modified version of Turán's result allows one to prove the Hardy–Ramanujan Theorem with any even moment.

See also

* Almost prime
* Turán–Kubilius inequality

References

Further reading

*
*

{{DEFAULTSORT:Hardy-Ramanujan theorem
Theorems in analytic number theory
Theorems about prime numbers