Calculate the number of integers in a given interval that are coprime to a given integer

Question

We can calculate the number of integers between $1$ and a given integer n that are relatively prime to n, using Euler function:
Let $p_1^{\varepsilon1}\cdot p_2^{\varepsilon2} \cdots p_k^{\varepsilon k}$ be the prime factorization of n. Then $\phi(n)=n\cdot\frac{p_1-1}{p_1}\cdot\frac{p_2-1}{p_2}\cdots\frac{p_k-1}{p_k} $

---

But why stop here? My question is:

Is there a fast algorithm to calculate the number of integers between two integers that are relatively prime to a given integer?

According to A059956, The probability that two integers x and x+y picked at random are relatively prime is $1/\zeta{(2)}$ .
Can I estimate the answer to be: $$\frac{y}{\zeta{(2)}}=\frac{6y}{\pi^2}$$ Is there a better method that can give me a more accurate answer to my question?

Answer 1

Determine the prime factors of the given number and for every such prime, scratch the numbers in the interval being divisble by that prime.

If the interval is small enough such that the numbers can be stored in an array, the calculation can be speed up drastically because it is sufficient to start with the first number in the interval being divisble by a prime and then adding the prime until we reach a number greater than the end of the interval.

If the intervall is too large, brute force seems to be the only way.

By the way, the gcd-calculation can already be realized very efficiently.

Answer 2

Let's say that you hand me integers $x$, $y$ and $m$ and you want me to tell you the number of integers between $x$ and $x+y$ and relatively prime to $m$. (To pin the question down precisely, let's say the number of $n$ satisfying $x < n \leq x+y$ and $n$ is relatively prime to $m$.)

If you just need a loose estimate, it's $\frac{\phi(m)}{m} \cdot y$, since $\phi(m)/m$ is the fraction of the numbers on each interval $[x+1,x+m]$ that are relatively prime to $m$. If $y$ is large compared to $m$ this will actually be a very good estimate.

Example: say you would like to know the number of integers greater than $47$ and less than or equal to $47+100$, and relatively prime to $6$. Well, $\phi(6)/6 = 2/6=1/3$, so $1/3$ of every 6 consecutive integers are relatively prime to 6. Thus roughly $1/3$ of the $100$ integers greater than $47$ and less than or equal to $47+100$ will be. So the estimate is 33ish integers.

For an exact answer, you need to account for $x$ and $y$ mod $m$. There are probably other good ways to think about this but here is how I am thinking about it: on every interval of length $m$, there are exactly $\phi(m)$ numbers relatively prime to $m$ (since you hit every residue class mod $m$, so its the same as on $0,\dots,m-1$). Thus the same holds on any interval of length a multiple of $m$. So the $\phi(m)/m$-based estimate accounts for everything except the interval at the end of length $y\mod m$. In my example, the interval $(47, 47+96]$ must have exactly $\phi(6)/6 \cdot 96 = (1/3)\cdot 96 = 32$ numbers relatively prime to $6$, and the only thing we have to do is count the number of such numbers on the interval $(47+96,47+100]$. The only such number is $47+98$ (since $47+97 = -1 + 1 = 0 \mod 6$, this is $1$ mod $6$, and we won't hit another till $5$ mod $6$ which would be $47+102$, too big). So the exact answer is $32+1=33$, and the estimate was spot on.

Answer 3

The following algorithm gives the solution in time $\mathcal O(\sqrt n +\log(n)n+ \log(l)+\log(r) )= \mathcal O(\log(n)n+\log(l)+\log(r))$.

So basically $l$ and $r$ can be huge and it won't matter, as long as $n<10^7$ this runs in around a second.

#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));
}