473,326 Members | 2,133 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

primes with Child's Binomial Theorem

theorem states that:
Integer n is prime if and only if (x +1)^n ≡ x^n +1 (mod n) in Z[x].

so I testing it, but values doesn't match ... and I don't se why.. I
guess :) it's some thing wrong in my implementation...
hope you can help out :)

#include <stdlib.h>
#include <stdio.h>

void id_prime(int i);
int power (int base, int n) ;

int i, p ;
int index = 0;
int expect[16] = {1, 2, 3 ,5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47};

int main(void)
{
int i;
for(i=1;i<50;i++)
{
id_prime(i);
}

return 0;

}
void id_prime(int i)
{
if( (power((4+1), i) % i) == ((power(4, i) +1) % i))
{
printf("PRIME :%d", i);
printf(" EXPECTED : %d\n", expect[index]);
index++;
}
}

int power (int base, int n)
{

p = 1;
for (i = 1; i <= n; ++i)
p *= base;
return p;
}
Mar 24 '07 #1
5 2426
Integer n is prime if and only if (x +1)^n ≡ x^n +1 (mod n) in Z[x].

In theorem, x must be integer , but do not say all integer satisfy
this condition. Theorem means , for all prime numbers there is an
integer (x) that satisfy this therom.
if( (power((4+1), i) % i) == ((power(4, i) +1) % i))
In here i must be constant ( not c language as in maths ) then find x
like this

for ( i = 0 ; i < 16 ; ++i )
for ( j = 1 ; j < 1000 ; ++j )
{
if( (power((j+1), expect[i]) % expect[i]) == ((power(j,
expect[i]) +1) % expect[i]))
{
// I found it
printf ( "%d", j );
break;
}
}

Erdinç Taşkın
erdinctaskin.blogspot.com
-----------------
On 24 Mart, 13:22, Carramba <u...@example.netwrote:
theorem states that:
Integer n is prime if and only if (x +1)^n ≡ x^n +1 (mod n) in Z[x].

so I testing it, but values doesn't match ... and I don't se why.. I
guess :) it's some thing wrong in my implementation...
hope you can help out :)

#include <stdlib.h>
#include <stdio.h>

void id_prime(int i);
int power (int base, int n) ;

int i, p ;
int index = 0;
int expect[16] = {1, 2, 3 ,5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47};

int main(void)
{
int i;
for(i=1;i<50;i++)
{
id_prime(i);
}

return 0;

}

void id_prime(int i)
{
if( (power((4+1), i) % i) == ((power(4, i) +1) % i))
{
printf("PRIME :%d", i);
printf(" EXPECTED : %d\n", expect[index]);
index++;
}

}

int power (int base, int n)
{

p = 1;
for (i = 1; i <= n; ++i)
p *= base;
return p;

}

Mar 24 '07 #2
Erdinç wrote:
>Integer n is prime if and only if (x +1)^n ≡ x^n +1 (mod n) inZ[x].
In theorem, x must be integer , but do not say all integer satisfy
this condition. Theorem means , for all prime numbers there is an
integer (x) that satisfy this therom.
thanx!
oh ok, but is there any known integers that I can use?
> if( (power((4+1), i) % i) == ((power(4, i) +1) % i))
In here i must be constant ( not c language as in maths ) then find x
like this

for ( i = 0 ; i < 16 ; ++i )
for ( j = 1 ; j < 1000 ; ++j )
{
if( (power((j+1), expect[i]) % expect[i]) == ((power(j,
expect[i]) +1) % expect[i]))
{
// I found it
printf ( "%d", j );
I have only used expect to by able compare output, in this case program
doesn't generate primes
break;
}
}

Erdinç Taşkın
erdinctaskin.blogspot.com
-----------------
On 24 Mart, 13:22, Carramba <u...@example.netwrote:
>theorem states that:
Integer n is prime if and only if (x +1)^n ≡ x^n +1 (mod n) inZ[x].

so I testing it, but values doesn't match ... and I don't se why.. I
guess :) it's some thing wrong in my implementation...
hope you can help out :)

