2
$\begingroup$

How many co-primes are there for a big integer $N$ over a specified interval ? bounds of $N$ are $[1,10^9]$ and the interval is $[a,b]$ where ($1\leq a\leq b \leq 10 ^{15}$) and there are $100$ testcases of $N$, this is a programming problem actually. Trying "Euler Phi" in its standard formula:

$$\varphi(n)=n\prod_{p|n}\left(1-\frac 1p\right)$$

wont work since we need to factor the Number and that needs generating primes , and since $N$ could reach $10^9$ and there is a time limit for computing, I think 5 seconds. then generating primes is not a good idea .

and looping through $GCD(n,N)$ won't work as there are $100$ testcases and this will take a lot of time , also trying Fourier transform of Phi will take even longer .

so how can I solve this ? thanks in advance ..

  • 0
    Factorization is not too expensive, since you only need to loop upto the square root of N which should easily fit in 5 seconds. Also, you can easily change the interval to make it within N.2012-08-31
  • 0
    @ZeroG but there are 100 N so I dont think factorization will work ,, also what do you mean by "change the interval to make it within N" ?2012-08-31
  • 0
    You can change the interval from (a, b) to (a % N, b % N). Of course, you have to take care of a few cases in here. Also, for 100 N's, you'll be doing the factorization approximately 100 * sqrt(10^9) times, which would be roughly some 10^7 operations. 5 seconds would be more than sufficient for that.2012-08-31
  • 0
    A related question came up on MathOverflow, http://mathoverflow.net/questions/98343/number-of-integers-coprime-to-l, you might find something useful in the answers there.2012-08-31
  • 0
    I'm not sure why you dismissed the idea of iterating over 100 test cases of $GCD(n,N)$, as I have just done this with a very simple program in Pari/gp on my rather old laptop, and it did the job in well under 1 second using 15 digit numbers. I can time it properly if you wish ...2012-08-31
  • 0
    thanks all guys ^^ , the problem that I saw in factorization that if we found Q divisors before sqrt(N) then there are exactly Q divisor in the interval (sqrt(N),N) so how can we check those 2Q divisors for primality ? looping for each Q from 2 to sqrt(q) but what if there were alot of divisors won't that take alot of time ? also suppose that we found all the prime factor for all N's quickly ,, what's the next step ? Euler phi ? but that will give me the count of primes for the interval [1,N) while we have a specified interval [a,b]2012-08-31
  • 0
    @ZeroG mmmmm I tried doing the (a % N, b % N) like for 5 on(11,21) that makes it 5 on (1,1) !! I think am doing it wrong ,, but let's say that we were able to change the interval from (a,b) to sth smaller (q,w) what if there were 50 primes in (a,b) and our N was prime then N is definitely co-prime to all of them won't we lose them when we convert to (q,w) ??2012-08-31

0 Answers 0