October 8th, 2015, 07: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(n1)=S(n)(2^n1) S(n2)=S(n1)+(2^n2) S(n3)=S(n2)(2^n3) .... 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^52^4=3216=16 S(3)=16+2^3=24 S(2)=242^2=20 S(1)=20+2=22 S(0)=22(2^0)=221=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 
October 8th, 2015, 08: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)^(x1)),n1=gcd(n,s2)); if(n1>1&&n1<n,return(0),s2%n==0,return(1)) } 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. 
October 8th, 2015, 08: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. 
October 8th, 2015, 08:37 AM  #4 
Banned Camp Joined: Dec 2013 Posts: 1,117 Thanks: 41 
Only odd numbers so 4 and 946 does noy count.

October 8th, 2015, 08:48 AM  #5 
Global Moderator 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 base2 Fermat test combined with a divisibility by 3 test.

October 8th, 2015, 08: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 
October 8th, 2015, 09:18 AM  #7  
Member Joined: Oct 2013 Posts: 60 Thanks: 6  Quote:
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.  
October 8th, 2015, 09: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. 
October 8th, 2015, 09:22 AM  #9 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  
October 8th, 2015, 09:26 AM  #10  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Quote:
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.  

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 09:58 AM 
Primality test Ąż!?  mathbalarka  Number Theory  1  June 2nd, 2012 03:59 PM 
New primality test?  Bogauss  Number Theory  19  May 24th, 2012 09:26 AM 
New primality test  momo  Number Theory  21  May 2nd, 2009 01:44 PM 
Check this primality test please  momo  Number Theory  16  April 9th, 2009 03:57 PM 