|
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). |
|||
|
|
|
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 $\lfloor \frac{m}{p_i} \rfloor$ multiples of $p_i$, there are $\lfloor \frac{m}{p_ip_j} \rfloor$ multiples of $p_ip_j$ and so on. Thus $$m-d(m,n)= \sum_{i=1}^k \lfloor \frac{m}{p_i} \rfloor -\sum_{ 1 \leq i < j \leq k} \lfloor \frac{m}{p_ip_j} \rfloor+\sum_{ 1 \leq i < j< l \leq k} \lfloor \frac{m}{p_ip_jp_k} \rfloor-...+(-1)^{k-1} \lfloor \frac{m}{p_1p_2....p_k} \rfloor$$ Thus, unless I made a mistake, your number is $$\phi(n)-m+\sum_{i=1}^k \lfloor \frac{m}{p_i} \rfloor -\sum_{ 1 \leq i < j \leq k} \lfloor \frac{m}{p_ip_j} \rfloor+\sum_{ 1 \leq i < j< l \leq k} \lfloor \frac{m}{p_ip_jp_k} \rfloor-...+(-1)^{k-1} \lfloor \frac{m}{p_1p_2....p_k} \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. |
||||
|
|
|
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. |
|||
|
