Halla la probabilidad de que dos enteros aleatoriamente seleccionados (de n enteros) sean relativamente primos

Question

Encontré este problema de encontrar dicha probabilidad y mi primer intento fue crear el siguiente algoritmo: Estoy contando el número de pares que son relativamente primos .

int rel = 0 
int total = n * (n - 1)/2 
for i in [1, n) 
    for j in [i+1, n) 
     if gcd(i, j) == 1 
      ++rel; 
return rel/total 

que es O (n^2).

Aquí está mi intento de reducir la complejidad:

Observación (1): 1 es primo relativo a [2, n] por lo n - 1 pares son triviales.

Observación (2): 2 no es primo relativo a los números pares en el rango [4, n] por lo que quedan los números impares son primos entre sí a 2, por lo

#Relatively prime pairs = (n/2) if n is even 

         = (n/2 - 1) if n is odd. 

Así que mi algoritmo mejorado sería:

int total = n * (n - 1)/2 
int rel = 0 
if (n % 2) // n is odd 
    rel = (n - 1) + n/2 - 1 
else // n is even 
    rel = (n - 1) + n/2 

for i in [3, n) 
    for j in [i+1, n) 
     if gcd(i, j) == 1 
      ++rel; 
return rel/total 

Con este enfoque podría reducir dos bucles, pero la peor complejidad de tiempo de caso sigue siendo O(n^2).

Pregunta: Mi pregunta es si podemos aprovechar cualquier otra característica matemática que no sea la anterior para encontrar la probabilidad deseada en tiempo lineal.

Gracias.

Answer 1

Tendrá que calcular el Euler's Totient Function para todos los números enteros de 1 a n. La función totient o phi de Euler, φ (n), es una función aritmética que cuenta el número de enteros positivos menores que o iguales a n que son relativamente primos a n.

Para calcular la función de manera eficiente, puede utilizar una versión modificada de Sieve of Eratosthenes.

Aquí es un ejemplo de código C++ -

#include <stdio.h> 

#define MAXN 10000000 

int phi[MAXN+1]; 
bool isPrime[MAXN+1]; 

void calculate_phi() { 
    int i,j; 
    for(i = 1; i <= MAXN; i++) { 
     phi[i] = i; 
     isPrime[i] = true; 
    } 

    for(i = 2; i <= MAXN; i++) if(isPrime[i]) { 
     for(j = i+i; j <= MAXN; j+=i) { 
      isPrime[j] = false; 
      phi[j] = (phi[j]/i) * (i-1); 
     } 
    } 

    for(i = 1; i <= MAXN; i++) { 
     if(phi[i] == i) phi[i]--; 
    } 
} 

int main() { 
    calculate_phi(); 
    return 0; 
} 

Se utiliza de Euler fórmula del producto descrito en la página de Wikipedia de la función totient.

Calcular la complejidad de este algoritmo es un poco complicado, pero es mucho menos que O(n^2).Puede obtener resultados para n = 10^7 bastante rápido.

Answer 2

El número de enteros en el rango 0 .. n que son coprimos a n es la función de empo de Euler de n. Está calculando la suma de dichos valores, p. llamada función tottoria sumatoria. Los métodos para calcular esta suma rápida son, por ejemplo, descritos here. Debería obtener fácilmente un método con una complejidad mejor que cuadrática, , dependiendo de qué tan rápido implemente la función totient.

Aún mejor son las referencias que figuran en la enciclopedia de secuencias de enteros: http://oeis.org/A002088, aunque muchas de las referencias requieren algunas habilidades matemáticas.

Usando estas fórmulas, incluso puede obtener una implementación que es sublineal.

Answer 3

Para cada primer p, la probabilidad de que la división de un número elegido aleatoriamente entre 1 y n es

[n/p]/n

([x] siendo el número entero mayor no mayor que x). Si n es grande, esto es aproximadamente 1/p.

La probabilidad de que dividiendo dos tales números escogidos al azar es

([n/p]/n)

nuevo, esto es 1/p para grande n.

dos números son primos entre sí si no prime divide tanto, lo que la probabilidad de que se trata es el producto

Π _{p es primo} (1 - ([n/p]/n))

es suficiente para calcular para todos los primos de menos de o igual a n. Como n va al infinito, este producto se acerca a 6/π .

No estoy seguro de que pueda usar la función totient directamente, como se describe en las otras respuestas.