El factor primo más pequeño esperado

Question

Para un entero al azar$x$ elegido uniformemente entre 2 y$n$, ¿cuál es el valor esperado del factor primo más pequeño de$x$ como una función de$n$?

¿Cuál es el comportamiento de la función como$n$ tiende a infinito?

Answer 1

Rápido y sucio respuesta... (empecé antes de que Le respondió...)

Me dirijo ante la siguiente pregunta: ¿cuál es la probabilidad de $\pi_n$ que un número tiene el n-ésimo prime $p_n$ menor factor primo.

• Un número aleatorio es incluso con proba ${1\over 2}$, por lo que el menor factor primo será de 2 con una probabilidad de ${1\over 2}$.

• Un número impar es un múltiplo de 3, con proba ${1\over 3}$, por lo que el menor factor primo se $3$ con proba ${1\over 2\cdot 3}$.

• Si no es divisible por 2 o 3, lo que ocurre con probabilidad de $1 - {1\over 2} - {1\over 6} = {1\over 3} $, esto va a ser $5$ con proba ${1\over 5}\times{1\over 3} = {2 \over 2\cdot 3 \cdot 5}$.

• Luego será el 7 con 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}$.

Denota esta proba por $\pi_n$ y $p_n$ la secuencia de los números primos, tenemos $\pi_1 = {1\over 2}$$\pi_{n} = {1 \over p_n} \left( 1 - \sum_{i=1}^{n-1} \pi_i\right)$.

Editar me tome un tiempo para ver la conexión entre esta respuesta y la Voluntad. Puedo calcular la totient función :

$\phi(2) = 1$, $\phi(2\cdot3) = 1\cdot 2$, $\phi(2\cdot 3\cdot 5) = 1 \cdot 2 \cdot 4$. Denotando $p_n\# = \prod_{i\le n} p_i$, parece que en el primer par de términos me sale lo siguiente : $$\pi_n = {\phi(p_{n-1}\#) \over p_n\#},$$ que es ligeramente diferente, pero la Voluntad es el cálculo de una expectativa, y él está a la derecha de la fq edición de 6 a continuación.

Edit 2 Esto es lógico, a partir de la definición de totient función : $\phi(p_{n-1}\#)\over p_{n-1}\#$ es la proporción de los números que no son divisibles por $p_1, \dots, p_{n-1}$ ; multiplicar por $1\over p_n$ para obtener la proporción de números que no son divisibles por $p_1, \dots, p_{n-1}$ pero divisible por $p_n$.

Si uno manejar para probar por recurrencia que los definidos anteriormente, $\pi_n$ coincidiendo con esto, el hecho de que la suma es 1, debe ser transparente.

Edición 3 no es difícil de completar. Si podemos demostrar que para todos los $n$, $$1 - \sum_{i\le n} \pi_i = {\phi(p_n\#) \over p_n\#},$$ hemos terminado. Esto es cierto para $n=1, 2$. La inducción paso es: $$\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},$$ así que hemos terminado.

Edición 4 el Uso de Euler truco, tenemos que fácilmente $$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,$$ que sin duda puede escribirse respetando los estándares modernos... yo no estoy familiarizado con la teoría analítica de números, pero estoy seguro de que este producto es un clásico.

Edición 5 Sí, es un clásico, cf Merten del tercer teorema, que dice que $\prod_{p\le n} \left(1-{1\over p}\right) \sim {e^{-\gamma}\over \log n}$. El uso de $p_n \sim n \log(n)$ obtenemos que

$$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 }$$ y $$ \pi_n \sim {e^{-\gamma}\over n \log^2 n},$$ que le da el comportamiento asintótico de esta secuencia.

Edición 6 De hecho yo no la dirección a la pregunta original, pero esto es ahora posible. El menor factor primo de un número tomado de manera uniforme entre 1 y $p_n-1$ $p_k$ con una probabilidad de $\simeq {\pi_k \over \sum_{\ell<n}\pi_\ell}$. Su expectativa es $$ { \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\#},$$ como Se enunció por primera vez (oh, Dios mío, ¿por qué hizo que me tomó tanto tiempo?). La anterior equivalente demuestra que esto se va al infinito como $n\rightarrow\infty$. Comparar a una integral conduce a una $O\left( {p_n \over \log p_n} \right)$.

Answer 2

Tomando las primorials$$P_0 = 1, \; P_1 = 2, \; P_2 = 6, \; P_3 = 30, \; P_4 = 210,$ $ Obtengo su valor esperado como$n$ aumenta a$\infty$ como$$ E = \sum_{k = 0}^\infty \; \frac{\phi(P_k)}{P_k},$ $ wher$\phi$ es la función totient de Euler. Todavía no estoy seguro de si esto es finito.

Answer 3

Intuitivamente, esperaría que esto sea del orden de$\dfrac{n}{\log_e n}$ sobre la base de que es un poco más que la suma de los números primos menores o iguales que$n$ dividido por$n-1$, y eso es un poco menos que$n$ multiplicado por la frecuencia de primos cerca de$n$.

Empíricamente esto parece razonable: para$n$ entre 32000 y 64000, algo así como$1.9\dfrac{n}{\log_e n}$ parece bastante cercano.