Hi..

I have been searching for the solution to this problem for quite some time.

Here's the problem:

Given a number n(0<=n<=1000000000), find the total number of coprimes of n in the range [1,x] 0<=x<=1000000000

(i just want the number i.e how many are there ?)


All my approaches so far have been slow.

Approach 1: Prime factorize n and then use an array of size x and remove all the mulitples of prime factors of n.

Approach 2: for i=1;i<=x;i++ if gcd(i,n)==1 counter++;

Approach 3 Using Euler's totient function

fi(n)=total number of co-primes of n from 1 to n-1.

I am dead sure this has something to do with Euler totient function but just can't get it. May be i am missign something.


The last approach is use the formula for union of sets(after finding the prime factors of n) However i think it would be quite tedious to code( can you think how would you code that ?)
I can't.

Kindly help.. i am writing bit fast as internet won't be available after next 2 minutes. Sorry ... thats the way it is here.

I hope i am able to explain my self or i will elaborate once i am home.


Regards
lali

Here is the link to the problem anyway
http://www.codechef.com/APRIL09/problems/B3/

Please don't post any ready made code. Just hints.


Regards
lali

Doesn't the totient function give the number of co-primes for a number n? That is, all the numbers that are co-prime in the interval [0..n]

But as I understand it, you want all co-primes for all ranges, so the number of co-primes in:
[0..1] +
[0..2] +
[0..3] ... etc.
right?

Or, if y(n) is the totient function (can't make the symbol for chi here), you want:
y(1) + y(2) + y(3) + ... + y(n)

Is there any proof that that number is finite anyway?

jlinkels

Euler's totient function gives a formula to find all the co-primes of n in the range [1,n]. This is easy.

However i want to find all the coprimes of n in the range [1,x]
where x<=n or x>=n

How can i do that in a really really fast way ?

Given that the number of co-primes for n is finite (it can't be more than n) then, given that n is finite sum of the co-prime in the range 1..n will also be finite.

You don't need to consider the co-primes for x>n because that will be taken into account when you look at n = x. For example when you are considering the co-primes of 9 you only consider the numbers 1..8, if you want to know if 10 is co-prime with 9 then that will be given when you look at the co-primes of 10.

That's incorrect consider n=30 and x=35 i.e i have to find all the coprimes of 30 upto 35.
The answer is 9
Prime factorization of 30 = 2*3*5
Therefore, by euler's totient function,
fi(30)=(2-1)*2^0*(3-1)*3^0*(5-1)*5^0 = 8

Similarly
fi(35) = 24

So how fi(30) and fi(35) are not anyway related. I just wanted to know the number of coprimes of 30 from [1,35] and the answer is 9

Here is some more interesting observation i found
if you consider the range as say[1,60] the answer = 16 = 2*fi(30)

Similarly for range[1,210] the answer = 24 = 4*fi(30)


Is there something i am missing. I think i am close. But just can't figure out what i am missing.

Kindly help me

Thanks for your patience
Regards
lali

You are of course correct...

However I'd stick my neck out and say that there isn't a pattern fairly safe because we're talking of primes. However you can extend the idea of the totient function.

step 1:find the factors of x: {x=30: 2, 3, 5}
step 2:find the product of each factor pair: {x=30: 2x3, 2x5, 3x5 or 6, 10, 15}
step 3:find the product of each factor triplet: {x=30: 2x3x5 or 30}
step 4:repeat until all factors are multiplied together: {x=30 no more steps are required}
step 5:find the sum of n divided by each factor: {n=35: 17+11+7=35}
step 6:find the sum of n divided by each number from step 2: {n=35: 5+3+2=10}
step 7:find the sum of n divided by each number from step 3: {n=35: 1}
step 8:repeat until all results from step 4 are absorbed: {x=35 no more steps are required}
step 9:number of co-primes to x in the range [1..n] = n - step5 + step6 - step7 etc. {x=30, n=35 is given by 35 - 35 + 10 - 1 = 9}

For x=30, n=60 you will have:

60 - (60/2 + 60/3 + 60/5) + (60/6 + 60/10+ 60/15) - (60/30) = 60 - (30+20+12) + (10+6+4) - 2 = 60 -62 + 20 - 2 = 16

If you know the value of x or you only need to consider a limited range of numbers then this will be quite easy to code.

Thanks for your reply.

Yeah i have mentioned this algorithm in my first post. This is similar to finding the union of sets.
However this is quite difficult to code(atleast for me and i failed in quite many attempts to code the above algorithm.) Can you code this easily ?
Do consider a number whose prime factorization is say 2*3*5*7*11*13*17*19*23 ?


Also i would like to mention another property of totient function.

If a is coprime to n and fi(n) be the euler's totient function then

a^fi(n)mod n =1

So can we deduce any property of 'a' using above property that can solve the problem in a really fast way ?
I have been banging my head at this problem for past 3 days and everyday i think i am very close only to realize at the end of the day that my approach doesn't work or isn't fast enough for the problem.

There must be some specific *thing* that i am missing badly.



Thanks for your help and patience.
Regards
lali

The problem with a^f(n) is that it will get big very quickly and so unless you have the ability to use very large integers (some languages support that others through libraries) I don't think that it will not be feasible.

Another thought would be to use a modified Sieve of Eratosthenes find the factors of x calculate f(x) now exclude the numbers between x and n which are divisible by any of the factors.

again for 30:

factors: 2, 3, 5
f(x): 8
n=35

start with 31, 32, 33, 34, 35
The number to start with will be given by x+f where f is the factor
using factor 2, start at 32 exclude each number from the list that is divisible by 2 (just add two to each number) hence: 32 and 34
giving: 31, 33, 35
using factor 3, start at 33 exclude: 33
giving: 31, 35
using factor 5, start at 35 exclude: 35
giving: 31

Thus there is just one number, which needs to be added to f(n)

For n=60 you will have:
31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60
factor 2:
31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59
factor 3:
31, 35, 37, 41, 43, 47, 49, 53, 55, 59
factor 5:
31, 37, 41, 43, 47, 49, 53, 59

Giving 8, Thus the number of co-primes to 30 between 1..35 is 8+8=16

It would be fairly easy to code that but you will need an array of n-x elements. This wouldn't be very large if you can do bit operations a simpler approach (to code if bits are not available) would be to have an array of integers initialised to zero add one for each 'hit' and at the end count the number of elements whose value is zero.

Hi,
there is an exact formula which counts the number of integers in an interval which are coprime to a given integer. Let $k=1$ in Theorem 3 (b) of the paper
" On the Number of Subsets of [1,m] Relatively Prime to n and Asymptotic Estimates "
which is available online on INTEGERS website (Paper 41).
Good luck!
Mohamed El Bachraoui