Número de dígitos hasta alcanzar un primo

Question

Comienza con un dígito aleatorio de $1$ a $9$ . Añade un dígito aleatorio a la derecha de $0$ a $9$ hasta alcanzar un número primo. ¿Cuántos dígitos son necesarios en la media?

Más exactamente: Sea $X$ sea el número de dígitos hasta alcanzar un primo. ¿Se puede consultar $E(X)$ existen, y si es así, ¿hay una estimación adecuada?

Answer 1

Fijar una constante real $c > 0$ y considera el siguiente juego:

En la ronda $n$ Hay un $\min(1/2,c/n)$ probabilidad de ganar el juego. En caso contrario, se pasa a la ronda $n+1$ .

Cabe preguntarse cuál es el número esperado de rondas que se necesitan para ganar la partida. En lugar de intentar calcularlo con exactitud, hagamos la pregunta más débil: ¿es esta expectativa finita o no? Obsérvese que para cualquier $c > 0$ la probabilidad de ganar en la ronda $n$ será eventualmente $c/n$ .

La posibilidad de no ganando después $n$ rondas es:

$$S_n:=\left(1 - \frac{c}{1}\right)\left(1 - \frac{c}{2}\right) \ldots \left(1 - \frac{c}{n}\right).$$

Si $c > 1/2$ Por supuesto, hay que ajustar los primeros factores. Para estimar este producto para grandes $n$ , tomar el logaritmo y utilizar la estimación $\log(1-x) \sim -x$ que es preciso para las pequeñas $x$ para conseguirlo:

$$\log(S_n) \sim - \sum \frac{c}{n} + O(1) \sim -c \log(n) + O(1),$$

o que $\displaystyle{S_n \sim \frac{A}{n^{c}}}$ para alguna constante $A > 0$ . De ello se deduce que la probabilidad de ganar después de exactamente $n$ rondas es:

$$(1 - S_n) - (1 - S_{n-1}) \sim \frac{B}{n^{1+c}},$$

para otra constante $B$ , y por lo tanto el número esperado de rondas requeridas puede ser estimado por:

$$\sum_{n=1}^{\infty} n(S_{n-1} - S_n) \sim \sum \frac{B}{n^c},$$

que es infinito si $c \le 1$ y finito en caso contrario. En particular, si $c \le 1$ la duración esperada del juego es infinita, y si $c > 1$ la longitud esperada es finita. Por supuesto, por la ley cero-uno de Kolmogorov, la expectativa de que finalmente se gane es $1$ .

Comparemos esto con su juego. En la ronda $n$ , usted tiene un $n-1$ número de dígitos al que se añade otro dígito al azar. La probabilidad de que un $n$ -número de un dígito es primo será:

$$\frac{\pi(10^n) - \pi(10^{n-1})}{10^n - 10^{n-1}} \sim \frac{1}{n \log(10)}$$

Ahora, por supuesto, en su juego, los números no son exactamente aleatorios, porque satisfacen algunas condiciones previas (a saber, que no admiten ninguna cadena inicial de dígitos que no sean primos). ¿Cómo cambia esto el análisis? Sospecho que para grandes $n$ No hay mucha diferencia, y también sospecho que será imposible demostrarlo. Sin embargo, sugiere cuál es la respuesta a su juego: porque $1/\log(10) < 1$ la duración esperada del juego es infinita.

Aquí hay dos variaciones:

1. Comienza con un número entero positivo al azar, y luego añade uno de los dígitos $1$ , $3$ , $7$ o $9$ . A "random" $n$ -El número con esta última cifra es primo con probabilidad $(10/4) \cdot 1/n \log(10)$ . Sin embargo, ahora

$$\frac{10}{4 \log(10)} = 1.08573\ldots > 1,$$

por lo que el juego (desde cualquier posición inicial debería tener una expectativa finita.

1. Comienza con un número entero aleatorio y juega el mismo juego en binario. Como $1/\log(2) > 1$ También se conjetura que tiene una expectativa finita.

Answer 2

Supongamos algunas conjeturas duras, que afirman que los primos se comportan como un conjunto aleatorio de enteros con densidad $\frac{1}{\log x}$ tras eliminar las "conspiraciones locales" (es decir, todos los primos suficientemente grandes son coprimos de cualquier número entero fijo).

Dejemos que $a_n$ sea la elección después de la primera $n$ dígitos. Entonces $10^{n}<a_{n+1}<10^{n+1}$ . Estimamos que un número entero dado (coprimo a $10$ ) de esta magnitud es primo con probabilidad $\frac{1}{n\log 10}$ . Así, un número entero arbitrario es primo con probabilidad $$p_n=\frac{\phi(10)}{10n\log 10}=\frac{2}{5n\log 10}=\frac{\alpha}{n}$$

Así que ahora la pregunta es: Lanzo una moneda con probabilidad $p_n$ de hacer girar las cabezas a su vez $n$ . ¿Cuál es el número esperado de lanzamientos antes de obtener una cabeza?

Esto, a su vez, viene dado por $$E=\alpha\sum_{n=1}^{\infty}\left[\prod_{i=1}^{n-1}\left(1-\frac{\alpha}{i}\right)\right]\sim \alpha\sum_{n=1}^{\infty}\left[\prod_{i=1}^{n-1}\exp\left(-\frac{\alpha}{i}\right)\right]\sim\alpha\sum_{n=1}^{\infty}e^{ -\alpha\log n}=\alpha\zeta(\alpha)$$ donde $\zeta$ es la función zeta de Reimann. Pero como $\alpha < 1$ Esto parece sugerir que la expectativa es divergente; no hay un punto finito en el que se pueda esperar haber encontrado un primo.