10006 - Carmichael Numbers

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

Moderator: Board moderators

Moshiur Rahman
New poster
Posts: 13
Joined: Mon Sep 08, 2008 6:57 pm
Location: State University of Bangladesh

Re: 10006 - Carmichael Numbers

reply for adhoc17......

Your program returns 62 Carmichael Numbers in the input range, while there are only 15

for example 341,645,....60787 are not a Carmichael Numbers, but your program says they are also Carmichael numbers

your isprime() function does not work for numbers which are a power of two, like 4,8,16 etc.

check your expm() function again....
Never think too hard, let ideas come to you...

alirezanoori
New poster
Posts: 26
Joined: Fri Jan 02, 2009 12:41 am

Re: 10006 - Carmichael Numbers

I can't understand the problem. Why 17 is Normal?
2^17 mod 17 = 2
3^17 mod 17 = 3
4^17 mod 17 = 4
5^17 mod 17 = 5
6^17 mod 17 = 6
7^17 mod 17 = 7
8^17 mod 17 = 8
9^17 mod 17 = 9
10^17 mod 17 = 10
11^17 mod 17 = 11
12^17 mod 17 = 12
13^17 mod 17 = 13
14^17 mod 17 = 14
15^17 mod 17 = 15
16^17 mod 17 = 16

Although my program finds all these numbers, I double checked them with windows calculator. And I'm sure they're correct.
Could you please help me? I'm sure something's here that I can't understand!

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

Re: 10006 - Carmichael Numbers

Quote from problem statement:
Some numbersthat are not prime still pass the Fermat test with every number smaller than themselves. These numbers are called Carmichael numbers.
17 is a prime.

alirezanoori
New poster
Posts: 26
Joined: Fri Jan 02, 2009 12:41 am

Re: 10006 - Carmichael Numbers

well, first of all thanks for your help. I finally understand the problem. I just don't know how I get WA!!! Because I'm almost sure I've done anything OK. I've checked my output format and its OK too. Here's my Fermat function.

Code: Select all

``````Removed after AC!
``````
If there is ANYTHING wrong with it please let me know. Thanks.
Last edited by alirezanoori on Thu Feb 12, 2009 5:56 pm, edited 1 time in total.

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

Re: 10006 - Carmichael Numbers

I don't see anything wrong with it.

Try to run your program on all possible 65000 inputs, and check that it identifies only these numbers as Carmichael numbers - http://www.research.att.com/~njas/seque ... 2997&fmt=4

alirezanoori
New poster
Posts: 26
Joined: Fri Jan 02, 2009 12:41 am

Re: 10006 - Carmichael Numbers

Thx alot. I tested my program and here's the bug. I used int for my bigmod function, but turns out that it's not enough. I just used long long and everything worked just fine. Now I got AC.

blackSajia
New poster
Posts: 4
Joined: Tue Nov 11, 2008 12:14 pm

Re: 10006 - Carmichael Numbers

Worng ans again again. Plzzzz help me . I give the 15 carmichael number of bellow 65000. these are
561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973.
My program give the right ans.but i get wa in uva. pls help

Code: Select all

``````
#include<stdio.h>
#include<string.h>
#include<math.h>

#define MAX 65005

char a[MAX]={0};

int fact[100];

void prime();
bool isprime(int n);
bool iscarmichael(int n);

int buildPrimeFactor(int n)
{
int i,j;

for(i=1,j=0;i<=n;i++)
if(!(n%i)&&isprime(i))
fact[j++]=i,n/=i,i=1;

return j-1;
}

int main()
{
int n;

prime();

while(1)
{
scanf("%d",&n);

if(n==0)
break;

if(isprime(n))
printf("%d is normal.\n",n);
else
{
if(n%2)
{
if(iscarmichael(n))
printf("The number %d is a Carmichael number.\n",n);
else
printf("%d is normal.\n",n);
}
else
printf("%d is normal.\n",n);

}
}

return 0;
}

void prime()
{
int i,j,sq;

for(i=4;i<MAX;i+=2)
a[i]=1;

sq=(int)sqrt(MAX);

for(i=3;i<=sq;i+=2)
for(j=i+i;j<MAX;j+=i)
a[j]=1;
}

bool isprime(int n)
{
if(a[n]==0)
return true;

return false;
}

bool iscarmichael(int n)
{
int numFactor=buildPrimeFactor(n),i;

bool flag=true;

if(numFactor<3)
flag= false;
else
for(i=0;i<numFactor;i++)
if(i!=numFactor-1&&fact[i]==fact[i+1])
flag= false;

return flag;
}

``````

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

Re: 10006 - Carmichael Numbers

Really? Did you even test your program? I think, no:

ivank@zoidberg:~/contest\$ xsel -b >p.cc # - this pastes your code into file p.cc
ivank@zoidberg:~/contest\$ g++ -O2 -o p p.cc
ivank@zoidberg:~/contest\$ seq 1 65000 | ./p | grep Carmichael | head
The number 75 is a Carmichael number.
The number 105 is a Carmichael number.
The number 147 is a Carmichael number.
The number 165 is a Carmichael number.
The number 195 is a Carmichael number.
The number 231 is a Carmichael number.
The number 245 is a Carmichael number.
The number 255 is a Carmichael number.
The number 273 is a Carmichael number.
The number 285 is a Carmichael number.
ivank@zoidberg:~/contest\$

blackSajia
New poster
Posts: 4
Joined: Tue Nov 11, 2008 12:14 pm

Re: 10006 - Carmichael Numbers

Thankssssssssss to mf. Finally got AC.

dipal
New poster
Posts: 4
Joined: Mon Apr 27, 2009 9:23 am
Location: BUET

10006 - Carmichael Numbers

Hi,
i accepted this pro 0.036s using find a num carmichael or not;
but when i precalculate these and output at O(1) time then i got 0.028 s.

if u chk the statistics of it then u find 0.000 .008 0.012 and .....

but how this is possible ??

Please some one explain it.
Its a Mystery to me...

thnx

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

Re: 10006 - Carmichael Numbers

Please don't abbreviate English words, it's just rude!

When computational time in a problem is insignificant, you shouldn't forget about I/O time. scanf/printf is faster that C++'s iostream. And custom-made input/output routines, directly talking to the OS (for example, via mmap()) can be faster than scanf/printf.

dipal
New poster
Posts: 4
Joined: Mon Apr 27, 2009 9:23 am
Location: BUET

Re: 10006 - Carmichael Numbers

Please don't abbreviate English words, it's just rude!

sorry for it.

actually i used scanf/printf .
thnx for reply.

cse.mehedi
New poster
Posts: 36
Joined: Sun Mar 18, 2012 8:18 am

10006 WA. Help Me!

Code: Select all

``````    #include<stdio.h>
#include<math.h>
#define M 80000

char prime[M];

int main()
{
long n,i,c,l,flag;
sieve();
while(1)
{
scanf("%ld",&n); if(n==0) break;
printf("AC");
}
return 0;
}

``````
Last edited by cse.mehedi on Fri Sep 07, 2012 8:08 pm, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10006 WA. Help Me!

30 is normal.
Check input and AC output for thousands of problems on uDebug!

cse.mehedi
New poster
Posts: 36
Joined: Sun Mar 18, 2012 8:18 am

Re: 10006 WA. Help Me!

brianfry713 wrote:30 is normal.
i changed but again WA!