Escogiendo números enteros aleatorios $a_i$ hasta el $\gcd(a_1,a_2,\dots,a_n)$ 1

Question

Cuando decimos "elige un entero aleatorio", los enteros están en el rango de $[1, N]$.

Problema:

Considere las siguientes instrucciones:

Escoge un entero aleatorio.

Encontrar el máximo común divisor de todos los números enteros que han sido recogidos hasta el momento.

Si el máximo común divisor no es 1, volver a dar el primer paso para elegir un entero aleatorio.

Cuando este proceso termina, vamos a $X$ el número total de enteros que han recogido. Me gustaría encontrar a $E(X)$ en términos de $N$.

Ejemplo de este proceso: (donde $N=4$)

1. Yo elegí el entero aleatorio, 2.
2. $\gcd(2)=2$
3. Tomé otro entero aleatorio, 4.
4. $\gcd(2, 4) = 2$
5. Tomé otro entero aleatorio, 2.
6. $\gcd(2, 4, 2) = 2$
7. Tomé otro entero aleatorio, 3.
8. $\gcd(2, 4, 2, 3) = 1$

En total, cogí $X=4$ enteros, $2, 4, 2, 3$.

Mis ideas:

Un fácil límite superior puede ser demostrado ser $N$, que es el número esperado de números para ser elegido antes de obtener un 1.

Deje $M(g, N)$ ser el esperado número de enteros que voy a necesitar después de conseguir $g$ como el máximo común divisor de los enteros hasta el momento.

Tenemos $E(X)=1+\frac{\sum_{i=1}^NM(g, N)}{N}$.

Pequeño casos:

$N=1\rightarrow E(X)=1$

$N=2\rightarrow E(X)=2$

Answer 1

(no una respuesta, pero aún así probablemente vale la pena un vistazo)

Voy a conseguir una mejor cota superior.

¿Cuál es la probabilidad de que nuestro mcd es divisible por dos? Es $1\over2$ después de el primer paso, $1\over4$ después de la segunda, y así sucesivamente. La probabilidad de ser divisible por 3, del mismo modo, se comporta como ${1\over3^n}$; luego se va 5 y el resto de los números primos. ¿Cuál es la probabilidad de mcd ser divisible por nada en absoluto , excepto 1? Obviamente, no más que la suma de los anteriores (en realidad, menos que eso, porque se superponen): ${1\over4}+{1\over9}+{1\over25}...$ después del paso 2, $\sum\limits_{i=1}^\infty{1\over p_i^3}$ después del paso 3, y así sucesivamente. Así, el número esperado de pasos sería acotado a los de arriba con a $1+1+\sum\limits_{i=1}^\infty{1\over p_i^2}+\sum\limits_{i=1}^\infty{1\over p_i^3}+\dots = 2+\sum\limits_{i=1}^\infty{1\over p_i(p_i-1)} < 2+\sum\limits_{i=2}^\infty{1\over i(i-1)}=3$.

Tenga en cuenta que el obtenido obligado es independiente de $N$.