20171227, 23:11  #34  
If I May
"Chris Halsall"
Sep 2002
Barbados
9845_{10} Posts 
Quote:
Quote:
When I don't I feel like I've failed.... Edit: Cross posted with Kieren. But, yeah! Last fiddled with by chalsall on 20171227 at 23:13 

20171228, 06:54  #35 
Romulan Interpreter
Jun 2011
Thailand
2·3·5^{3}·13 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^p1\) 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 34 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 20171228 at 07:08 
20171228, 10:02  #36 
Feb 2017
3·5·11 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^n1 mod (n+2)= 1/2*(2^n1)+1, which also happens to correspond to the first encountered mersenne nonprimes, for which I could run the sagemath noncommercial 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 nonprime divisors (composites), where the nonprime divisor is not in the form of 2^n1, with 2^n1 mod n+2, not equal to 1/2*(2^n1)+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 nevertheless. 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^n1) mod (n+2) is congruant to (n+1)/2 for all odd prime numbers, and noncongruant 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. 
20171228, 11:45  #37  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2×3×7×149 Posts 
Quote:


20171228, 12:02  #38 
Dec 2017
2×5^{2} 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 fellowresearcher 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 20171228 at 12:39 
20171228, 12:08  #39  
Feb 2012
Prague, Czech Republ
264_{8} Posts 
Quote:
but . 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) } 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> 

20171228, 13:29  #40  
Romulan Interpreter
Jun 2011
Thailand
2×3×5^{3}×13 Posts 
Quote:
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 34 days, but maybe 3040 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<<p1, s=Mod(4,m)); for(i=3,p,s=s^22); s==0 %1 = (p)>my(m=1<<p1,s=Mod(4,m));for(i=3,p,s=s^22);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^31 is prime 3: 2^51 is prime 4: 2^71 is prime 5: 2^131 is prime 6: 2^171 is prime 7: 2^191 is prime 8: 2^311 is prime 9: 2^611 is prime 10: 2^891 is prime 11: 2^1071 is prime 12: 2^1271 is prime 13: 2^5211 is prime 14: 2^6071 is prime 15: 2^12791 is prime 16: 2^22031 is prime 17: 2^22811 is prime 18: 2^32171 is prime 19: 2^42531 is prime 20: 2^44231 is prime ...7450... *** at toplevel: ...=1;for(p=3,1257787,if((l=lucas(p))>0,cnt++;pr *** ^ *** in function lucas: ...od(4,m));for(i=3,p,s=s^22);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 20171228 at 13:31 

20171228, 13:48  #41  
Feb 2012
Prague, Czech Republ
2^{2}×3^{2}×5 Posts 
Quote:
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! 

20171228, 14:06  #42 
Feb 2012
Prague, Czech Republ
2^{2}×3^{2}×5 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> 
20171228, 14:14  #43 
Dec 2017
2×5^{2} Posts 
very nice
Last fiddled with by guptadeva on 20171228 at 14:16 
20171228, 15:11  #44 
Feb 2017
3·5·11 Posts 
Thank you for the encouragement from everybody, I actually don't deserve it.
I shall perservere, without the bravado. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
gpuOwL: an OpenCL program for Mersenne primality testing  preda  GpuOwl  2730  20210914 13:39 
GQQ: a "deterministic" "primality" test in O(ln n)^2  Chair Zhuang  Miscellaneous Math  21  20180326 22:33 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
"New primality proving test from Alex Petrov"  ewmayer  Math  11  20070423 19:07 
P1 B1/B2 selection with "Test=" vs "Pfactor="  James Heinrich  Software  2  20050319 21:58 