darth_chef's blog

Interesting Question on Co-primes
By darth_chef, history, 4 years ago, In English

I found this question somewhere online, which went as follows: For each integer x in a given range [L, R], find the count of integers in the given range that are co-prime with x. Constraints: 1 <= L <= R <= 1e5

Example: For L = 2, R = 4, the co-prime pairs would be:

2 -> (2,3) so count = 1 3 -> (3,2), (3,4) so count = 2 4 -> (4,3) so count = 1

Does anyone have an optimal solution for this?

  • Vote: I like it
  • +16
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

i didnt get it. do you mean just the numbers between L R or there is a array and you want this for ai -> L <= i <= R!? but in these kind of problems there are some solution that works with this -> add edge between them (if you get the numbers or indexes as a node) and then you want the number of edges in range L, R. and you can do this with segment tree. there is a similar problem "Yaroslav and Divisors"

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

    There's no array, I meant all the integers in the given range.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by darth_chef (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it +43 Vote: I do not like it

You can do some inclusion-exclusion/Mobius stuff to solve this.

Let's fix a particular $$$x$$$. Note that it suffices for us to be able to count the number of integers coprime with $$$x$$$ in the range $$$[1,n]$$$, for some $$$n$$$.

All uses of / indicate integer division, by the way.

Let's suppose $$$x = 12$$$. Let's initialize a variable count = n, since initially there are $$$n$$$ numbers in the given range. A number is definitely not coprime with $$$x$$$ if it has a common prime factor with $$$x$$$. So, let's remove all the multiples of $$$2$$$ and all multiples of $$$3$$$, since those definitely arent coprime with $$$12$$$. We do count -= n/2 and count -= n/3. However, when we did this, we subtracted all multiples of $$$6$$$ twice when we really only should have to subtract them once. We account for this by adding back in count += n/6.

Great, let's look at another example. Suppose $$$x = 700$$$. Again, we begin at count = n. Then, remove all multiples of $$$2$$$, $$$5$$$, and $$$7$$$, so count -= n/2, count -= n/5, and count -= n/7. This time, we double-counted the multiples of $$$10$$$, $$$14$$$, and $$$35$$$ (the ones where two distinct prime factors showed up). So, we add back in count += n/10, count += n/14, and count += n/35. However, now we are under-counting the multiples of $$$70$$$ (where all three prime factors appear), so we do again count -= n/70.

In general, we get the following inclusion-exclusion for $$$x$$$:

  • Let count := n initially
  • Then, -= update for all prime divisors of $$$x$$$.
  • Then, += update for all divisors of $$$x$$$ that are exactly two distinct prime factors.
  • Then, -= update for all divisors of $$$x$$$ that are exactly three distinct prime factors.
  • And so on...

This information is captured succinctly in the Mobius function, which you can Google, but long story short, we have a function $$$\mu$$$ such that $$$\mu(d) = 0$$$ if $$$d$$$ is not squarefree; otherwise, $$$\mu(d)=1$$$ if $$$d$$$ has an even number of prime factors, and $$$\mu(d)=-1$$$ if $$$d$$$ has an odd number of prime factors (this describes the inclusion-exclusion alternating parity seen above).

Then, for our counting problem, the answer is

$$$ \sum_{d | x} \mu(d) f(d) $$$

where $$$f(d) = n/d$$$. As you can see, $$$\mu$$$ is just a compact way of saying whether you should add, subtract, or ignore a given divisor to match the inclusion-exclusion formulation. You can look up how to quickly compute $$$\mu(d)$$$ for all $$$d$$$ from $$$1$$$ to $$$n$$$ using a sieve.

Thus, the complexity to answer for a single value of $$$x$$$ is $$$\tau(x)$$$, the number of divisors of $$$x$$$. The worst case complexity to answer all $$$x$$$ in the range $$$[1,n]$$$ is

$$$ \sum_{x=1}^n \tau(x) = \mathcal{O}(n \log n) $$$
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I knew Mobius function was to be used, just couldn't figure it out till the end. Brilliant explanation though, thanks.

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

    Hi. I was thinking of using function similar to totient function(see this) but the problem is that it gives wrong answer. I am not able to think why it gives wrong answer though. Can you please help. Help is appriciated:)

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

      How are you using the totient function?

      You'll notice the main difference between this problem and the derivation of the totient function is that we are counting all coprime to $$$x$$$ in the range $$$[1,n]$$$; unlike in $$$\varphi(n)$$$, in our problem $$$x$$$ and $$$n$$$ are not necessarily the same.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        yes i know that. in the above link in combinatorial proof of totient function ,what if we use prime factors of x instead of prime factors of n. Thanks for replying

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

          Just try it for concrete values and you'll find that it doesn't count what you want to be counting

          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can you please share the problem link?

→ Reply