#include <stdlib.h>
#include <stdio.h>

void id_prime(int i);
int power (int base, int n) ;

int i, p ;
int index = 0;
int expect[16] = {1, 2, 3 ,5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,43,
47};

int main(void)
{
int i;
for(i=1;i<50;i++)
{
id_prime(i);
}

return 0;

}

void id_prime(int i)
{
if( (power((4+1), i) % i) == ((power(4, i) +1) % i))
{
printf("PRIME :%d", i);
printf(" EXPECTED : %d\n", expect[index]);
index++;
}

}

int power (int base, int n)
{

p = 1;
for (i = 1; i <= n; ++i)
p *= base;
return p;

}
Mar 24 '07 #3
On Sat, 24 Mar 2007 12:22:22 +0100, Carramba <us**@example.netwrote:
>theorem states that:
Integer n is prime if and only if (x +1)^n ? x^n +1 (mod n) in Z[x].
What does the '?' mean above? Is it congruent? What is Z[x] and how
does it differ from "normal" arithmetic?

Must it be true for all x or just for some x that you have to find? Is
there any upper limit on x (it doesn't take very long for powers to
exceed the range of an int)?
>
so I testing it, but values doesn't match ... and I don't se why.. I
guess :) it's some thing wrong in my implementation...
hope you can help out :)

#include <stdlib.h>
You don't appear to use this header.
>#include <stdio.h>

void id_prime(int i);
int power (int base, int n) ;

int i, p ;
These two are used only in power and should be defined there.
>int index = 0;
int expect[16] = {1, 2, 3 ,5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47};
These two are used only in id_prime and could (should) be defined
there as static.
>
int main(void)
{
int i;
for(i=1;i<50;i++)
{
id_prime(i);
}

return 0;

}
void id_prime(int i)
{
if( (power((4+1), i) % i) == ((power(4, i) +1) % i))
Is this the way you do arithmetic in Z[x]?
{
printf("PRIME :%d", i);
printf(" EXPECTED : %d\n", expect[index]);
index++;
}
}

int power (int base, int n)
{

p = 1;
Why are you using a global for this?
for (i = 1; i <= n; ++i)
Why another global?
> p *= base;
return p;
}

Remove del for email
Mar 24 '07 #4
Barry Schwarz wrote:
On Sat, 24 Mar 2007 12:22:22 +0100, Carramba <us**@example.netwrote:
>theorem states that:
Integer n is prime if and only if (x +1)^n ? x^n +1 (mod n) in Z[x].

What does the '?' mean above? Is it congruent? What is Z[x] and how
does it differ from "normal" arithmetic?
? just encoding error it should by equivalent

Z[x] means x in Z, were Z is set of integers
Must it be true for all x or just for some x that you have to find? Is
there any upper limit on x (it doesn't take very long for powers to
exceed the range of an int)?
>so I testing it, but values doesn't match ... and I don't se why.. I
guess :) it's some thing wrong in my implementation...
hope you can help out :)

#include <stdlib.h>

You don't appear to use this header.
>#include <stdio.h>

void id_prime(int i);
int power (int base, int n) ;

int i, p ;

These two are used only in power and should be defined there.
>int index = 0;
int expect[16] = {1, 2, 3 ,5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47};

These two are used only in id_prime and could (should) be defined
there as static.
>int main(void)
{
int i;
for(i=1;i<50;i++)
{
id_prime(i);
}

return 0;

}
void id_prime(int i)
{
if( (power((4+1), i) % i) == ((power(4, i) +1) % i))

Is this the way you do arithmetic in Z[x]?
> {
printf("PRIME :%d", i);
printf(" EXPECTED : %d\n", expect[index]);
index++;
}
}

int power (int base, int n)
{

p = 1;

Why are you using a global for this?
> for (i = 1; i <= n; ++i)

Why another global?
> p *= base;
return p;
}


