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 factors of n, then, loosely speaking, the probability distribution of
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.
Digits in n
of distinct primes
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.
- Erdős, Paul; Kac, Mark (1940). "The Gaussian Law of Errors in the Theory of Additive Number Theoretic Functions". American Journal of Mathematics 62 (1/4): 738–742. doi:10.2307/2371483. ISSN 0002-9327. Zbl 0024.10203.
- Kuo, Wentang; Liu, Yu-Ru (2008). "The Erdős–Kac theorem and its generalizations". In De Koninck, Jean-Marie; Granville, Andrew; Luca, Florian. Anatomy of integers. Based on the CRM workshop, Montreal, Canada, March 13--17, 2006. CRM Proceedings and Lecture Notes 46. Providence, RI: American Mathematical Society. pp. 209–216. ISBN 978-0-8218-4406-9. Zbl 1187.11024.
- Kac, Mark (1959). Statistical Independence in Probability, Analysis and Number Theory. John Wiley and Sons, Inc.