11064 - Number Theory

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

11064 - Number Theory

Post by sakhassan » Sat Aug 12, 2006 6:23 pm

I didnt get the clear idea of the problem? Can anybuddy help me !!


Thanks in Advance

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Aug 12, 2006 6:29 pm

Did you fail to understand the problem, or can't solve it?

If it's the former, the whole problem is: find out, how many integers m are there, satisfying: 1<=m<=n, and gcd(m,n)!=1, and gcd(m,n)!=m.
That is, how many integers between 1 and n are there, which are not relatively prime with n, and yet are not n's divisors.
Last edited by mf on Sat Aug 12, 2006 8:23 pm, edited 1 time in total.

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Sat Aug 12, 2006 8:03 pm

Thanks... I got the point now.. :).. can any one give me some more test cases.......

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Aug 12, 2006 8:08 pm

Here are some

Code: Select all

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
25
125
53387
2147483647
2147483646
2147483645
2147395600
982007569
765934
377744
216263
391530
669701
475509
349753
887257
417257
158120
699712
268352
772844
78706
My output:

Code: Select all

0
0
0
0
0
1
0
1
1
3
0
3
0
5
4
3
22
464
0
1612883455
519917158
1413369866
31335
417439
188871
0
290699
0
168782
0
126754
10214
96841
387863
153509
406785
42963

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Aug 12, 2006 8:10 pm

sakhassan wrote:Thanks... I got the point now.. :).. can any one give me some more test cases.......
Some cases:

Code: Select all

1
2
3
4
5
6
7
8
9
10
11
12
13
2036223251
1831084566
2060163999
734985436
922144514
57163345
3542469
1661043921
291037751
589276374
2147483641
2147483642
2147483643
2147483644
2147483645
2147483646
2147483647
My AC's outputs:

Code: Select all

0
0
0
0
0
1
0
1
1
3
0
3
0
65684648
1234917567
703269316
394243541
461785527
11983962
1565766
554109674
0
403189119
798354
1120426263
715827880
1079830757
519917158
1612883455
0

mindboggler
New poster
Posts: 6
Joined: Fri Dec 30, 2005 10:29 am

Euler Totient Function?

Post by mindboggler » Sun Aug 13, 2006 12:45 pm

I am using Euler Totien'ts function....which is timing out for some cases because it is difficult to find the prime numbers. Please give me a small hint.

Thank you

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Aug 13, 2006 2:36 pm

Euler Totien'ts function should not time out..
.. i used this and got AC.

What do you mean by 'it's difficult to find the prime numbers' ?

You have to use the prime numbers upto sqrt(N) only and there are only few of them.

mindboggler
New poster
Posts: 6
Joined: Fri Dec 30, 2005 10:29 am

Post by mindboggler » Sun Aug 13, 2006 4:36 pm

This is how I am calculating the prime numbers..

Code: Select all

//Here n is the number for which I am trying to find the primes
int x=n;
double totient = n;
int y=2;
while(x!=0) {
  while(x%y!=0 && y<x) y++;
  if (y>x || y==n) break;
  totient *= ((double)y-1.0)/(double)y;
  while(x%y==0) x=x/y;
}
For Example, a number say 84...the sequence it run thru is...2(2 Times)...then 3 and finally 7.

I tried random cases and have seen that for some, the code sticks a lot of time inside the loop.

Please point out where the mistake is

Thank you

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Sun Aug 13, 2006 6:07 pm

mindboggler wrote:This is how I am calculating the prime numbers..

Code: Select all

//Here n is the number for which I am trying to find the primestwhile(x!=0) {
  while(x%y!=0 && y<x) y++;
  if (y>x || y==n) break;
  totient *= ((double)y-1.0)/(double)y;
  while(x%y==0) x=x/y;
}
For Example, a number say 84...the sequence it run thru is...2(2 Times)...then 3 and finally 7.

I tried random cases and have seen that for some, the code sticks a lot of time inside the loop.

Please point out where the mistake is

Thank you
ok , some suggestions to you :D

1 you should try all prime numbers instead of all numbers
( I mean 2 3 5 7 , instead of 2 3 4 5 6 7 8 .... )
2 try prime numbers until ( prime*prime<=n ) , because when
prime*prime>n , now n is a prime

3 you don't need to use double , just int is enough , because
when you do totient*(y-1)/y , you can turn it to
totient/y*(y-1) .

Code: Select all

  example :
  int i=0 , totient = n ;    // prime counter 
  while ( i<size(prime) && prime[i]*prime[i]<=n ) {
     if ( n%prime[i]==0 ) {
       while ( n%prime[i]==0 )
       n/=prime[i] ; 
       totient/=prime[i] , totient*=(prime[i]-1) ;
     }
    i++ 
  }
  if ( n!=1 ) {
       //  now n is a prime , too 
      totient/=n , totient*=(n-1) ; 
  }
studying @ ntu csie

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

11064 i got abt 17 WA.........

Post by ayeshapakhi » Sun Aug 13, 2006 9:29 pm

hi there!
i'm again asking for ur help......
i test Martin's i/o and it's okay...
my code's below

Code: Select all

removed after AC
pls give me such i/o for which my code is wrong.....
or tell me why its wrong!!!!
Thanks.......
Last edited by ayeshapakhi on Tue Aug 15, 2006 8:23 am, edited 1 time in total.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 11064 i got abt 17 WA.........

Post by Martin Macko » Sun Aug 13, 2006 11:37 pm

ayeshapakhi wrote:hi there!
i'm again asking for ur help......
i test Martin's i/o and it's okay...
my code's below
Not working for this one:

Code: Select all

2072798759
My AC's output:

Code: Select all

91052

leocm
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil

Post by leocm » Mon Aug 14, 2006 5:50 am

I'm not understanding how to compute this problem.

Could anybody feel a general explanation of what should be done?

I know the Euler's totient function, but I don't have idea of how implements it in an efficient way.

Thank you.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Aug 14, 2006 6:39 am

Well, you can count divisors and calculate the totient function at the same time, because both can be calculated from the prime factorization.

If a number is given as n = p1^k1 * p2^k2 * ... * pm^km, number of its divisors is (k1+1) * (k2+1) * ... * (km+1) and totient function is (p1-1) * p1^(k1-1) * (p2-1) * p2^(k2-1) * ... * (pm-1) * pm^(km-1).

How to do prime factorization efficiently? Well, I don't know, I just go through primes in order, nothing fancy, and it usually works fine.

leocm
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil

Post by leocm » Mon Aug 14, 2006 7:04 am

Darko wrote:How to do prime factorization efficiently? Well, I don't know, I just go through primes in order, nothing fancy, and it usually works fine.
Yes, I understand your point, but the question is:

Do you have a list of the primes to do this? Until which number? If not, how can you "go through primes in order"?

Thank you.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Aug 14, 2006 7:12 am

Try to divide n by all primes up to sqrt(n).
If at the end of this n is still greater than 1, it'll also be another prime factor.

In pseudo-code:

Code: Select all

p = 2
while p*p <= n do
  while p divides n do
    n=n/p
    output p as a prime factor
  p=p+1   // or you can replace p by next larger prime here, but this will work, too
if n > 1 then output n.
Last edited by mf on Mon Aug 14, 2006 7:19 am, edited 2 times in total.

Post Reply

Return to “Volume 110 (11000-11099)”