Calcular el número de enteros en un intervalo dado que son coprimos de un entero dado

Question

Podemos calcular el número de enteros entre $1$ y un número entero dado n que son relativamente primordiales para n utilizando la función de Euler:
Dejemos que $p_1^{\varepsilon1}\cdot p_2^{\varepsilon2} \cdots p_k^{\varepsilon k}$ sea la factorización en primo de n . Entonces $\phi(n)=n\cdot\frac{p_1-1}{p_1}\cdot\frac{p_2-1}{p_2}\cdots\frac{p_k-1}{p_k} $

---

Pero, ¿por qué detenerse aquí? Mi pregunta es:

¿Existe un algoritmo rápido para calcular el número de enteros entre dos enteros que son relativamente primos de un número entero dado?

Según A059956 La probabilidad de que dos enteros x y x + y elegidos al azar son relativamente primos es $1/\zeta{(2)}$ .
Puedo estimar que la respuesta es: $$\frac{y}{\zeta{(2)}}=\frac{6y}{\pi^2}$$ ¿Existe un método mejor que pueda darme una respuesta más precisa a mi pregunta?

Answer 1

Digamos que me entregas números enteros $x$ , $y$ y $m$ y quieres que te diga el número de enteros entre $x$ y $x+y$ y relativamente primo a $m$ . (Para precisar la pregunta, digamos que el número de $n$ satisfaciendo $x < n \leq x+y$ y $n$ es relativamente primo de $m$ .)

Si sólo necesita una estimación suelta, es $\frac{\phi(m)}{m} \cdot y$ , ya que $\phi(m)/m$ es la fracción de los números de cada intervalo $[x+1,x+m]$ que son relativamente primordiales para $m$ . Si $y$ es grande en comparación con $m$ esto será en realidad una muy buena estimación.

Ejemplo: digamos que quieres saber el número de enteros mayores que $47$ y menor o igual a $47+100$ y relativamente primo a $6$ . Bueno, $\phi(6)/6 = 2/6=1/3$ Así que $1/3$ de cada 6 enteros consecutivos son relativamente primos a 6. Por lo tanto, aproximadamente $1/3$ de la $100$ enteros mayores que $47$ y menor o igual a $47+100$ será. Así que la estimación es de 33 enteros.

Para obtener una respuesta exacta, hay que tener en cuenta $x$ y $y$ mod $m$ . Probablemente hay otras buenas maneras de pensar en esto, pero así es como lo estoy pensando: en cada intervalo de longitud $m$ Hay exactamente $\phi(m)$ números relativamente primos a $m$ (ya que golpeas cada clase de residuo mod $m$ Así que es lo mismo que en $0,\dots,m-1$ ). Por tanto, lo mismo ocurre en cualquier intervalo de longitud múltiplo de $m$ . Así que el $\phi(m)/m$ -La estimación basada en el tiempo tiene en cuenta todo, excepto el intervalo al final de la longitud $y\mod m$ . En mi ejemplo, el intervalo $(47, 47+96]$ debe tener exactamente $\phi(6)/6 \cdot 96 = (1/3)\cdot 96 = 32$ números relativamente primos a $6$ y lo único que tenemos que hacer es contar el número de tales números en el intervalo $(47+96,47+100]$ . El único número de este tipo es $47+98$ (ya que $47+97 = -1 + 1 = 0 \mod 6$ Esto es $1$ mod $6$ y no golpearemos a otro hasta $5$ mod $6$ que sería $47+102$ demasiado grande). Así que la respuesta exacta es $32+1=33$ y la estimación fue acertada.

Answer 2

Determina los factores primos del número dado y para cada uno de esos primos, rasca los números del intervalo que son divisibles por ese primo.

Si el intervalo es lo suficientemente pequeño como para que los números puedan almacenarse en una matriz, el cálculo puede acelerarse drásticamente, ya que basta con empezar con el primer número del intervalo que sea divisible por un primo e ir sumando los primos hasta llegar a un número mayor que el final del intervalo.

Si el intervalo es demasiado grande, la fuerza bruta parece ser la única manera.

Por cierto, el cálculo de gcd ya se puede realizar de forma muy eficiente.

Answer 3

El siguiente algoritmo da la solución en tiempo $\mathcal O(\sqrt n +\log(n)n+ \log(l)+\log(r) )= \mathcal O(\log(n)n+\log(l)+\log(r))$ .

Así que básicamente $l$ y $r$ puede ser enorme y no importará, siempre que $n<10^7$ esto se ejecuta en alrededor de un segundo.

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

const lli MAX=1000;
vector <lli> P; //stores primes dividing P;
lli A[MAX]; // A[i] is number of coprime <=i 

lli cop(lli n, lli x){ // this gives the number of coprime integers in {1,2,3...x}
    if(x<0) return(-cop(n,-x-1));
    return(A[n]*(x/n) + A[x%n]);
}

int main(){
    lli n,l,r;
    scanf("%lld %lld %lld",&n,&l,&r);
    lli m=n;
    for(lli i=2;i*i<=m;i++){ // first we extract the prime divisors of n
        if(m%i==0) P.push_back(i);
        while(m%i==0) m/=i;
    }
    if(m!=1) P.push_back(m);
    for(lli i=1;i<=n;i++){ 
        lli t=1;
        for(lli p : P){ // this checks whether an integer is coprime with n
            if(i%p==0) t=0;
        }
        A[i]=A[i-1]+t; //if it is then A[i]=A[i-1]+1 and otherwise A[i]=A[i]
    }
    printf("%lld\n",cop(n,r)-cop(n,l-1));
}