# 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)?

-
Yes, you should look into Euler's $\phi$ function: en.wikipedia.org/wiki/Euler%27s_totient_function –  Your Ad Here Oct 22 '12 at 18:31
Interesting algorithmic problem! Would suggest inclusion/exclusion to count the ones not relatively prime to $N$ if the prime power factorization of $N$ has few primes. –  André Nicolas Oct 22 '12 at 18:42

## 1 Answer

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.

-
Very nice answer! The programming ideas are rather trivial: Using a mask running from 0 to numberOfDifferentFactors-1, compute the nominator as product of corresponding primes, depending on bitCount(mask) & 1 add or subtract C/nominator, done. –  maaartinus Nov 3 '12 at 10:58