My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree6Thanks
Reply
 
LinkBack Thread Tools Display Modes
October 8th, 2015, 08:05 AM   #1
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

New primality test

This primality test is different from Fermat test :
n=561 which is a Carmichael number fail this test.
So I still do not know if some numbers fail this test.
Are they finite or no?
Thank you for listing the first numbers failing this test.
Thank you.


n positive odd integer > 3

Let us define a function S(k)

S(n)=2^n
S(n-1)=S(n)-(2^n-1)
S(n-2)=S(n-1)+(2^n-2)
S(n-3)=S(n-2)-(2^n-3)
....
S(0)=S(1)+ or - (2^0)

We start with the sign + and we alternate -+-+-+....

Example n=5

S(5)=2^5=32
S(4)=2^5-2^4=32-16=16
S(3)=16+2^3=24
S(2)=24-2^2=20
S(1)=20+2=22
S(0)=22-(2^0)=22-1=21

Here is the algorithm :

1. Compute S(2)
2. Compute gcd(n,S(2)
If 1<gcd(n,S(2))<n then n is composite print "n is composite" otherwise next step
3. Compute S(2) mod n
If S(2) mod n = 0 then n is prime print "n is prime" otherwise n is composite
4. End
mobel is offline  
 
October 8th, 2015, 09:30 AM   #2
Member
 
Joined: Oct 2013

Posts: 60
Thanks: 6

Here's your Code

Code:
ismobel(n)={   \\returns 1, if n is a (pseudo)prime, otherwise 0.
  my(s2=sum(x=2,n,2^x*(-1)^(x-1)),n1=gcd(n,s2));
  if(n1>1&&n1<n,return(0),s2%n==0,return(1))
}
Testing for pseudoprimes up to 10^4 results in

Code:
for(n=4,10^4,if(isprime(n)<>ismobel(n),print(n)));

4
341
946
1105
1387
1729
2047
2465
2701
2821
3277
4033
4369
4681
5461
6601
7957
8321
8911
time = 20,661 ms.
amazingly 561 is not in the list
Thanks from mobel
Martin Hopf is offline  
October 8th, 2015, 09:35 AM   #3
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Thank you.
It seems that there is an infinite number of those failing the test.
So I see no need to find a close formula for computing S(2) without going through all the values from n to 2.
Gcd(n,S(2)) seems unuseful then.


Thank you very much.
mobel is offline  
October 8th, 2015, 09:37 AM   #4
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

Only odd numbers so 4 and 946 does noy count.
mobel is offline  
October 8th, 2015, 09:48 AM   #5
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Interesting. This seems to be very similar to a base-2 Fermat test combined with a divisibility by 3 test.
CRGreathouse is offline  
October 8th, 2015, 09:57 AM   #6
Member
 
Joined: Oct 2013

Posts: 60
Thanks: 6

I misssed to filter the Test for odd numbers!
946 seems to be the only even pseudoprime for n>4.
And 561 is missing as gcd(s2,561)=187
Martin Hopf is offline  
October 8th, 2015, 10:18 AM   #7
Member
 
Joined: Oct 2013

Posts: 60
Thanks: 6

Quote:
Interesting. This seems to be very similar to a base-2 Fermat test combined with a divisibility by 3 test.
Yes, I think in the same way. A subset of A001567

Code:
forstep(n=5,3*10^4,2,if(isprime(n)<>ismobel(n),print1(n,", ")));
341, 1105, 1387, 1729, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4681, 5461,
6601, 7957, 8321, 8911, 10261, 10585, 11305, 13741, 13747, 13981, 14491,
15709, 15841, 16705, 18721, 19951, 23377, 29341
time = 3min, 11,981 ms.
Thanks from CRGreathouse
Martin Hopf is offline  
October 8th, 2015, 10:22 AM   #8
Banned Camp
 
Joined: Dec 2013

Posts: 1,117
Thanks: 41

There is still a room for improving the test.
First : finding close formula for computing S(2)
Second : analyzing the numbers failing the test. We could then reach almost 100% success

I`m still thinking on how to do ti.
If you have any idea let us improve the test.
mobel is offline  
October 8th, 2015, 10:22 AM   #9
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by Martin Hopf View Post
I misssed to filter the Test for odd numbers!
946 seems to be the only even pseudoprime for n>4.
I find also 25156 and 66788.
Thanks from Martin Hopf
CRGreathouse is offline  
October 8th, 2015, 10:26 AM   #10
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by Martin Hopf View Post
Yes, I think in the same way. A subset of A001567
Or better yet
https://oeis.org/A066488
which shows that Robert G. Wilson v had considered this at least 13 years ago.

On the plus side, this gives a really quick version of the test (see the 2011 comment or the 2013 program). On the minus, this suggests that strengthening it will be hard.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
primality, test



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primality test using combinations Mouhaha Number Theory 6 June 6th, 2017 10:58 AM
Primality test Ąż!? mathbalarka Number Theory 1 June 2nd, 2012 04:59 PM
New primality test? Bogauss Number Theory 19 May 24th, 2012 10:26 AM
New primality test momo Number Theory 21 May 2nd, 2009 02:44 PM
Check this primality test please momo Number Theory 16 April 9th, 2009 04:57 PM





Copyright © 2019 My Math Forum. All rights reserved.