MHB What is the Limit of Prime Factors per Integer?

  • Thread starter Thread starter alexmahone
  • Start date Start date
AI Thread Summary
The discussion centers on proving that the limit of the ratio of the number of prime factors of an integer \( n \) to \( n \) approaches zero as \( n \) increases. It begins by defining \( \nu(n) \) as the number of prime factors of \( n \) and using the prime counting function \( \pi(x) \) to establish that \( \lim_{x\to\infty}\frac{\pi(x)}{x}=0 \). The proof employs Bertrand's postulate and inequalities related to binomial coefficients to show that the growth of prime factors is outpaced by the growth of integers. Additionally, a logarithmic approach is used to reinforce the conclusion through the squeeze theorem, demonstrating that \( \lim \frac{\nu(n)}{n}=0 \). The discussion concludes with a reference to a proof from a number theory text.
alexmahone
Messages
303
Reaction score
0
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$.
 
Mathematics news on Phys.org
Alexmahone said:
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.
 
Last edited:
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$.
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Back
Top