Does the 80-20 Rule (also known as the Law of Factor Sparsity, the Law of the Vital Few, and the Pareto Principle) apply to factorization? That is, if x is a large positive integer, then are about 20% of the primes not exceeding x sufficient for factorizing about 80% of the positive integers not exceeding x? Has anyone done a statistical study of this?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Yes. Hint: The set of primes less than 20% of $x$ constitute 20% of the set of primes less than $x$ for large $x$ (use the prime number theorem; using some explicit bounds you can show that the set constitutes at least 19% of the set of primes less than $x$ for all sufficiently large $x$). If any integer $n\leq x$ has a prime factor $p$ larger than 20% of $x$, then that integer $n$ must be one of $p,2p,3p,4p,5p$, so the number of such integers is less than 6 times the number of primes larger than 20% of $x$, and in particular, less than $6\pi(x)$. Thus since $\pi(x)/x\to0$ as $x\to\infty$, the set of primes less than 20% of $x$ are sufficient for factorizing almost all integers $\leq x$.