# Expected smallest prime factor

For a random integer $x$ chosen uniformly between 2 and $n$, what is the expected value of the smallest prime factor of $x$ as a function of $n$?

What is the behavior of the function as $n$ tends to infinity?

-

I first address the following question: what is the probability $\pi_n$ that a number has the n-th prime $p_n$ as smallest prime factor.

• A random number is even with proba ${1\over 2}$, so the smallest prime factor will be 2 with probability ${1\over 2}$.

• An odd number is a multiple of 3 with proba ${1\over 3}$, so the smallest prime factor will be $3$ with proba ${1\over 2\cdot 3}$.

• If it is not dividable by 2 or 3, which happens with probability $1 - {1\over 2} - {1\over 6} = {1\over 3}$, this will be $5$ with proba ${1\over 5}\times{1\over 3} = {2 \over 2\cdot 3 \cdot 5}$.

• Then it will be 7 with proba ${1\over 7} \times (1 - {1\over 2} - {1\over 6} - {1\over 15}) = {1\over 7} \times {4 \over 15} = {8 \over 2\cdot 3 \cdot 5\cdot 7}$.

Denoting this proba by $\pi_n$ and by $p_n$ the sequence of primes, we have $\pi_1 = {1\over 2}$ and $\pi_{n} = {1 \over p_n} \left( 1 - \sum_{i=1}^{n-1} \pi_i\right)$.

Edit I take some time to see the connection between this answer and Will’s. I compute the totient function :

$\phi(2) = 1$, $\phi(2\cdot3) = 1\cdot 2$, $\phi(2\cdot 3\cdot 5) = 1 \cdot 2 \cdot 4$. Denoting $p_n\# = \prod_{i\le n} p_i$, it appears that in the first few terms I get the following : $$\pi_n = {\phi(p_{n-1}\#) \over p_n\#},$$ which is slightly different – but Will is computing an expectation, and he is right cf edit 6 below.

Edit 2 This is logical from the definition of totient function : $\phi(p_{n-1}\#)\over p_{n-1}\#$ is the proportion numbers which are not dividable by $p_1, \dots, p_{n-1}$ ; multiply by $1\over p_n$ to get the proportion of numbers which are not dividable by $p_1, \dots, p_{n-1}$ but dividable by $p_n$.

If one manage to prove by recurrence that the above defined $\pi_n$ coincide with this, the fact that the sum is 1 should be clear.

Edit 3 It is not difficult to complete. If we prove that for all $n$, $$1 - \sum_{i\le n} \pi_i = {\phi(p_n\#) \over p_n\#},$$ we are done. This is true for $n=1, 2$. The induction step is: $$\begin{array}{rcl} 1 - \sum_{i\le n+1} \pi_i &=& \left(1 - \sum_{i\le n} \pi_i\right) - \pi_{n+1} \\ &=& \left(1 - \sum_{i\le n} \pi_i\right)\left( 1 - {1\over p_{n+1}}\right)\\ &=& \left({\phi(p_n\#) \over p_n\#} \right) \left( {p_{n+1} - 1\over p_{n+1}}\right)\\ &=& { \phi(p_n\#) \times (p_{n+1} - 1) \over p_n\# \times p_{n+1} }\\ &=& {\phi(p_{n+1}\#) \over p_{n+1}\#} \end{array},$$ so we are done.

Edit 4 Using Euler’s trick, we have easily that $$1 - \sum_{i=1}^\infty \pi_i = \prod_p \left(1-{1\over p}\right) = { 1 \over \sum_{n=1}^\infty {1\over n}} = 0,$$ which can surely be rewritten respecting the modern standards... I am not familiar with analytic number theory, but I am sure this product is a classic.

Edit 5 Yes, it is a classic, cf Merten’s third theorem, which tells that $\prod_{p\le n} \left(1-{1\over p}\right) \sim {e^{-\gamma}\over \log n}$. Using $p_n \sim n \log(n)$ we get that

$$1 - \sum_{i=1}^n \pi_i = \prod_{p\le p_n} \left(1-{1\over p}\right) \sim {e^{-\gamma}\over \log n + \log\log n} \sim {e^{-\gamma}\over \log n }$$ and $$\pi_n \sim {e^{-\gamma}\over n \log^2 n},$$ which gives you the asymptotic behaviour of this sequence.

Edit 6 In fact I didn’t adress the original question but this is possible now. The smallest prime factor of a number taken uniformly between 1 and $p_n-1$ is $p_k$ with probability $\simeq {\pi_k \over \sum_{\ell<n}\pi_\ell}$. Its expectation is $${ \sum_{\ell < n} p_\ell\pi_\ell \over \sum_{\ell < n} \pi_\ell} \sim \sum_{\ell < n} p_\ell\pi_\ell = \sum_{\ell < n} {\phi(p_\ell\#) \over p_\ell\#},$$ as Will first stated (oh my God, why did that took me so long?). The above equivalent shows that this goes to infinity as $n\rightarrow\infty$. Comparing to an integral leads to a $O\left( {p_n \over \log p_n} \right)$.

-
The induction is easy: If $\pi_n=\frac{\phi(p_{n-1}\#)}{p_n\#}$, then $\pi_{n+1}=\frac1{p_{n+1}}\left(1-\sum_{i=1}^n\pi_i\right)=$ $\frac1{p_{n+1}}\left(1-\sum_{i=1}^{n-1}\pi_i-\frac{\phi(p_{n-1}\#)}{p_n\#}\righ‌​t)=\frac1{p_{n+1}}\left(p_n\pi_n-\frac{\phi(p_{n-1}\#)}{p_n\#}\right)=\frac{(p_n-‌​1)\phi(p_{n-1}\#)}{p_{n+1}\#}=\frac{\phi(p_n\#)}{p_{n+1}\#}$. – Brian M. Scott Dec 28 '11 at 10:57
Well, this is an other way to write it :) – Elvis Dec 28 '11 at 11:59
I posted that before I saw your third edit, or I’d not have bothered. – Brian M. Scott Dec 28 '11 at 12:13
No problem, I kept editing this for a while, it’s my fault. – Elvis Dec 28 '11 at 12:29

Taking the primorials $$P_0 = 1, \; P_1 = 2, \; P_2 = 6, \; P_3 = 30, \; P_4 = 210,$$ I get your expected value as $n$ increases to $\infty$ as $$E = \sum_{k = 0}^\infty \; \frac{\phi(P_k)}{P_k},$$ wher $\phi$ is Euler's totient function. I'm not sure yet whether this is finite.

-
are you saying $E(n) = \sum_k^n \phi(P_k)/P_k$? – user20266 Dec 28 '11 at 8:54

Intuitively, I would expect this to be of the order of $\dfrac{n}{\log_e n}$ on the grounds that it is slightly more than the sum of the primes less than or equal to $n$ divided by $n-1$, and that is slightly less than $n$ times the frequency of primes near $n$.

Empirically this looks reasonable: for $n$ between 32000 and 64000, something like $1.9\dfrac{n}{\log_e n}$ looks fairly close.

-