Exactamente lo que me piden en esta pregunta? No necesito la respuesta, sólo la interpretación.

Question

Escribir un programa que las aportaciones de un número entero N y salidas el porcentaje de relativamente primos pares de números a, b en el intervalo de 1 a N.

Por alguna razón, estoy teniendo dificultad para la comprensión de la pregunta. Necesito calcular la probabilidad de a y b, siendo co-primos? Necesito encontrar el mcd? No estoy seguro de lo que me pidió.

También, por favor proporcione una respuesta final o un ejemplo, así que tengo algo para comprobar mi respuesta en contra y saber que estoy en el camino correcto. Gracias.

Answer 1

Tome $N=6$ como un ejemplo. Hay $\binom62=15$ pares de números enteros en el rango de $1$ a través de $N$. Entre ellos, los pares de $\{1,2\},\{1,3\},\{1,4\},\{1,5\},\{1,6\},\{2,3\},\{2,5\},\{3,4\},\{3,5\},\{4,5\}$, e $\{5,6\}$ son relativamente primos. Eso es $11$ relativamente primos pares de un total de $15$ pares, o $73.\overline3$ por ciento.

Añadido: tenga en cuenta que supuse que te están preguntando desordenada pares de distintos números; creo que esta es la interpretación más plausible, pero sería una buena idea para comprobar, si usted tiene alguna manera de hacerlo. El enfoque más sencillo es simplemente para ejecutar $i$$1$$N-1$, y dentro de ese $j$$i+1$$N$, comprobando $\gcd(i,j)$.

Answer 2

Como @Greg Martin comentario de puntos, la pregunta es ambigua. Yo tal caso, la mejor manera de lidiar con esto es como cuatro preguntas, con cuatro respuestas, donde los denominadores son, respectivamente,$n^2$, $n(n-1)$, $\frac12n(n+1)$, y $\frac12n(n-1)$. Obviamente, esto es laborioso; pero usted estará seguro de tener cubiertas todas las posibles interpretaciones.

Answer 3

Creo que se debe interpretar la pregunta como la búsqueda, para dos variables aleatorias independientes $X,Y$ cada distribuidos de manera uniforme sobre el conjunto de $[n]=\{1,2,\ldots,n\}$, la probabilidad de que $\gcd(X,Y)=1$. Mientras que otras interpretaciones de la pregunta son posibles, esta parece ser la más natural para mí, y además, resulta más fácil de manejar.

Usted puede hacer esto mediante dos bucles anidados $[n]$, pero hay una manera más eficiente si $n$ es grande. El valor de $\gcd(X,Y)$ es siempre un valor en$~[n]$, y para un determinado $d\in[n]$ es fácil encontrar la probabilidad de que $\gcd(X,Y)$ es un múltiplo de a$~d$, es decir,$\bigl(\frac{\lfloor n/d\rfloor}n\bigr)^2$: tanto en $X$ $Y$ deben ser múltiplos de $d$, y $\lfloor n/d\rfloor$ estos múltiplos. El factor constante $\frac1{n^2}$ no es muy interesante, así que definen $f(d)=\lfloor n/d\rfloor^2$$d\in[n]$; a continuación, el número de $g(d)$ de los pares de $(x,y)\in[n^2]$ $\gcd(x,y)=d$ satisface $$ \sum_{k=1}^{\lfloor n/d\rfloor}g(kd)=f(d). $$ A partir de esto se puede solucionar $g(d)=f(d)-\sum_{k=2}^{\lfloor n/d\rfloor}g(kd)$ por abajo de la recursividad. Usted puede mejorar aún más mediante la observación de que $g(d)$ sólo depende del valor entero $\lfloor n/d\rfloor$, tan sólo un $2\sqrt n$ valores de $g$ necesario para ser calculado y tabulado. El valor final calculado $g(1)$ da su respuesta $\frac{g(1)}{n^2}$.

Como un resultado de ejemplo, para $N=30$ uno encuentra $g(1)=555$. De más valores de la muestra, ver OEIS:018805.

Answer 4

Usted podría calcular $\sum_{n=1}^N \phi(n)$, que sería $O(N log N)$, para encontrar el número de coprime pares de $1 \leq a<b\leq N$.