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 any efficient way , to find for a particular n, the cardinality of set consisting of all numbers coprimes to n, but bigger than m(assuming i know the prime factorisation of n and m)

I am looking for the implementation which is simple+fast (like the euler totient/phi function, which given the factorisation of n will just need O(logn) steps).

share|improve this question

2 Answers 2

You can try to find instead the number of numbers $1 \leq x \leq m$ which are relatively prime to $n$. Lets denote $d(m,n)$ this number. Then your answer is $\phi(n)- d(m,n)$.

If $p_1,..,p_k$ are all the primes dividing $n$, a simple inclusion-exclusion calculation tells us what $m-d(m,n)$ (namely the numbers which are not relatively prime to n) is:

There are $\left\lfloor \frac{m}{p_i} \right\rfloor$ multiples of $p_i$, there are $\left\lfloor \frac{m}{p_ip_j} \right\rfloor$ multiples of $p_i p_j$ and so on. Thus

$$m-d(m,n)= \sum_{i=1}^k \left\lfloor \frac{m}{\,p_i\,} \right\rfloor -\sum_{ 1 \leq i < j \leq k} \left\lfloor \frac{m}{p_ip_j} \right\rfloor+\sum_{ 1 \leq i < j< l \leq k} \left\lfloor \frac{m}{p_ip_jp_k} \right\rfloor-\ldots+(-1)^{k-1} \left\lfloor \frac{m}{p_1p_2....p_k} \right\rfloor$$

Thus, unless I made a mistake, your number is

$$\phi(n)-m+\sum_{i=1}^k \left\lfloor \frac{m}{p_i} \right\rfloor -\sum_{ 1 \leq i < j \leq k} \left\lfloor \frac{m}{p_ip_j} \right\rfloor+\sum_{ 1 \leq i < j< l \leq k} \left\lfloor \frac{m}{p_ip_jp_k} \right\rfloor-\ldots+(-1)^{k-1} \left\lfloor \frac{m}{p_1p_2....p_k} \right\rfloor$$

P.S. I am not sure if the sum is calculable in reasonable time, there are $2^k$ terms where $k$ is the number of prime factors of $n$. $k$ is typically smaller than $\log_2(n)$ but I am not sure if it is always smaller than $\log(\log(n))$.

Also, it is improbable that the sum can be simplified further, due to the integer part. The easy case is when $m$ has exactly the same divisors as $n$, and then it can be simplified to $\phi(n)-\phi(m)$, but in this case this result can be obtained easily directly.

share|improve this answer

You variation seems to have 2 parameters, $n$ and $m$, but no matter - for any $n$, {\em all} primes, except the (finite) set of prime factors, are coprime to any number $n$ (except itself), so the set of those primes $\ge m$ will still be infinite.

share|improve this answer
    
I'm guessing he means to find all numbers $x$ coprime to $n$ such that $m \lt x \lt n$. –  Brandon Carter Mar 10 '11 at 6:03

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.