mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > gophne

Reply
 
Thread Tools
Old 2017-12-27, 23:11   #34
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

32·5·13·17 Posts
Default

Quote:
Originally Posted by guptadeva View Post
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 View Post
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
chalsall is offline   Reply With Quote
Old 2017-12-28, 06:54   #35
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

263016 Posts
Default

@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
LaurV is offline   Reply With Quote
Old 2017-12-28, 10:02   #36
gophne
 
Feb 2017

3·5·11 Posts
Unhappy 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.
gophne is offline   Reply With Quote
Old 2017-12-28, 11:45   #37
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

23·5·157 Posts
Default

Quote:
Originally Posted by gophne View Post
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.
retina is offline   Reply With Quote
Old 2017-12-28, 12:02   #38
guptadeva
 
Dec 2017

2×52 Posts
Default

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 ?

Click image for larger version

Name:	sundaram.jpg
Views:	132
Size:	101.3 KB
ID:	17418

Last fiddled with by guptadeva on 2017-12-28 at 12:39
guptadeva is offline   Reply With Quote
Old 2017-12-28, 12:08   #39
jnml
 
Feb 2012
Prague, Czech Republ

22×32×5 Posts
Default

Quote:
Originally Posted by gophne View Post
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>
jnml is offline   Reply With Quote
Old 2017-12-28, 13:29   #40
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

230608 Posts
Default

Quote:
Originally Posted by gophne View Post
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
LaurV is offline   Reply With Quote
Old 2017-12-28, 13:48   #41
jnml
 
Feb 2012
Prague, Czech Republ

22×32×5 Posts
Default

Quote:
Originally Posted by LaurV View Post
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 is offline   Reply With Quote
Old 2017-12-28, 14:06   #42
jnml
 
Feb 2012
Prague, Czech Republ

2648 Posts
Default

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>
jnml is offline   Reply With Quote
Old 2017-12-28, 14:14   #43
guptadeva
 
Dec 2017

2·52 Posts
Default

very nice

Last fiddled with by guptadeva on 2017-12-28 at 14:16
guptadeva is offline   Reply With Quote
Old 2017-12-28, 15:11   #44
gophne
 
Feb 2017

3·5·11 Posts
Default

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

I shall perservere, without the bravado.
gophne is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
gpuOwL: an OpenCL program for Mersenne primality testing preda GpuOwl 2733 2021-10-13 10:39
GQQ: a "deterministic" "primality" test in O(ln n)^2 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
"New primality proving test from Alex Petrov" ewmayer Math 11 2007-04-23 19:07
P-1 B1/B2 selection with "Test=" vs "Pfactor=" James Heinrich Software 2 2005-03-19 21:58

All times are UTC. The time now is 11:39.


Tue Oct 19 11:39:57 UTC 2021 up 88 days, 6:08, 0 users, load averages: 0.80, 0.94, 1.10

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.