"New" primality test/check

[chalsall]

Originally Posted by guptadeva

unfortunately in the academic world, there has been a growing tendency to measure scientific progress through 'impact factors' or 'number of publications'.

In the industry, this is referred to as "publish or perish".

Originally Posted by guptadeva

also don't be afraid of making a fool out of yourself by presenting something that can be disproved in a microsecond ... in that case just get over it and find a new algorithm

Agreed. I go out of my way to make a fool out of myself every single day. Or, at least, every second day.

When I don't I feel like I've failed....

Edit: Cross posted with Kieren. But, yeah!

[LaurV]

@OP:
Let me try to make clear what your claim is, in math terms.
You claim:
1. you have a function from primes to booleans (i.e. {true, false}), that is defined as: \(f:P\rightarrow B\) such as \(f(p)=T\) whenever \(2^p-1\) is in \(P\) (i.e is prime) and \(f(p)=F\) otherwise.
2. you tested this function for all primes up to \(p=1\, 257\, 787\) and you didn't get any wrong result (neither false positive, nor false negative)
3. this function of yours can be calculated faster than the LL test

Is that really what you are claiming?
You must be careful with the third point, testing all exponents lower than the exponent of M34 (which is 1257787) is VERY fast with the known algorithms, there are a lot of exponents there, but they are really small... One average computer will need about 3-4 hours to complete all these tests. All together, not each. And using pari/gp, which is very slow, I do not talk here of specialized tools like P95 or so. Did your "formula" take less amount of time?

[gophne]

If it is too good to be true, it is too good to be true.

I have been found out by my lack of math training and hubris. For this I stand accused and am guilty. I will consider to leave this site voluntarily and won't post anything again under any name.

The algorith has false positives...apparently when 2^n-1 mod (n+2)= 1/2*(2^n-1)+1, which also happens to correspond to the first encountered mersenne non-primes, for which I could run the sagemath non-commercial software installed on my laptop. I did not pick this up the matrix table/grid that I was working with, which commenced at the first odd prime. The algorithm seemed to hold true for the first few hundred of odd numbers/primes and also seemed to hold for high prime numbers, but the false positives probably rubbishes the algorithm.

I also erred in claiming that the algorithm holds up to M34...the algorithmic relationship of the "mersenne odd number (dividend)" to the "odd number(prime)" in the matrix holds, but the tested prime (divisor) lags exponentially to the mersenne odd number part (dividend) in the modulo relationship. I conflated the dividend and the divisor in my claim w.r.t M34. This of course is a massive deficit, contrary to what I had claimed.

I could not find any case where the tested (odd) prime divisor returned a false value, so it might be that the "primality" function still holds.

The algorithm seems to hold for all non-prime divisors (composites), where the non-prime divisor is not in the form of 2^n-1, with 2^n-1 mod n+2, not equal to 1/2*(2^n-1)+1...(but this is not proven/verified), that is, apparently for the common composite odd number dividors divisible by 3, 5, etc.

So I stand accused and is deserving of any scorn for my outlandish claims never-the-less. I was called "dishonest" on this site before with a previous "algorithm", so I probably deserve this label, very certainly for due diligence.

In my defense I can only say that I am a hobbyist, and that I really thought I had hit onto something big. As far as I could tabulate the matrix table -from which I derived the "modulo formula", the results returned true. The consistency of the table- modulo ~ mersenne odd numers (starting at 1) vs odd numbers (starting at 3), also seemed intrisically logical and consistent, for the first few hundred odd number (modulo divisors).

The algorithm is this:

For x=n (n being an element of the set of odd (positive) number/integers, n=>1), (2^n-1) mod (n+2) is congruant to (n+1)/2 for all odd prime numbers, and non-congruant for all composites (barring false positives!!!!).

Thats it!

The relationship holds up at least (as tested using sagemath) with respect to the dividend/divisor relationship of 1,257,785/1,257,787, for what it is worth.

That is it, that is the algorithm.

I feel ashamed and have made a big fool of myself and the readers by wasting their time. For this I apologise.

