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

Post by Moshiur Rahman » Tue Sep 09, 2008 7:32 am

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

Post by alirezanoori » Wed Feb 11, 2009 2:22 pm

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

Post by mf » Wed Feb 11, 2009 4:05 pm

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

Post by alirezanoori » Wed Feb 11, 2009 11:30 pm

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

Post by mf » Thu Feb 12, 2009 9:38 am

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

Post by alirezanoori » Thu Feb 12, 2009 5:55 pm

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

Post by blackSajia » Mon Feb 23, 2009 11:47 pm

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

Post by mf » Mon Feb 23, 2009 11:58 pm

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

Post by blackSajia » Sat Feb 28, 2009 9:11 pm

Thankssssssssss to mf. Finally got AC. :lol: :lol: :lol:

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

10006 - Carmichael Numbers

Post by dipal » Tue Jun 09, 2009 8:02 pm

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

Post by mf » Wed Jun 10, 2009 10:53 pm

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

Post by dipal » Mon Jun 15, 2009 8:53 am

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!

Post by cse.mehedi » Mon Sep 03, 2012 2:20 am

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!

Post by brianfry713 » Wed Sep 05, 2012 1:51 am

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!

Post by cse.mehedi » Fri Sep 07, 2012 7:10 pm

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

Post Reply

Return to “Volume 100 (10000-10099)”