# Thread: How to find all the coprimes of a number n in a given range

1. ## How to find all the coprimes of a number n in a given range

Hi ,

This is my first post in this forum.
Here is my problem

The Euler's totient function i.e fi(n) gives us the total numbers that are relatively prime(co-prime) with n in the range [1,n-1]

However i wish to find the number of co-primes of n in the range [1,x]
where x<=n or x>=n.

Wait.... here is the catch.. i need to write a computer program to do so.

Let me elaborate....so that you guys don't think that this is a homework problem or i haven't worked hard enough on this problem.

An easy way to do so is have an array form [1,x] and then strike out all the multiples of prime factors of n.

example : n=30, x=35

prime factors of 30 = 2*3*5

So strike out all the factors of 2 and 3 and 5 from 1 to 35. That would give the answer. Please note that I don't need to find those numbers, i just need the count them i.e how many are co-prime to 30 in the range [1,35].

Another approach could be:

Code:
counter=0
from i=1 to x
if( gcd(i,n) == 1)
counter++;
so answer is the value of counter

However both of these problem are very slow as in my case

1<=n<=2100000000
1<=x<=2100000000

I need a method(or formula) that could quickly find the number of co-primes of n in a range [1,x]

for example if x=n then i can use Euler' totient function... that's easy... but what if x!=n ?

Kindly help me.. i have been searching a solution(that would be fast enough) for the past 3 days and that lead me to this site.

I bet there must be some formula or method that i am missing.
I hope i explained my problem

Regards
lali

2. ## This method will save you computing time for x>n

Since a = a+kn (mod d) for all d|n, gcd(a,n)=gcd(a+kn,n).

Example: Look at the coprimes of 15: 1,2,4,7,8,11,13,14. Now add any multiple of 15 to them, and you have another, bigger set of coprimes.

So, define f(x,n)= “the number of coprimes of n less than or equal to x”

If x>n, then there are phi(n) coprimes between 1 and n, another phi(n) coprimes between n+1 and 2n, and so on. Therefore, f(x,n)=floor(x/n)*phi(n)+f(x%n, n), where "%" denotes the remainder of x/n.

In other words, adjust your loop to find all the coprimes of n only up to x%n, and add that number to floor(x/n)*phi(n), which you said you already had an “easy” method of computing.

You're much better using an array of numbers 1 to x (x<=n) and striking out prime factors than calling the gcd() function x times, from a computing standpoint, assuming you have a relatively fast way to factor n.

3. Originally Posted by Media_Man
Since a = a+kn (mod d) for all d|n, gcd(a,n)=gcd(a+kn,n).

Example: Look at the coprimes of 15: 1,2,4,7,8,11,13,14. Now add any multiple of 15 to them, and you have another, bigger set of coprimes.

So, define f(x,n)= “the number of coprimes of n less than or equal to x”

If x>n, then there are phi(n) coprimes between 1 and n, another phi(n) coprimes between n+1 and 2n, and so on. Therefore, f(x,n)=floor(x/n)*phi(n)+f(x%n, n), where "%" denotes the remainder of x/n.

In other words, adjust your loop to find all the coprimes of n only up to x%n, and add that number to floor(x/n)*phi(n), which you said you already had an “easy” method of computing.

You're much better using an array of numbers 1 to x (x<=n) and striking out prime factors than calling the gcd() function x times, from a computing standpoint, assuming you have a relatively fast way to factor n.

Consider that n=1000000000
and x=500000000, in that case also this approach(i.e strike out all the multiples of prime factors of n) would be slow. The method you have mentioned i had tried earlier.

But how would you take care of the above case.

Please note that in my problem 1<=n<=2100000000
and 1<=x<=2100000000