[retina]

Originally Posted by gophne

If it is too good to be true, it is too good to be true.

I have been found out by my lack of math training and hubris. For this I stand accused and am guilty. I will consider to leave this site voluntarily and won't post anything again under any name.

The algorith has false positives...apparently when 2^n-1 mod (n+2)= 1/2*(2^n-1)+1, which also happens to correspond to the first encountered mersenne non-primes, for which I could run the sagemath non-commercial software installed on my laptop. I did not pick this up the matrix table/grid that I was working with, which commenced at the first odd prime. The algorithm seemed to hold true for the first few hundred of odd numbers/primes and also seemed to hold for high prime numbers, but the false positives probably rubbishes the algorithm.

I also erred in claiming that the algorithm holds up to M34...the algorithmic relationship of the "mersenne odd number (dividend)" to the "odd number(prime)" in the matrix holds, but the tested prime (divisor) lags exponentially to the mersenne odd number part (dividend) in the modulo relationship. I conflated the dividend and the divisor in my claim w.r.t M34. This of course is a massive deficit, contrary to what I had claimed.

I could not find any case where the tested (odd) prime divisor returned a false value, so it might be that the "primality" function still holds.

The algorithm seems to hold for all non-prime divisors (composites), where the non-prime divisor is not in the form of 2^n-1, with 2^n-1 mod n+2, not equal to 1/2*(2^n-1)+1...(but this is not proven/verified), that is, apparently for the common composite odd number dividors divisible by 3, 5, etc.

So I stand accused and is deserving of any scorn for my outlandish claims never-the-less. I was called "dishonest" on this site before with a previous "algorithm", so I probably deserve this label, very certainly for due diligence.

In my defense I can only say that I am a hobbyist, and that I really thought I had hit onto something big. As far as I could tabulate the matrix table -from which I derived the "modulo formula", the results returned true. The consistency of the table- modulo ~ mersenne odd numers (starting at 1) vs odd numbers (starting at 3), also seemed intrisically logical and consistent, for the first few hundred odd number (modulo divisors).

The algorithm is this:

For x=n (n being an element of the set of odd (positive) number/integers, n=>1), (2^n-1) mod (n+2) is congruant to (n+1)/2 for all odd prime numbers, and non-congruant for all composites (barring false positives!!!!).

Thats it!

The relationship holds up at least (as tested using sagemath) with respect to the dividend/divisor relationship of 1,257,785/1,257,787, for what it is worth.

That is it, that is the algorithm.

I feel ashamed and have made a big fool of myself and the readers by wasting their time. For this I apologise.

Admitting that we are wrong can gain one respect. I see no need for you to crawl away and hide in the corner.

[guptadeva]

don't worry and keep searching and posting !

honestly our insight into the prime numbers is still very limited and every tiny little bit of knowledge is very valuable

so yes, we need fellow-researcher like you who don't only hunt to compute higher and higher primes but also steadily continue to work and struggle to find new relations, theorems, and algorithms - and who knows, maybe someday you might be able to find other wonderful or amazing things on your way ?

attached below is a graphical representation of the sieve of sundaram, where the points plotted are { 2 (i + j + 2ij) + 1 , 2 i +1 }
at the first glance it looks very much like the sieve or eratosthenes, but maybe this fact could also be of inspiration to someone ?

[jnml]

Originally Posted by gophne

The algorithm is this:

For x=n (n being an element of the set of odd (positive) number/integers, n=>1), (2^n-1) mod (n+2) is congruant to (n+1)/2 for all odd prime numbers, and non-congruant for all composites (barring false positives!!!!).

FTR: IIUC, the algorithm fails as soon as for .




but

.

Some more evaluation (in Go):

package main

import (
	"fmt"

	"github.com/cznic/mathutil"
	"github.com/cznic/mathutil/mersenne"
)

