Find number of coprimes with a given integer in a specified range.

[shitstar]

I was recently asked in my interview for a way to find the number of coprimes with a given integer N (1 <= N <= 10^9) in a range [L, R] (1 <= L <= R <= 10^18).

I have studied a bit of Number Theory earlier, and I knew about the Euler Totient Function. However, for this problem, it could give a Time Limit error (Time limit = 1s). Another point we can use is that for a number X in (N, R] is a coprime with N iff X%N is a coprime with N.

I don't know if I can solve this problem using this fact (the interviewer said that I am going in the right direction, but my approach may give me a TLE).

Can you recommend me a new way to tackle this/such problems?

[tpb]

Consider:
How many numbers from 1 to 100 are coprime with 2 ?
With 4 ?
With 3 ?
With 9 ?
With 6 (= 2 * 3) ?
With 12 ( = 2 * 2 * 3 ) ?
With 36 ( = 2 * 2 * 3 * 3) ?
With 30 (= 2 * 3 * 5) ?

[icy1]

your interviewer actually said to your face that your code might give a Time Limit Expired?

[JLBorges]

Find the set of unique prime factors of N.
(For 1 <= N <= 10^9, the cardinality of this set would be quite small.)

Then use a sieve to count the numbers which are not divisible by any of these prime factors.

[tpb]

@JLBorges, wouldn't a sieve be overkill? The number of primes alone up to 10^18 is > 2^16.

The number of values up to 10^18 coprime with 2 is 10^18 - (10^18 / 2) - 1.
The number of values up to 10^18 coprime with 3 is 10^18 - (10^18 / 3) - 1.
The number of values up to 10^18 coprime with 6 is 10^18 - (10^18 / 2 + 10^18 / 3 - 10^18 / 6) - 1.

[shitstar]

@icy1, he said that it _could_ exceed the time limit, the reason being the algorithm to find the Totient could be at max O(sqrt(n)). So, for values in the range (n, R], I would have to iterate over every number. Making the complexity ~O(n*sqrt(n)). Still, I am not sure.

@tpb, I think you are saying that we use the prime factors to make something like the Sieve of Eratosthenes, and we find the number of coprimes using that?
If that is the case, then what would be your algorithm to find the prime factors (that would be time consuming for big numbers).

[JLBorges]

Yeah, if a sieve is to be used for a large range, it would have to be segmented.

[tpb]

I think you are saying that we use the prime factors to make something like the Sieve of Eratosthenes

No, I never said anything about a sieve. I don't think that's necessary at all. Your largest [L,R] range can have over 10^16 primes in it, so it's quite a job. Obviously the example in my last post doesn't use a sieve. But if there are a lot of factors you will have to deal with many combinations of them. I haven't worked that out at all.

what would be your algorithm to find the prime factors (that would be time consuming for big numbers)

But your highest N is not big. It's only a billion. So something as simple as this may do:

#include <iostream>

inline int g(int n, int f) {
    int cnt = 0;
    while (n % f == 0) {
        n /= f;
        ++cnt;
    }
    if (cnt > 0) {
        std::cout << f;
        if (cnt > 1)
            std::cout << '^' << cnt;
        std::cout << ' ';
    }
    return n;
}

int main() {
    while (true) {
        int n;
        std::cout << ">>> "; // highest prime < 1e9 = 999999937
        if (!(std::cin >> n))
            break;
        n = g(n, 2);
        for (int f = 3; f * f <= n; f += 2)
            n = g(n, f);
        if (n > 1)
            std::cout << n;
        std::cout << '\n';
    }
    std::cout << '\n';
}

[tpb]

Another example:

For ranges from 1 to h, and N with the prime factors 2, 3, 5, 7 (i.e., any N that has all of those factors to at least degree 1):

h - [  h/2 + h/3 + h/5 + h/7
     - h/(2*3) - h/(2*5) - h/(2*7) - h/(3*5) - h/(3*7) - h/(5*7)
     + h/(2*3*5) + h/(2*3*7) + h/(2*5*7) + h/(3*5*7)
     - h/(2*3*5*7) ]
    - 1

(The final -1 gets rid of the number 1, which is not coprime with anything.)

Maybe this isn't a good solution since as there are more and more factors there are more and more combinations.

If h is 1000, the answer to the above is 227.
As a check, this simple program gives the same answer:

int main() {
    const int h = 1000;
    int cnt = 0;
    for (int i = 2; i <= h; i++)
        if (i % 2 != 0 && i % 3 != 0 && i % 5 != 0 && i % 7 != 0)
            ++cnt;
    std::cout << cnt << '\n';
}

[shitstar]

(i.e., any N that has all of those factors to at least degree 1)

What do you mean by degree, here? Unique factors?

This sounds like the Inclusion-Exclusion principle, but looks a bit time consuming.

I found this hint here [1], however, I was unable to understand it. Maybe, it's the same thing of what you were saying?


[1]: https://stackoverflow.com/a/3692986

[tpb]

Yeah, that looks like it. I didn't know it had a name. You say it looks "time consuming" but he says it works in "no time".

[jonnin]

seems like a 'did you know this math trick to count this value' not 'can you code'. Hopefully you are interviewing for a theoretical math position or actuary, not coding?

if you did have to do something to actually find them, you can code up a pretty large lookup table of all the primes to some point. I used to keep the first million primes in a table and that was on much, much smaller machines (but 2 to the 16 is a LOT more than I ever needed). Every bit helps... primes do become sparse after the first N, (I forget N) but if you look at a plot of primes there are a lot more from 0 to some N than there in subsequent intervals. That would reduce the work, somewhat. Doing a sieve or whatever for the first million, maybe even the first 10M, is just spinning your cpu for nothing.

I can't think of a practical use for finding all of the pairs of coprimes though.

[tpb]

but 2 to the 16 is a LOT more than I ever needed

If you're talking about primes up to 10^18 it's 10 to the 16, so more like 2 to the 54.

Number of primes up to:

10^9              50,847,534
10^18 24,739,954,287,740,860

[shitstar]

@Jonnin this interview was for a getting a PHD seat under a Professor at Trinity College - Dublin. Since they are a bit more interested in technology, they were a bit more focussed on the "coding" part.

This question was definitely not for any practical use (maybe mersenne.org can use it.. :P), but I think it was aimed to test my understanding of Primes, or basic Number Theory

@tpb
Thanks for your help. I will look into the problem.