## 10006 - Carmichael Numbers

Moderator: Board moderators

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:
b3yours3lf wrote:but i've test in my comp (Celeron 1,1 GHZ), it's only take 2 second to find all carmichael number < 65000, but when i submitted itu (only the function to find carmichael number) i got TLE.
You may get TLE if you are calculating carmichael number function again and again for each input. You should use such function just once, generating all carmichael numbers before reading any input. This may look like pre-calculating, but it is not
Else, I read you may have problems if you use signed int (4 bytes), because 32 bits are needed to avoid overflow when calculating 65000 * 65000, so you need unsigned long (4 bytes, 32 bits) or long long (8 bytes, 63 bits + 1 bit for signal) types.

Hope I have helped, but now I need your help
How did you make such function? I failed to do it. Reading about carmichael numbers in mathworld didn't help either:
http://mathworld.wolfram.com/CarmichaelNumber.html

In my first attempt, I first tested if it is prime. If it is not, I test for all number 2<a<n if the equation "a^n mod n = a" is satisfied, but this would obviously cause overflow.
Please explain to me how to test if a number is Carmichael. You may send you function to murilop@email.iis.com.br

backslashnull
New poster
Posts: 3
Joined: Tue Dec 02, 2003 5:02 pm

### How to solve 10006

Hi there!
for testing the a^n %n==a statement you can use the divide method like this:

[cpp]
unsigned long int bigmod(unsigned long int a,unsigned long int b,unsigned long int c){
if (b==0)
return 1;
else if (b==1)
return a%c;
else if (b%2==0){
int k=bigmod(a,b/2,c)%c;
return (k*k)%c;
}
else return ((bigmod(a,b-1,c)%c)*(a%c))%c;
}
[/cpp]
and you can use the traditional loop for prime check in this way you can solve the problem in O(n*n^1/2*lg(n)) but the real time is much much less.

I got AC in 0.650 seconds even with precalc!maybe the input file size is bigger than 1MB !
beacuse i used a loop like this : while (n!=0) { if n==561 || n==1105 ||n==1729 ...)

Happy AC everyone !

fangs404
New poster
Posts: 10
Joined: Thu Jan 22, 2004 3:32 am
Contact:

my code runs wonderfully on my system, but for some reason, the judge isn't accepting my solution; of all things it gives me a compile error. here's the error:

gcj: Internal compiler error: program jc1 got fatal signal 11

i'm using java, and i'm sending it via the e-mail submitter. there are no text wraparounds, and i'm not trying to access methods that java 1.4.2_03 doesn't have over 1.1. of course, when i submit it, i'm change public class Main to class Main, so that's not the problem either. does anyone have any ideas as to what the problem is and how i can solve it? i can post my code if need be, so just ask if i should. thanks for any and all help.
"God does not care about our mathematical difficulties. He integrates empirically."
-Albert Einstein

OutCaster
New poster
Posts: 4
Joined: Thu Jan 22, 2004 2:24 am

### 10006 Time Limit Exceeded .. huh?

Hey guys

I've tried two ways .. precalculating and storing the numbers in an array .. and then i've tried calculating while the online judge spits out a number .. both have failed

I get time limit exceeded even though it runs on my in less than 10 seconds .. any thoughts?

Thanks

fangs404
New poster
Posts: 10
Joined: Thu Jan 22, 2004 3:32 am
Contact:
well, i fixed it. it turns out that i wasn't checking to see if the input from the console would be null (although this shouldn't cause a compile error at all), but whatever. it works now.
"God does not care about our mathematical difficulties. He integrates empirically."
-Albert Einstein

Salmin Sultana
New poster
Posts: 16
Joined: Sun Mar 07, 2004 12:19 pm
Location: Dhaka

### 10006

i can't understand why it is wa?
[cpp]
what a funny mistake
[/cpp]
Last edited by Salmin Sultana on Thu Mar 11, 2004 11:18 am, edited 1 time in total.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
consider this line from your code.

[cpp]printf("The number %ld is a Carmichel number.\n",num);
[/cpp]

Here is the first line of sample output:
The number 1729 is a Carmichael number.
I guess you now know the mistake.

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
The code i used for 10006 gives me TLE.
So i precalculate it .
I wanna know is there a better logic to avoid TLE.
cuii e

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### Try this.

_.

purinflash
New poster
Posts: 2
Joined: Sat Nov 22, 2003 1:35 am
How did you guys generate the carmichael numbers?

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
i precalcuate the prime but did not precalculate the charmical number . i check every time. it is Accepted but it takes large time 1.450 sec.

when i got n , i check whether it is prime or not. next check from 2 to n-1 if i got any other answer than a^n mod n= a, i break the loop. to calculate a^n mod n , i use calculate a^1, a^2, a^4 , a^8.. (mod n) and with this i make a^n mod n.

i don't know if there is other good procedute other than precalculating or sending data table.
__nOi.m....

J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Contact:

### Plz Help me...

Here is my code I do not understand why this out Wrong Ans:..Plz Help me.....
#include<stdio.h>
int main()
{
int i;
long input,array[15]={561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973};
while(scanf("%ld",&input)==1)
{
if(input==0) break;
int k=0;
for(i=0;i<=14;i++)
{
if(input==array)
{
printf("The number %ld is a Charmichael number.\n",input);
k++;
break;
}
}
if(k==0) printf("%ld is normal.\n",input);
}
return 0;
}

J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Contact:
Any body plz help me to find the mistake of my code....I m really unable Why.......

rob
New poster
Posts: 2
Joined: Fri Feb 18, 2005 1:21 pm
Contact:

### linear time

Hi Guys!

Can anybody solve this problem in linear time? I only find this algorithm:

Code: Select all

``````prev_mod = 2%n;
is_charmich = 0;

for(a=2; a<n; a++){
prev_mod = a%n;
for(i=1; i<n; i++){
prev_mod = (a*prev_mod)%n;
}

if(prev_mod != a){
is_charmich = 0;
break;
}

if(a<sqrtn && !(n%a)){
is_charmich = 1;
break;
}
}
``````
but it use O(n^2) time. What is the trick of this problem?

rob

(sorry for my terrible english )

rob
New poster
Posts: 2
Joined: Fri Feb 18, 2005 1:21 pm
Contact:

### Re: Plz Help me...

Hi!
J&Jewel wrote:Here is my code I do not understand why this out Wrong Ans:..Plz Help me.....
Maybe you should declare k near i (outside the while loop).

It's just an idea, so maybe work or maybe not.

rob