Remove del for email
Mar 25 '07 #5
Carramba wrote:
theorem states that:
Integer n is prime if and only if (x +1)^n ≡ x^n +1 (mod n) in Z[x].

so I testing it, but values doesn't match ... and I don't se why.. I
guess :) it's some thing wrong in my implementation...
hope you can help out :)
If you were to run the following,
#include <stdio.h>

const unsigned testmax = 300;
int main(void)
{
unsigned n, x, lhp, rhp, rhs, ok, j;

for (n = 1; n <= testmax; n++) {
for (x = ok = 0; x <= n; x++) {
for (lhp = rhp = j = 1, rhs = 2; j <= n; j++) {
lhp *= x + 1;
rhp *= x;
lhp %= n;
rhp %= n;
rhs = rhp == n - 1 ? 0 : rhp + 1;
}
if (lhp != rhs) {
ok = 1;
break;
}
}
if (!ok)
printf("%u ok\n", n);
else
printf
("%u fails: (%u+1)^%u = %u (%u), %u^%u +1 == %u"
" (%u).\n",
n, x, n, lhp, n, x, n, rhs, n);

}
return 0;

}
it strongly suggests that the test need only be done for x = 1.
If you can demonstrate that
Integer n is prime if and only if 2^n (mod n) ≡ 2 (mod n),
then this shorter program will suffice (some implementations of printf
are broken; if your lines are too long, yours is one of those):
#include <stdio.h>

const unsigned testmax = 1000;
int main(void)
{
unsigned n, lhp, rhs, ok, j, linepos = 0;
const unsigned linelimit = 60;
for (n = 1; n <= testmax; n++) {
ok = 1;
rhs = 2 % n;
for (lhp = j = 1; j <= n; j++) {
lhp *= 2;
lhp %= n;
}
if (lhp == rhs) {
linepos += printf("%u", n);
if (linepos < linelimit)
putchar(' ');
else {
putchar('\n');
linepos = 0;
}

}
}
if (linepos)
putchar('\n');
return 0;

}


>
#include <stdlib.h>
#include <stdio.h>

void id_prime(int i);
int power (int base, int n) ;

int i, p ;
int index = 0;
int expect[16] = {1, 2, 3 ,5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47};

int main(void)
{
int i;
for(i=1;i<50;i++)
{
id_prime(i);
}

return 0;

}
void id_prime(int i)
{
if( (power((4+1), i) % i) == ((power(4, i) +1) % i))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This is not the way to do this
{
printf("PRIME :%d", i);
printf(" EXPECTED : %d\n", expect[index]);
index++;
}
}

int power (int base, int n)
{

p = 1;
for (i = 1; i <= n; ++i)
p *= base;
return p;
}
Mar 25 '07 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

36
by: Dag | last post by:
Is there a python module that includes functions for working with prime numbers? I mainly need A function that returns the Nth prime number and that returns how many prime numbers are less than N,...
0
by: Ryan M. Keith | last post by:
I am having a problem with the ostream operator in templated classes that I wrote (I'm using the Borland compiler), and I'm certain that the templates are the problem because when I remove the...
2
by: keit6736 | last post by:
Hi, I'm using the Borland compiler and I've created two templated classes in which I've overloaded the ostream << operator. However, when I try and use the operator on objects of either class I...
9
by: uttre | last post by:
hai to all, i did some programming in Lisp (6 months) & next i want to learn C++. i searched all the archives of "comp.lang.c++" & ACCU too & decided "C++ Primer" 3/e as my text book....
7
by: newstips6706 | last post by:
1, 2, 3, 5, 7... PRIME Numbers ________________________________ Definitions What is a PRIME Number ?
13
by: sigmundccs | last post by:
Write a program to load in two integers from the user. Display all the prime numbers between the two integers. i'm a beginner. i'm problem doing this. can anyone teach me ? thanks a lot.
4
by: Busgosu | last post by:
i dont know how to upload in a way that you can see it clearly.. so im just going to copy and paste what i have so far... sorry. :S #include <iostream> using namespace std; #include <cmath>...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.