mersenneforum.org "New" primality test/check
 Register FAQ Search Today's Posts Mark Forums Read

2017-12-27, 23:11   #34
chalsall
If I May

"Chris Halsall"
Sep 2002

22·34·31 Posts

Quote:
 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".

Quote:
 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!

Last fiddled with by chalsall on 2017-12-27 at 23:13

 2017-12-28, 06:54 #35 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 24·613 Posts @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? Last fiddled with by LaurV on 2017-12-28 at 07:08
 2017-12-28, 10:02 #36 gophne   Feb 2017 101001012 Posts Falling on my sword 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.
2017-12-28, 11:45   #37
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2·23·137 Posts

Quote:
 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.

 2017-12-28, 12:02 #38 guptadeva   Dec 2017 3216 Posts 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 ? Last fiddled with by guptadeva on 2017-12-28 at 12:39
2017-12-28, 12:08   #39
jnml

Feb 2012
Prague, Czech Republ

5·37 Posts

Quote:
 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 $M_7$.

$127 = 1 \pmod 9$

but

$(7+1)/2 = 4$.

Some more evaluation (in Go):

Code:
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:

Code:
~/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>

2017-12-28, 13:29   #40
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

265016 Posts

Quote:
 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.
Code:
? 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>

Last fiddled with by LaurV on 2017-12-28 at 13:31

2017-12-28, 13:48   #41
jnml

Feb 2012
Prague, Czech Republ

5×37 Posts

Quote:
 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!

 2017-12-28, 14:06 #42 jnml   Feb 2012 Prague, Czech Republ 101110012 Posts Moar stats Code: ~/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>
 2017-12-28, 14:14 #43 guptadeva   Dec 2017 2·52 Posts very nice Last fiddled with by guptadeva on 2017-12-28 at 14:16
 2017-12-28, 15:11 #44 gophne   Feb 2017 2458 Posts Thank you for the encouragement from everybody, I actually don't deserve it. I shall perservere, without the bravado.

 Similar Threads Thread Thread Starter Forum Replies Last Post preda GpuOwl 2734 2021-11-14 05:33 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33 wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 ewmayer Math 11 2007-04-23 19:07 James Heinrich Software 2 2005-03-19 21:58

All times are UTC. The time now is 09:55.

Wed Dec 1 09:55:58 UTC 2021 up 131 days, 4:24, 1 user, load averages: 1.33, 1.17, 1.14