My Math Forum New primality test

 Number Theory Number Theory Math Forum

 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(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
 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)^(x-1)),n1=gcd(n,s2)); if(n1>1&&n1ismobel(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
 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 base-2 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:
 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.

 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
Quote:
 Originally Posted by Martin Hopf 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.

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:
 Originally Posted by Martin Hopf 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.

 Tags primality, test

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Mouhaha Number Theory 6 June 6th, 2017 09:58 AM mathbalarka Number Theory 1 June 2nd, 2012 03:59 PM Bogauss Number Theory 19 May 24th, 2012 09:26 AM momo Number Theory 21 May 2nd, 2009 01:44 PM momo Number Theory 16 April 9th, 2009 03:57 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top