func main() {
	fails := 0
	n := uint32(2)
	for n <= mersenne.Knowns[48] {
		n, _ = mathutil.NextPrime(n)
		if (mathutil.ModPowUint32(2, n, (n+2))-1)%((n+1)/2) == 0 {
			if _, ok := mersenne.Known[n]; ok {
				fmt.Printf("M_%d really is prime\n", n)
			} else {
				fails++
			}
		}
	}
	fmt.Printf("False positives: %d\n", fails)
}

Running it:

~/src/tmp/main> go build && time ./main
M_3 really is prime
M_5 really is prime
M_17 really is prime
M_107 really is prime
M_521 really is prime
False positives: 338664

real	0m4.744s
user	0m4.735s
sys	0m0.004s
~/src/tmp/main>

[LaurV]

Originally Posted by gophne

I will consider to leave this site voluntarily and won't post anything again under any name.

Now, that is not necessary! We all make mistakes, and as other people here said, recognizing when we make mistakes and willing to learn from it is a big quality of a person. We wish you to stay, and continue to play with numbers, maybe read some more theory, and in the future you may really find something worthy.

About that "quality of a person" for example, (hehe) I was one order of magnitude off with the estimation of the time that one will need to test all mersenne numbers with a prime exponent up to e(M34) with LL test, in pari. One will need not 3-4 days, but maybe 30-40 days, with a 4 core computer. The tests in the 1.2 millions take close to one hour each... (this was not really a miscalculation, but mostly trying to lay a trap for you, hehe)

Whatever, here is some pari/gp code if you want to try how this works, install pari and play with it... The ctrl+c was pressed after about 5 minutes.

? lucas(p)=my(m=1<<p-1, s=Mod(4,m)); for(i=3,p,s=s^2-2); s==0
%1 = (p)->my(m=1<<p-1,s=Mod(4,m));for(i=3,p,s=s^2-2);s==0
? cnt=1; for(p=3,1257787,if((l=lucas(p))>0,cnt++; print(cnt": 2^"p"-1 is prime"), printf("...%d...%c",p,13)))
2: 2^3-1 is prime
3: 2^5-1 is prime
4: 2^7-1 is prime
5: 2^13-1 is prime
6: 2^17-1 is prime
7: 2^19-1 is prime
8: 2^31-1 is prime
9: 2^61-1 is prime
10: 2^89-1 is prime
11: 2^107-1 is prime
12: 2^127-1 is prime
13: 2^521-1 is prime
14: 2^607-1 is prime
15: 2^1279-1 is prime
16: 2^2203-1 is prime
17: 2^2281-1 is prime
18: 2^3217-1 is prime
19: 2^4253-1 is prime
20: 2^4423-1 is prime
...7450...
  
  ***   at top-level: ...=1;for(p=3,1257787,if((l=lucas(p))>0,cnt++;pr
  ***                                             ^--------------------
  ***   in function lucas: ...od(4,m));for(i=3,p,s=s^2-2);s==0
  ***                                                  ^-------
  ***   user interrupt after 5min, 12,328 ms
  ***   Break loop: <Return> to continue; 'break' to go back to GP prompt
break>

[jnml]

Originally Posted by LaurV

Now, that is not necessary! We all make mistakes, and as other people here said, recognizing when we make mistakes and willing to learn from it is a big quality of a person. We wish you to stay, and continue to play with numbers, maybe read some more theory, and in the future you may really find something worthy.

I concur.

Additionally, the method gives the correct answer in 92.21% cases up to M49 and as a single test can be done in about a microsecond, it would be actually very valuable! The "only" problem are the 43 false negatives.

What I mean is you might want to look at those false negatives and maybe you can figure out a refinement that gets rid of them (false positives are ok for some low rates). Good luck!

[jnml]

Moar stats

~/src/tmp/main> go build && time ./main
False negatives:       43
False positives:   338664
Correct results:  4011894
Prime exponents:  4350601 (tests performed)
Last exponent:   74207297

real	0m4.821s
user	0m4.814s
sys	0m0.008s
~/src/tmp/main>

[guptadeva]

very nice

[gophne]

Thank you for the encouragement from everybody, I actually don't deserve it.

I shall perservere, without the bravado.