theFakeFellow's blog

By theFakeFellow, history, 3 years ago, In English

How to find how many numbers in range [l, r] are coprime to n where r-l < n? [ in O(sqrt(n)) complexity]


Thanks in advance.

  • Vote: I like it
  • -4
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

We will focus on calculating number of numbers coprime to $$$n$$$ which are also less than or equal to a number $$$l$$$. Then we can easily manipulate the result to obtain the answer for a range $$$[l,r]$$$. Also, we could simply solve for finding the numbers which are NOT coprime to $$$n$$$ and are less than or equal to $$$l$$$ and then subtract the result from $$$l$$$ later.

Solution

This approach should work in $$$O(\sqrt{n})$$$ time. The cost of generating subsets is almost constant because the size of the list of prime factors doesn't depend on the value of $$$n$$$ much and it's always less enough to sustain an exponential solution. And prime factorization can be done in $$$\sqrt{n}$$$ time.
I have tried my best to provide a satisfactory explanation but do reply me if any clarification is needed or I have messed up somewhere ':D.
Also I have found an implementation to this problem on the internet.
Link : https://www.geeksforgeeks.org/count-of-natural-numbers-in-range-l-r-which-are-relatively-prime-with-n/

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Can you give me a direct link to the theory that you have used to solve this part or the name of the theory?

    What we will do is to pick a subset of the list A[], calculate the LCM of the elements of it, let's call it L. Now, if the size of this subset was odd, we add the value of f(L,l) to answer else we subtract it.

    And how generating subsets from a set can be done in that very complexity? It would be more helpful if you added a short explanation for me.

    Thanks in advance!

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There is no such theory link, but I think it's explainable.
      We first count the numbers which are direct multiples of $$$a_i$$$. Then we subtract the numbers which are direct multiples of $$$a_i\cdot a_j$$$ (because we have counted them twice, once with $$$a_i$$$ and once with $$$a_j$$$). But in this process we have nullified the contribution of $$$a_i\cdot a_j\cdot a_k$$$ (added with $$$a_i,a_j,a_k$$$ and subtracted with $$$a_i\cdot a_j,a_j\cdot a_k,a_k\cdot a_i$$$). So we should add the contribution of subset of size three. Similarly subtracting for size four and so on...

      And for the case with bitmasking approach, it will take exponential time. But the size of the list of prime factors is at most $$$11$$$ (considering $$$1\leq n\leq 10^{12}$$$). So, a bitmasking approach will always work within the needed time complexity.