Erdos–Kac theorem
Encyclopedia
In number theory
, the Erdős–Kac theorem, named after Paul Erdős
and Mark Kac
, and also known as the fundamental theorem of probabilistic number theory
, states that if ω(n) is the number of distinct prime factor
s of n, then, loosely speaking, the probability distribution
of
is the standard normal distribution. This is a deep extension of the Hardy–Ramanujan theorem
, which states that the average value of ω(n) is log log n with a typical error of size
.
More precisely, for any fixed a < b,
where
is the normal (or "Gaussian") distribution, defined as
Stated somewhat heuristically, what Erdős and Kac proved was that if n is a randomly chosen large integer, then the number of distinct prime factors of n has approximately the normal distribution with mean and variance log log n.
This means that the construction of a number around one billion requires on average three primes.
For example 1,000,000,003 = 23 × 307 × 141623.
Around 12.6% of 10,000 digit numbers are constructed from 10 distinct prime numbers and around 68% (±σ) are constructed from between 7 and 13 primes.
A hollow sphere the size of the planet Earth filled with fine sand would have around 1033 grains. A volume the size of the observable universe would have around 1093 grains of sand. There might be room for 10185 quantum strings in such a universe.
Numbers of this magnitude—with 186 digits—would require on average only 6 primes for construction.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, the Erdős–Kac theorem, named after Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
and Mark Kac
Mark Kac
Mark Kac was a Polish mathematician. His main interest was probability theory. His question, "Can one hear the shape of a drum?" set off research into spectral theory, with the idea of understanding the extent to which the spectrum allows one to read back the geometry. Kac completed his Ph.D...
, and also known as the fundamental theorem of probabilistic number theory
Probabilistic number theory
Probabilistic number theory is a subfield of number theory, which explicitly uses probability to answer questions of number theory. One basic idea underlying it is that different prime numbers are, in some serious sense, like independent random variables...
, states that if ω(n) is the number of distinct prime factor
Prime factor
In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's...
s of n, then, loosely speaking, the probability distribution
Probability distribution
In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....
of
is the standard normal distribution. This is a deep extension of the Hardy–Ramanujan theorem
Hardy–Ramanujan theorem
In mathematics, the Hardy–Ramanujan theorem, proved by , states that the normal order of the number ω of distinct prime factors of a number n is log...
, which states that the average value of ω(n) is log log n with a typical error of size
.More precisely, for any fixed a < b,
where
is the normal (or "Gaussian") distribution, defined as
Stated somewhat heuristically, what Erdős and Kac proved was that if n is a randomly chosen large integer, then the number of distinct prime factors of n has approximately the normal distribution with mean and variance log log n.
This means that the construction of a number around one billion requires on average three primes.
For example 1,000,000,003 = 23 × 307 × 141623.
| n | Number of Digits in n |
Average number of distinct primes |
standard deviation |
|---|---|---|---|
| 1,000 | 4 | 2 | 1.4 |
| 1,000,000,000 | 10 | 3 | 1.7 |
| 1,000,000,000,000,000,000,000,000 | 25 | 4 | 2 |
| 1065 | 66 | 5 | 2.2 |
| 109,566 | 9,567 | 10 | 3.2 |
| 10210,704,568 | 210,704,569 | 20 | 4.5 |
| 101022 | 1022+1 | 50 | 7.1 |
| 101044 | 1044+1 | 100 | 10 |
| 1010434 | 10434+1 | 1000 | 31.6 |
Around 12.6% of 10,000 digit numbers are constructed from 10 distinct prime numbers and around 68% (±σ) are constructed from between 7 and 13 primes.
A hollow sphere the size of the planet Earth filled with fine sand would have around 1033 grains. A volume the size of the observable universe would have around 1093 grains of sand. There might be room for 10185 quantum strings in such a universe.
Numbers of this magnitude—with 186 digits—would require on average only 6 primes for construction.