When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Pranayhalo's blog

By Pranayhalo, history, 4 years ago, In English

I am trying to solve Coprime Integers. I believe the central idea to the problem involves the ETF, as I can solve the number of integers between a <= x <= b such that gcd(x, n) = 1, and loop this (or possibly leverage Euler Phi Function) for all c <= n <= d. If anyone has a general explanation of the solution, this would also be helpful.

Nevertheless, ETF is "the number of integers [1...n] that are coprime with n. I need "the number of integers [1...c] that are coprime with n.

For example, if n=40=2^3*5 and c=12, then the following 5 pairs are valid: (1,40), (3,40), (7,40), (9,40), (11,40). I think the way this should be generated is this: total number of integers — number of integers not coprime + the number of double counts= 12 — floor(12/2) — floor(12/5) + floor(12/10) = 5. However, this is too inefficient as inclusion-exclusion may take a long time.

I know that the ETF is multiplicative and that phi(P1^x * P2^y) = phi(P1^x) * phi(P2^y). However, this calculates the first ETF definition given above, not the second type which is what I need. How can I transform this to work for my need? And what is the reason behind it? My math is not super strong, so details would be helpful!

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

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

I think it is similar to this problem where instead of being co-prime the gcd should be k. For more insights may be this is helpful.

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

    Let f(n,m) denote the number of pairs (x, y), such that 1 ≤ x ≤ n, 1 ≤ y ≤ m, and GCD(x,y) = 1. Assuming n ≥ m and using inclusion exclusion we get,

    form

    Now this can be calculated according to the blog linked above.

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

I have previously solved this problem by using the inclusion-exclusion principle over possible common prime factors in a pair $$$(x, y)$$$. This is more or less equivalent to the Möbius inversion approach linked to by wjex09, but might be less intimidatingly abstract.

The variant Euler totient function $$$\Phi(n,c)$$$ you suggest might not be enough to solve the problem unless it can be calculated extremely quickly due to the bounds on the problem, but I can't off the top of my head think of a better way to calculate it than to perform inclusion-exclusion over the factors of $$$n$$$, which definitely isn't fast enough and in any case isn't easier than applying the same technique to the pair-counting problem.

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

    I’m thinking the following solution, but it seems too slow. Compute the prime factorization of all numbers <= 10^7. Using sieve this takes O(n loglogn). Then each query for a prime factorization of a number takes O(log n) time. Then for each prime in the prime factorization, we need to do inclusion-exclusion, which takes O(2^p), and the number of distinct primes of any number less than 10^7 is at most 10. So O(2^10)=1000. So each query will take O(1000+logn), and there are at most 10^7 queries, so O(n(1000+logn)), which is too slow, about 10^10. How did you solve this previously using this method, or am I missing something?

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

      Right! This is why I think computing the variant totient function $$$\Phi(n,c)$$$ as you wanted to isn't fast enough. But you can apply inclusion-exclusion over primes directly to the problem of counting pairs $$$(x,y)$$$ with $$$gcd(x,y)=1$$$. Exclude the pairs with a common factor of 2, 3, 5; re-include pairs with both common factors 2 and 3 (== common factor of 6), 2 and 5 (== common factor of 10); and so on. Nominally there are $$$2^{(\text{number of primes < 1e7})}$$$ set intersections to consider, but almost all of those intersections are empty because we don't care about numbers higher than $$$10^7$$$. Overall complexity is $$$O(\min \{b,d\})$$$ arithmetic operations.

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

        Sorry, I’m not fully understanding how you’re including-excluding over primes directly. How do you compute the number of pairs with a common factor of 2,3,5? This would be common factors of 30, so we’d see the number of combinations of (x, y) where 30|x and 30|y? Which is the number of multiple of 30s in the x range * the number of multiples of 30s in the y range? And then you’d do inclusion (+) of all 1-prime factors, exclude (-) all 2-prime factors, incision (+) all 3-prime factors, and so on for all primes <= 10^7?

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

          Start the counter from (d-b+1)*(c-a+1), because there is that many pairs in the range.

          Iterate k from 2 to max(d,b) and include-exclude as needed:

          • if k only contains odd number of prime factors on the first power then exclude the pairs with common factor k
          • if k only contains even number of prime factors on the first power then include the pairs with common factor k
          • if k has a prime factor on the second or greater power ignore it (you've already counted the multiples of this number)

          This can be done both with Erathostenes sieve if you are okay with $$$O(max(b,d)*loglog(max(b,d)))$$$, and also with linear sieve for $$$O(max(b,d))$$$.

          In case you notice that the inclusion-exclusion actually uses the Möbius-function for coefficients, you can also do this in $$$O(max(b,d)^{2/3})$$$ with magic, however it will be more annoying to implement using the harmonic lemma, because instead of $$$\lfloor\frac{n}{i}\rfloor^2$$$, you are calculating $$$\left(\lfloor\frac{b}{i}\rfloor-\lfloor\frac{a-1}{i}\rfloor\right)*\left(\lfloor\frac{d}{i}\rfloor-\lfloor\frac{c-1}{i}\rfloor\right)$$$