8
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm guessing he means to find all numbers $x$ coprime to $n$ such that $m \lt x \lt n$. $\endgroup$ – Brandon Carter Mar 10 '11 at 6:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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