Para dos números aleatorios$d$ dígitos$a,b$%, ¿cuál es la probabilidad$\gcd(a,b)<B$? Aquí$B$ es mucho más pequeño que$a,b$.
Respuestas
¿Demasiados anuncios?
La probabilidad de que dos enteros, elegido uniformemente al azar de $1,2,\dots,n$, el mayor común divisor $g$, es (para grandes $n$) $\displaystyle{6\over\pi^2g^2}$. Así que la probabilidad de que el mcd es menos de $B$$\displaystyle{6\over\pi^2}\sum_{g=1}^{B-1}{1\over g^2}$.
Una referencia es J. Chidambaraswamy y R. Sitarmachandrarao, En la probabilidad de que los valores de $m$ polinomios tienen un determinado g.c.d., Revista de Teoría de los números 26 (1987) 237-245.
La información que se encuentra en http://en.wikipedia.org/wiki/Greatest_common_divisor#Probabilities_and_expected_value
Hay una buena exposición en http://aperiodical.com/2013/06/cushing-your-luck-properties-of-randomly-chosen-numbers/
La elección de $1,2,\dots,n$ no es lo mismo que elegir entre $d$-números de un dígito, pero tengo la sospecha de que un gran $d$ de las respuestas llegan de fuera de la misma.
Hagen von Eitzen
Puntos
171160
Heurísticamente: para$k>B$, la probabilidad de que ambos$a$ sea un múltiplo de$k$ es esencialmente$\frac1k$, de ahí que tanto$a$ y$b$ múltiplos de$k$ es$\frac1{k^2}$. Asumiendo ingenuamente la independencia (que da un límite superior), la probabilidad de que$\gcd(a,b)>B$ sea por lo tanto como máximo$\le \sum_{k=B}^\infty \frac1{k^2}=\frac{\pi^2}6-\sum_{k=1}^B\frac1{k^2}$. Para el pequeño$B$ esta estimación no es muy buena.
