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!
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.
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,
Now this can be calculated according to the blog linked above.
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.
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?
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.
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?
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:
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)$$$