Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.