MHB What is the Limit of Prime Factors per Integer?

[alexmahone]

Let $\nu(n)$ be the number of prime factors of the integer $n$. For example, $\nu(8)=3$, $\nu(5)=1$. Prove: $\lim\ \nu(n)/n=0$.

 

[Also sprach Zarathustra]

Let $\nu(n)$ be the number of prime factors of the integer $n$. For example, $\nu(8)=3$, $\nu(5)=1$. Prove: $\lim\ \nu(n)/n=0$.

In math literature we use the symbol $\pi(x)$ for number of prime factors of the integer that less or equal to $x$.You need to prove that:$$\lim_{x\to\infty}\frac{\pi{(x)}}{x}=0$$Proof:Recall calculus limit definition:We will show that for all $\varepsilon >0$, there is exist $N$ such that $\frac{\pi(x)}{x}<\varepsilon$ for all $x\geq N$.Let $n>1$ be a natural number. Bertrand postulate guarantees us existence of prime number $p$ so that $2^{n-1}<p<2^n$. $p$ such that maintains $p\mid (2^n)!$ but $p\nmid (2^{n-1})!$ , hence the binomial coefficient $\binom{2^n}{2^{n-1}}$ divisible by $p$.From the above we get the following inequalities:$$2^{2^n}\geq \binom{2^n}{2^{n-1}} \geq \prod _{2^{n-1}<p<2^n}p\geq (2^{n-1})^{\pi(2^n)-\pi(2^{n-1})}$$We can say conclude that,$$\pi(2^n)-\pi(2^{n-1})\leq \frac{2^n}{n-1}$$Now we substitute $ n=2k,2k-1,2k-2,...,3 $, and summing all the inequalities, we'll get:$$\pi({2^{2k}})-\pi({2^2})\leq \sum ^{2k}_{r=3}\frac{2^r}{r-1}$$It's clear that, $\pi{2^2}<2^2$, hence:$$\pi({2^{2k}})<\sum ^{2k}_{r=2}\frac{2^r}{r-1}=\sum ^{k}_{r=2}\frac{2^r}{r-1}+\sum ^{2k}_{r=k+1}\frac{2^r}{r-1}<\sum ^{k}_{r=2}{2^r}+\sum ^{2k}_{r=k+1}\frac{2^r}{k}<2^{k+1}+\frac{2^{2k+1}}{k}$$$k<2^k$ for all $k\geq 2$ and, $2^{k+1}<\frac{2^{2k+1}}{k}$, so:$$\pi({2^{2k}})<2(\frac{2^{2k+1}}{k})=4(\frac{2^{2k}}{k})$$or:$$\frac{2^{2k}}{2^{2k}}<\frac{4}{k}$$

For all real number $x>4$ , there is exist unique natural number $k$ such that: $$2^{2k-2}<x\leq 2^{2k}$$From last inequality we can deduce:$$\frac{\pi(x)}{x}\leq \frac{\pi(2^{2k})}{x}<\frac{\pi(2^{2k})}{2^{2k-2}}=4(\frac{\pi({2^{2k}})}{2^{2k}})<\frac{16}{k}$$Now, let $ \varepsilon >0$, and we choose $ N=2^{2[\frac{16}{\varepsilon }]+1}$. If $x\geq N$ then $k\geq [\frac{16}{\varepsilon }]+1$, and:$$\frac{\pi(x)}{x}<\frac{16}{[\frac{16}{\varepsilon }]+1}<\varepsilon $$

Q.E.DThe proof is from David M. Burton, Elementary Number Theory, page 419, Hebrew edition.

 

[alexmahone]

There's actually a neat way of doing this:

Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}$

Then $\nu(n)=\alpha_1+\alpha_2+\ldots+\alpha_k$

$n\ge 2^{\alpha_1}2^{\alpha_2}\ldots 2^{\alpha_k}=2^{\alpha_1+\alpha_2+\ldots+\alpha_k}=2^{\nu(n)}$

$\log_2 n\ge\nu(n)$

$0\le\frac{\nu(n)}{n}\le\frac{\log_2 n}{n}$

Using the squeeze theorem, we see that $\lim \frac{\nu(n)}{n}=0$.