How many numbers in a given range are coprime to $N$?

Is there a good algorithm for counting the numbers $x$ between $A$ and $B$ with $x$ and $N$ coprime? This is just like this question except for the range.

The factorization of $N$ is known. I actually need to solve the problem for fixed $N$ and many ranges, so I think I can mark all multiples of factors of $N$ in a BitSet and simply count what remains. But is there a nicer solution (or one for the case I need the answer for a single range only)?

Solution 1:

Let $f(C)$ be the number of integers from $1$ to $C$ that are relatively prime to $N$. If we can compute $f(C)$, the rest is easy. Say we are allowing $A \le x\le B$. Then our answer is $f(B)-f(A-1)$.

Note that $f(C)$ is $C$ minus the number of integers in the interval $[1,C]$ that are not relatively prime to $N$.

Call this number $g(C)$. So $f(C)=C-g(C)$. We attack the problem of finding $g(C)$.

If $N$ is a prime power $p^a$, it is easy. The numbers in the interval $[1,C]$ that are not relatively prime to $N$ are the multiples of $p$. Thus $$g(C)=\left\lfloor \frac{C}{p}\right\rfloor,$$ where $\lfloor x\rfloor$ is the usual "floor" function.

If $N$ has prime power factorization $p^aq^b$, where $p$ and $q$ are distinct primes, then $g(C)$ is the number of integers in $[1,C]$ that are divisible by $p$ or $q$ or both. By Inclusion/Exclusion, we obtain $$g(C)=\left\lfloor \frac{C}{p}\right\rfloor+\left\lfloor \frac{C}{q}\right\rfloor-\left\lfloor \frac{C}{pq}\right\rfloor.$$ The reason is that when we add the first two terms above, we are counting twice all the multiples of $pq$.

If $N$ has prime power factorization $p^aq^br^c$, the same basic idea works. We get $$g(C)=\left\lfloor \frac{C}{p}\right\rfloor+\left\lfloor \frac{C}{q}\right\rfloor+\left\lfloor \frac{C}{r}\right\rfloor-\left\lfloor \frac{C}{qr}\right\rfloor -\left\lfloor \frac{C}{pr}\right\rfloor-\left\lfloor \frac{C}{pq}\right\rfloor+\left\lfloor \frac{C}{pqr}\right\rfloor.$$

Similar expressions work for $N$ that has a more complex prime power factorization.

Remark: Depending on the relative sizes of $A$, $B$, and $N$, there are shortcuts available, involving the Euler $\varphi$-function. This is because there are $\varphi(N)$ numbers relatively prime to $N$ in the interval $[kN+1,(k+1)N]$. Since you know the prime power factorization of $N$, $\varphi(N)$ is given by a simple formula. Thus our problem is solved if we can find $f(D)$ for $D\lt N$. For dividing $C$ by $N$ gives us the number of full "chunks" of shape $[kN+1,(k+1)N]$ there are up to $C$. These are dealt with using the $\varphi$-function, and the remainder $D$ is dealt with by Inclusion/Exclusion.

And in addition to mathematical facts, one will need programming ideas to produce an efficient solution.

Solution 2:

For a proof of André Nicolas's formula using multiplicative number theory, see Section 8.3 in I. Niven, H. S. Zuckerman, H. L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley (New York), 1991, which gives the succinct expressions \begin{align} f(C) & = \sum_{d|N} \mu(d) \left\lfloor \frac{C}{d} \right\rfloor\\ & = \frac{C \varphi(N)}{N} - \sum_{d|N} \mu(d) \text{ frac} \left( \frac{C}{d} \right) \end{align} where the sums are taken over the positive square-free integers $d$ that divide $N$ because $\mu(d)$, the Möbius function, is $0$ when $d$ is not square-free, and $\text{frac}$ is the fractional part function. We see that $C\varphi(N)/N$ approximates $f(C)$ and that the approximation improves as $C$ increases or as the number of prime factors of $N$ decreases.