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.

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?

share|improve this question

3 Answers 3

up vote 4 down vote accepted

A quick and dirty answer... (I began before Will answered...)

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

share|improve this answer
    
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.

share|improve this answer
    
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.

share|improve this answer

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.