Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
1  
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
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.