I also applied the approach that may be the number of relative primes of n
in [1,x/2] is half of that in [1,x]( i don't have any proof, just felt may be it would work.. but i get errors..i mean off by 1 or 2 from the correct answer)
Most probably my assumption is wrong.

I have seen few people solve this problem in 0.01 seconds(on a computer program). So my guess is that they must be using a formula or method that i am unaware of.
The approach of striking out the multiples of prime factors of n is very slow, in my humble opinion, considering the range of x and n.

Another property that i know of is:

if a is co-prime of n then a^fi(n) mod n = 1. Calculating fi(n) is trivial. All i need to find is how many a's are there in [1,x] which satisfy the above property. I don't have any other idea.

All my approaches so far have failed(to be fast enough) Kindly help.

Regards
lali

4. ## Coprimes come in pairs

Proof that the number of coprimes of n from [1,n/2] is half of phi(n):
For some n, let $\displaystyle a+b=n$. Suppose $\displaystyle gcd(a,n)=1$. This means that $\displaystyle a!=0 (mod d)$ for all $\displaystyle d|n$. But $\displaystyle n=0 (mod d)$, so $\displaystyle b=-a!=0 (mod d)$. Ergo, $\displaystyle gcd(b,n)=1$. This implies that $\displaystyle phi(x)$ is always an even number, and that coprimes come in pairs. (These tags are making ! look like a factorial. As you know, I am using != to represent "not equal to.")

DIDN'T YOU SAY YOU TRIED THIS AND GOT INCORRECT ANSWERS? FOR WHAT VALUES OF n DID YOU GET COUNTEREXAMPLES HERE?

5. ## You are correct...but...

Does the result generalize ? i mean the number of co-primes of n in [1,n/2] is half of that in [1,n] and number of co-primes of n in [1,n/4] is 1/4 of that in [1,n] and so on ? No i suppose ? counter example: number of co-primes of 30 in [1,30/8] i.e [1,3] = 3 !=8/8.

That is 30 has three coprimes in interval [1,3] but by above assumption, it should be 8/8 i.e phi(30)/8. So the above assumption is wrong.

I basically tried an approach similar to binary search(assuming the above to be true) and thats why i got wrong results(sometimes off by 1 sometimes off by 2).
When i said that i tried and got wrong result thats what i meant.

Even if number of co-primes of n in [1,n/2] is half of that in [1,n] the solution is still not fast enough considering the range of x and n.

I hope i was able to explain.. why i got wrong results. Is there something i am missing ?

What approach should i follow ?

Regards
lali

6. ## Squareful Numbers

You are very correct that this result cannot be generalized. One half is the only ratio that works. Here is another result that will shave off some computing time for you...

Imagine applying the sieve method to a squareful number (where at least one square can be factored out), such as $\displaystyle 45=3^2*5$

Let a "1" signify a strike-out:
3: 001001001001001001001001001001001001001001001
5: 000010000100001000010000100001000010000100001
S: 001011001101001001011001101001001011001101001

Your coprimes are the "zeros" left over. Notice that this binary pattern repeats in increments of $\displaystyle 15=3*5$. Define $\displaystyle f(n)=$ "the product of all primes $\displaystyle p|n$". Then $\displaystyle phi(n)=n/f(n)*phi(f(n))$. So $\displaystyle phi(3*15)=3*phi(15)$. This is of no help for $\displaystyle n=f(n)$, but for numbers like $\displaystyle n=1,000,000,000=2^9*5^9$, where $\displaystyle f(n)=10$, $\displaystyle phi(n)=100,000,000*phi(10)=400,000,000$.

This will cut down on your computing time, but only slightly, as about 60% of numbers are squarefree, $\displaystyle n=f(n)$.

Here is a more formal proof: For an arbitrary $\displaystyle n$, let $\displaystyle s=f(n)$ as defined earlier. Choose a coprime of $\displaystyle n$ less than $\displaystyle s$ and call it $\displaystyle a$. So $\displaystyle a !=0 (mod p)$ for all $\displaystyle p|n$. By definition of mod, $\displaystyle a+kp !=0$ for all $\displaystyle k$, so $\displaystyle a+ks !=0$, since by construction, if $\displaystyle p|n$ then $\displaystyle p|s$. Therefore the number of coprimes from $\displaystyle [1,s]$ equals the number from $\displaystyle [s+1,2s]$, equals $\displaystyle [2s+1,3s]$, and so on.

7. ## Got it

Here is some java code for you. N is inputted as a string of *distinct* primes (not sure if this works otherwise). Just make sure x<n before inputting. The two for loops are simply a streamlined way to count binary.

int x=400;
int n[]={3,5,7,19,59,103};
int k,b,f,p=0;
String str;
for (int i=0; i<Math.pow(2,n.length); i++)
{
k=0; str=""; b=i; f=1;
for (int j=0; j<n.length; j++)
{
k+=b%2; str+=b%2; f*=(int)Math.pow(n[j],(b%2)); b=b>>1;
}
p+=(int)(Math.pow(-1,k)*Math.floor(x/f));
System.out.println(str+" k="+k+" f="+f+" p="+p);

THIS WORKS ONLY FOR SQUAREFREE NUMBERS N WHERE X<N, BUT WITH THE OTHER RESULTS WE'VE FOUND IN THIS THREAD, YOU SHOULD BE OKAY.

Here is basically the idea: Let n be a squarefree number, and x<n. For each prime p|n, there are floor(x/p) multiples of p less than or equal to x that are therefore NOT coprime to n. So, start with x and subtract off floor(x/p1), floor(x/p2), floor(x/p3), etc. We've now stripped away all numbers under x not coprime to n. But we've double-counted those divisible by more than one p. Ex: x=16, n=30. There are 5 multiples of 3 and 3 multiples of 5 <=16, but we've double counted 15. So now add back in floor(x/p1p2), floor(x/p2p3), etc. Then we've double-added-back numbers with three prime factors. GAAAAA. Have no fear, this is not an endless loop, in fact it is profoundly simple. Start with p=x. Loop through every divisor f|n and if f has an even number of prime factors, add floor(x/f), if odd then subtract. This generalizes further: when f=1, there are 0 factors, which is even, which calls for adding floor(x/1)=x. This makes sense if we simply start p at zero instead of x.

Since we're dealing with squarefree numbers, this allows us to represent the factorization of n in binary, and make the counting loop that much simpler. I DO NOT BELIEVE THIS ALGORITHM WORKS IF YOU ENTER THE SAME PRIME FACTORS IN THE n[] ARRAY.

Combine this algorithm with my previous two posts, and I believe you are finished. This entire algorithm works in O(2^w(n)) time, where w(n) is the number of distinct prime factors of n. YOU ARE ON YOUR OWN WITH THE PROCESSING TIME IT TAKES TO FACTOR N IN THE FIRST PLACE.

8. Here is the programming puzzle i was trying to solve(what this thread was all about).
April 2009 (Contest II) - Problem B3

Thanks for your helpl. I'll try that algorithm and see if it works fast enough to be accepted

,

,

,

,

,

,

,

,

,

,

,

,

,

,

# coprimes

Click on a term to search for related topics.