mersenneforum.org (https://www.mersenneforum.org/index.php)
-   gophne (https://www.mersenneforum.org/forumdisplay.php?f=149)
-   -   "New" primality test/check (https://www.mersenneforum.org/showthread.php?t=22838)

 gophne 2017-12-27 03:47

"New" primality test/check

I think that I might have discovered a new "primality" test, as well as a new prime sieve. I think that the primality test might be computer-time friendly as well, as it consists of a simple straight calculation/logic test only. I think it is big. What would be the most appropriate route to submit it to the math community for scrutiny?

 CRGreathouse 2017-12-27 03:57

The usual way to announce a mathematical discovery is to write a paper, push a preprint to the arXiv, then publish the paper. In the fortunate case that the algorithm can be coded easily I would recommend programming a reference implementation and including the timing results in the preprint and paper. If they improve on the current state of the art, it might be worth posting a note to NMBRTHRY while you're writing the paper. (Since you're here, you could also post timings here; depending on what they are we could advise further.)

 gophne 2017-12-27 04:35

Thanks CRGreathouse.

I had previous attempts at prime innovation on this site, with a bit of embarrassing results!

I am a hobbyist only, and have made some interesting discoveries (using hobbyist approach of "go where my fancy takes me"). I think my present "test" is indeed interesting and had not found anything like it in the "primality" literature, especially on the internet as well -not to say that it is unique/new, but submitting it would of course quickly verify the authenticity of the system/test in a split second.

I was thinking of submitting the "test" on this forum, but I could write a "paper" as I can ask my son/daughter (who is more competent w.r.t writing academic papers) to assist if required.

I am really exited, but it could of course turn out to be a damp squib as well.

 CRGreathouse 2017-12-27 05:11

[QUOTE=gophne;474954]I had previous attempts at prime innovation on this site, with a bit of embarrassing results![/QUOTE]

In that case I'd suggest doing the same again: show what you have and let the forum give feedback. If it's good they can give you advice on how to prepare the work for publication, if not you're saved the effort and possible embarrassment.

Here are some things we (and others) would likely be interested in checking:[list][*] Is the description clear enough that we can understand the intended algorithm?[*] Does it classify all primes as prime?[*] Does it classify all composites as composite?[*] Does it run in reasonable time on average primes?[*] Does it run in reasonable time on worst-case primes?[*] Can you prove the above claims?[*] Is the algorithm easy to implement?[/list]

 rogue 2017-12-27 14:14

Can you write a computer algorithm to execute the test? If so, have you tested it against known primes and composites? Do you know how fast/slow the test is compared to other primality tests? Can it be used as a primality test for numbers of any form?

 gophne 2017-12-27 18:11

New Frontier

Hi CRGreathouse

The algorithm is very clear.
ALL primes are covered- tested to M34 -2^1,257,787-1, Seriously!
ALL composites are identified!
Time O(log n) -Very very fast. Serious.
ALL primes are defined -NO false primes expected as per algorithm logic.
The algorith is a logical formulation, so can be verified quickly.
If authenticated, will compare to simplicity of Euclid's Proof for Infinite number of Primes.
If true, will be a new frontier in PNT

Call me crazy

 chalsall 2017-12-27 18:31

[QUOTE=gophne;474993]The algorithm is very clear.[/QUOTE]

Under US of A law, an algorithm cannot be patented. So, you are unlikely to make any money from this discovery directly.

On the other hand, this would be a ground breaking discovery if it was true.

Why don't you give us the algorithm so the experts here can vet it?

 gophne 2017-12-27 18:34

Grease lightning

Hi Rogue

Yes, I run the algorithm in SAGE. Time, is the time needed in SAGE to caculate straight math formula/logic test, of course involving very large numbers. I tested M34 -2^1,257,787-1. I won't mention the time taken as I will be debarred from this site. (I use a Intel(R) Core(TM)2 CPU T5500 @ 1.66 GHz 1.67 GHz RAM 2.00 GB, 64 bit O/S x64 based processor).

I have tested it to M34. If vindicated, the algorithm will replace GIMP. (Your are allowed to scream out in vexation at this point w.r.t the claims I am making...I don't expect anybody to consider my claims seriously at this stage -I am looking for the best way to submit my algorith/system

Tests ALL known Primes...it is that surreal.

The algorithm maps ALL primes in sequence.

Now you can release your breath and burst out laughing!!!

 gophne 2017-12-27 18:47

[QUOTE=chalsall;474995]Under US of A law, an algorithm cannot be patented. So, you are unlikely to make any money from this discovery directly.

On the other hand, this would be a ground breaking discovery if it was true.

Why don't you give us the algorithm so the experts here can vet it?[/QUOTE]
Hi Chalsall

That was my intention, to submit the algorithm to the world on this site, with the advantage that the algorithm will be ripped to pieces in a matter of micro seconds, if it is a hoax, with myself probable banned for life from this site, if not any other serious math site.

However, I would like to believe that a Site such as this would be able to offer me some sort of protection of my work/intellectual property, even if is open source.

If the algorithm is confirmed, this would have a serious implication on Prime Number Theory.

This is my dilemma.

 gophne 2017-12-27 18:51

Post erased as it was a duplicate of #9. Apologies.

[QUOTE=gophne;474951]What would be the most appropriate route to submit it to the math community for scrutiny?[/QUOTE]

the mathematical community was the first scientific group to understand, that classical publications in books, journals or other printed media has limits.

you could always publish your results in arxiv ([URL]https://arxiv.org/help/submit[/URL]) and/or here in mersenneforum where the density of prime experts is very high and where you would get deep and quick feedback needed to determine the future of your new primality check ...

 jnml 2017-12-27 19:11

[QUOTE=gophne;474993]Hi CRGreathouse

Time O(log n) -Very very fast. Serious.

Call me crazy[/QUOTE]

What do you mean by [TEX]n[/TEX]? Is it the [TEX]n[/TEX] in [TEX]2^n-1[/TEX] or something else?

 bsquared 2017-12-27 19:12

[QUOTE=gophne;475000]
That was my intention, to submit the algorithm to the world on this site, with the advantage that the algorithm will be ripped to pieces in a matter of micro seconds, if it is a hoax, with myself probably banned for life from this site, if not all other serious math sites as well.
[/QUOTE]

Posting an algorithm is not a reason to institute a ban, hoax or otherwise (short of it being some sort of obfuscated malicious fork-bomb algorithm or something).

In fact, open dialog about math, primes, and code is encouraged! It is how we all learn.

 Batalov 2017-12-27 19:13

[QUOTE=gophne;474993]
[COLOR="Red"]ALL primes are covered- tested to M34 -2^1,257,787-1[/COLOR], Seriously!
ALL composites are identified!

Call me crazy[/QUOTE]
Ok, if you insist. You are crazy, dude.
"You tested all primes" to M34. ...oh... oh... allrighty then. :leaving:

 gophne 2017-12-27 19:45

[QUOTE=guptadeva;475003]the mathematical community was the first scientific group to understand, that classical publications in books, journals or other printed media has limits.

you could always publish your results in arxiv ([URL]https://arxiv.org/help/submit[/URL]) and/or here in mersenneforum where the density of prime experts is very high and where you would get deep and quick feedback needed to determine the future of your new primality check ...[/QUOTE]

I will try arXiv then.

I will start to prepare the submission to as professional a level as I can manage on the Site. Time frame should be 2 weeks to a month, if I consider all the implications going forward.

Should I include the background development of the algorithm, tables, the logic of the algorithm as well.

The actual algorithm/formula is concise and straight forward and only involves an inherent relationship between odd numbers and prime numbers. I said previously that it would be Euclidian in nature.

My only concern is that I would like to be advanced some kind of intellectual protection, although I would like to share the discovery on an open source basis.

Is this too much to ask?

 gophne 2017-12-27 19:56

[QUOTE=Batalov;475007]Ok, if you insist. You are crazy, dude.
"You tested all primes" to M34. ...oh... oh... allrighty then. :leaving:[/QUOTE]
Hi Batalov

I don't blame you for your skeptisism.

Did you ever hear about a guy called Archimedes?

I hear your incredulity about testing M34 - IT IS CRAZY!....wait for it.

But console yourself....I share your incredulity from where you come from being a serious mathematician. But I would like to believe amazing discoveries have been made in the course of history and will continue to be made into the future.

I beg of you only to wait then for the submission of the algorithm...then to rip it apart...but I suspect you will be disappointed in this.

 gophne 2017-12-27 20:00

[QUOTE=jnml;475005]What do you mean by [TEX]n[/TEX]? Is it the [TEX]n[/TEX] in [TEX]2^n-1[/TEX] or something else?[/QUOTE]
Mersenne primes are involved in the algorithm.

 jnml 2017-12-27 20:02

[QUOTE=gophne;475014]Hi Batalov

I don't blame you for your skeptisism.

Did you ever hear about a guy called Archimedes?

I hear your incredulity about testing M34 - IT IS CRAZY!....wait for it.

But console yourself....I share your incredulity from where you come from being a serious mathematician. But I would like to believe amazing discoveries have been made in the course of history and will continue to be made into the future.

I beg of you only to wait then for the submission of the algorithm...then to rip it apart...but I suspect you will be disappointed in this.[/QUOTE]

Testing M34 is easy. But you've claimed something different, ie. to test all primes to M34. Do you realize what number of tests you're even talking about?

And what about that complexity question of mine?

 chalsall 2017-12-27 20:04

[QUOTE=gophne;474999]However, I would like to believe that a Site such as this would be able to offer me some sort of protection of my work/intellectual property, even if is open source. This is my dilemma.[/QUOTE]

There is no dilemma. Publishing here would prove that you are the original discoverer.

If you look at the bottom of this page (and every other page on this site) you will see a GNU Free Documentation License. Thus, as the author, you maintain copyright and must be credited for any duplication.

Iff this turns out to be true, you'll go down in history. If it isn't, you won't be banned. Being incorrect is encouraged around here; it's how everyone learns.

 jnml 2017-12-27 20:06

[QUOTE=chalsall;475019]There is no dilemma. Publishing here would prove that you are the original discoverer.

If you look at the bottom of this page (and every other page on this site) you will see a GNU Free Documentation License. Thus, as the author, you maintain copyright and must be credited for any duplication.

Iff this turns out to be true, you'll go down in history. If it isn't, you won't be banned. Being incorrect is encouraged around here; it's how everyone learns.[/QUOTE]

Agreed, but hand-waving not so much.

 gophne 2017-12-27 20:06

[QUOTE=Batalov;475007]Ok, if you insist. You are crazy, dude.
"You tested all primes" to M34. ...oh... oh... allrighty then. :leaving:[/QUOTE]
Hi Batalov

Your point about testing all primes to M34...of course being humongous number, let alone the possible "missing" large primes...but this statement relates to the logic of the algorithm. You don't have to count to infinity to know that x+1 follows x at any point of the set of let us say "integers".

I really value you input, as I would consider any other approach to be naive to a large degree with respect to the claims being made.

 gophne 2017-12-27 20:11

[QUOTE=jnml;475020]Agreed, but hand-waving not so much.[/QUOTE]
See my reply #21 to Batalov w.r.t to testing "all" primes to M34.

I said the algorithm is mindblowingly simple...it involves an (elusive) prime relationship.

 jnml 2017-12-27 20:16

[QUOTE=gophne;475022]See my reply #21 to Batalov w.r.t to testing "all" primes to M34.

I said the algorithm is mindblowingly simple...it involves an (elusive) prime relationship.[/QUOTE]

Just show the proof. It's that simple.

 gophne 2017-12-27 20:25

[QUOTE=chalsall;475019]There is no dilemma. Publishing here would prove that you are the original discoverer.

If you look at the bottom of this page (and every other page on this site) you will see a GNU Free Documentation License. Thus, as the author, you maintain copyright and must be credited for any duplication.

Iff this turns out to be true, you'll go down in history. If it isn't, you won't be banned. Being incorrect is encouraged around here; it's how everyone learns.[/QUOTE]
Hi chalsall

Thanks so much for this assurance, this is very comforting. Thanks also for the general positivity...I would not expect anything but derision, because the claims are gargantuan.

I am well aware that I am setting up a theatre of increduality with this spiel (involving respected mathematians), but I am not a fraud looking for notoriety. I am a serious prime researcher in my own way. I have been busy with prime research since my school days and has been spending many hours in research/hobby in my spare time.

So all I can say is that I am not a confidence trickster and I fully aware of the seriousness of making such a claim. Time will tell.

 chalsall 2017-12-27 20:36

[QUOTE=gophne;475024]Time will tell.[/QUOTE]

Publish. And then we all will know.

 gophne 2017-12-27 20:37

[QUOTE=jnml;475023]Just show the proof. It's that simple.[/QUOTE]
Noted. Please just give me a little bit of time to double check the algorithm for obvious errors and typos, etc. I have committed to post asap.

 gophne 2017-12-27 20:42

[QUOTE=chalsall;475026]Publish. And then we all will know.[/QUOTE]
Noted. I will post asap.

Will do editing of the algorithm to fit onto arXiv forum.

I can possibly post within the next week or two given the feedback and comments from the users w.r.t site protocols.

 chalsall 2017-12-27 21:01

[QUOTE=gophne;475030]I can possibly post within the next week or two given the feedback and comments from the users w.r.t site protocols.[/QUOTE]

This is already sounding a bit fishy. But I still have hope.

Two last pieces of advise: publish under your own name, and consult a lawyer to make sure you maintain copyright (what I said above about the GNU Free Documentation License is true, but it is always good to get an independent second opinion).

 gophne 2017-12-27 21:53

[QUOTE=chalsall;475035]This is already sounding a bit fishy. But I still have hope.

Two last pieces of advise: publish under your own name, and consult a lawyer to make sure you maintain copyright (what I said above about the GNU Free Documentation License is true, but it is always good to get an independent second opinion).[/QUOTE]

I am going to stop replying to miscellaneous comments under the circumstances. I will concentrate on posting the algorithm.

I will advise shortly when i will be ready...I don't want to set myself up with an early date, only to fail to deliver, so I rather want to give myself enough time...two to three weeks...to double, triple, quadruple check the algorithm and remove any typo's, bugs, etc.

I think that is fair for what I am claiming, to change the face of primality testing.

I have spoken enough. Next I will either post or indicate when I will post based on the time frame given.

"Tempus volat hora fugit"

 chalsall 2017-12-27 22:06

[QUOTE=gophne;475041]"Tempus volat hora fugit"[/QUOTE]

Est tempus habemus.

first of all, i totally agree with chalsall:

[QUOTE]There is no dilemma. Publishing here would prove that you are the original discoverer.
[/QUOTE]however, i would like to write some words about submitting a paper to arxiv or other online servers :

unfortunately in the academic world, there has been a growing tendency to measure scientific progress through 'impact factors' or 'number of publications'.
grants are primarily given to scientists that may show a high number of publications - no matter if the content is original or not.
in consequence, many authors simply publish rubbish ... a lot of rubbish !

you are in the lucky case of having made a discovery as a hobby-prime-researcher and are not subject to any publishing pressure.

no matter if your algorithm is correct or not, you have already experienced the joy of having made some discovery and this has given you the urge to share this joy with others ...

maybe you have re-discovered something, that has already been known for many years

some time ago a colleague re-discovered a simple continued fraction for pi:

4/pi == 1 + 1^2/(3 + 2^2/(5 + 3^2/(7 + 4^2/(9 + 5^2/(11 + 6^2/(13 + ... ))))))

the fact, that he was not the first to obtain this expression didn't diminish his joy - on the contrary.

maybe your algorithm is flawed or simply wrong ...

many of us here in this forum can only dream of learning to know some new connection between the prime numbers or some simple (elusive) connection between them.

and if cause - don't worry - you will get your credit for any original or novel method no matter if you choose to publish your algorithm here or elsewhere.

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

the choice is yours ...

 science_man_88 2017-12-27 23:04

[url]https://en.m.wikipedia.org/wiki/Sieve_of_Sundaram[/url] is the closest my knowledge would come to what seems to be described.

[QUOTE=guptadeva;475046]first of all, i totally agree with chalsall:

however, i would like to write some words about submitting a paper to arxiv or other online servers :

unfortunately in the academic world, there has been a growing tendency to measure scientific progress through 'impact factors' or 'number of publications'.
grants are primarily given to scientists that may show a high number of publications - no matter if the content is original or not.
in consequence, many authors simply publish rubbish ... a lot of rubbish !

you are in the lucky case of having made a discovery as a hobby-prime-researcher and are not subject to any publishing pressure.

no matter if your algorithm is correct or not, you have already experienced the joy of having made some discovery and this has given you the urge to share this joy with others ...

maybe you have re-discovered something, that has already been known for many years

some time ago a colleague re-discovered a simple continued fraction for pi:

4/pi == 1 + 1^2/(3 + 2^2/(5 + 3^2/(7 + 4^2/(9 + 5^2/(11 + 6^2/(13 + ... ))))))

the fact, that he was not the first to obtain this expression didn't diminish his joy - on the contrary.

maybe your algorithm is flawed or simply wrong ...

many of us here in this forum can only dream of learning to know some new connection between the prime numbers or some simple (elusive) connection between them.

and if cause - don't worry - you will get your credit for any original or novel method no matter if you choose to publish your algorithm here or elsewhere.

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

the choice is yours ...[/QUOTE]
I left the entire quote without editing because I am so affected by it. It is a wonderful, kind, encouraging, and above all, informative post.

Thanks! May your well-considered words calm the waters of the shark tank. :shark:
2nd edit: I do share the sense of "sounding a bit fishy" but that is based on style, as much as anything.

 chalsall 2017-12-27 23:11

[QUOTE=guptadeva;475046]unfortunately in the academic world, there has been a growing tendency to measure scientific progress through 'impact factors' or 'number of publications'.[/QUOTE]

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

[QUOTE=guptadeva;475046]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 :smile:[/QUOTE]

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 2017-12-28 06:54

@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 2017-12-28 10:02

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.

 retina 2017-12-28 11:45

[QUOTE=gophne;475101]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.[/QUOTE]Admitting that we are wrong can gain one respect. I see no need for you to crawl away and hide in the corner. :confused:

1 Attachment(s)
don't worry and keep searching and posting ! :pals:

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 ?

[ATTACH]17418[/ATTACH]

 jnml 2017-12-28 12:08

[QUOTE=gophne;475101]
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!!!!).
[/QUOTE]

FTR: IIUC, the algorithm fails as soon as for [TEX]M_7[/TEX].

[TEX]127 = 1 \pmod 9[/TEX]

but

[TEX](7+1)/2 = 4[/TEX].

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]
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>
[/CODE]

 LaurV 2017-12-28 13:29

[QUOTE=gophne;475101] I will consider to leave this site voluntarily and won't post anything again under any name.
[/QUOTE]
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... [COLOR=white](this was not really a miscalculation, but mostly trying to lay a trap for you, hehe)[/COLOR]

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>[/CODE]

 jnml 2017-12-28 13:48

[QUOTE=LaurV;475116]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.
[/QUOTE]

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 2017-12-28 14:06

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>
[/CODE]

very nice :smile:

 gophne 2017-12-28 15:11

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

I shall perservere, without the bravado.

 gophne 2017-12-28 15:16

[QUOTE=jnml;475127]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>
[/CODE][/QUOTE]
Hi jnml

Can you give me an example of a false negative please that you have found -the target congruant for the algorithm always being 1/2*(n+1)

 gophne 2017-12-28 15:22

[QUOTE=jnml;475127]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>
[/CODE][/QUOTE]
Hi jnml

How far are you able to test the "divisor" using this algorithm, using your software, and how long does it take? My hunch is that it would be limited due to the exponential relationship between the dividend and the divisor in the algorithm?

 jnml 2017-12-28 15:26

[QUOTE=gophne;475136]
Can you give me an example of a false negative please that you have found -the target congruant for the algorithm always being 1/2*(n+1)[/QUOTE]

[CODE]package main

import (
"fmt"

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

func main() {
var tests, ok, falsePos, falseNeg int
var negs []uint32
n := uint32(2)
for n <= mersenne.Knowns[48] {
n, _ = mathutil.NextPrime(n)
_, prime := mersenne.Known[n]
conj := (mathutil.ModPowUint32(2, n, n+2)-1)%((n+1)/2) == 0
tests++
switch {
case prime == conj:
ok++
case prime:
falseNeg++
negs = append(negs, n)
default:
falsePos++
}
}
fmt.Printf("False negatives: %8d\n", falseNeg)
fmt.Printf("False positives: %8d\n", falsePos)
fmt.Printf("Correct results: %8d\n", ok)
fmt.Printf("Prime exponents: %8d (tests performed)\n", tests)
fmt.Printf("Last exponent: %8d\n", n)
fmt.Println("False negatives:")
for _, v := range negs {
fmt.Printf("\tM_%d\n", v)
}
}
[/CODE]

Run

[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
False negatives:
M_7
M_13
M_19
M_31
M_61
M_89
M_127
M_607
M_1279
M_2203
M_2281
M_3217
M_4253
M_4423
M_9689
M_9941
M_11213
M_19937
M_21701
M_23209
M_44497
M_86243
M_110503
M_132049
M_216091
M_756839
M_859433
M_1257787
M_1398269
M_2976221
M_3021377
M_6972593
M_13466917
M_20996011
M_24036583
M_25964951
M_30402457
M_32582657
M_37156667
M_42643801
M_43112609
M_57885161
M_74207281

real 0m5.063s
user 0m5.059s
sys 0m0.000s
~/src/tmp/main>
[/CODE]

 jnml 2017-12-28 15:30

[QUOTE=gophne;475137]
How far are you able to test the "divisor" using this algorithm, using your software, and how long does it take? My hunch is that it would be limited due to the exponential relationship between the dividend and the divisor in the algorithm?[/QUOTE]

I don't understand the question, sorry. Perhaps please try to reformulate your method/algorithm in a more universally comprehensible math notation. Chances are I completely misunderstood your description. Anyway, the test for a single exponent using your method as-I-understood-it takes about a microsecond in Go and could be maybe made about twice faster in assembly, I guess.

 science_man_88 2017-12-28 15:45

[QUOTE=gophne;475137]Hi jnml

How far are you able to test the "divisor" using this algorithm, using your software, and how long does it take? My hunch is that it would be limited due to the exponential relationship between the dividend and the divisor in the algorithm?[/QUOTE]

Want to see real crazy? Check out my blog area for more.

 gophne 2017-12-28 15:51

[QUOTE=jnml;475112]FTR: IIUC, the algorithm fails as soon as for [TEX]M_7[/TEX].

[TEX]127 = 1 \pmod 9[/TEX]

but

[TEX](7+1)/2 = 4[/TEX].

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]
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>
[/CODE][/QUOTE]
Hi jnml

Using the algorithm (sagemath), I get positive result for M3, M5 & M17. I could not test beyound M29 (dividend) due to unknown run time).

e.g. M3 (2^7-1)

#1......a=2^7-1..................Divisor under test~127....n-2
#2......b=(2^7-1)-2.............n~125
#3......c=1/2*(b+1).............Target Congruant~63
#4......d=2^b-1...................Dividend~42,535,295,865,117,307,932,921,825,928,971,026,431
#5.......e=d mod a..............Congruant~63
#6.......c==e.......................True~127(divisor) is Prime

 jnml 2017-12-28 15:52

[QUOTE=science_man_88;475140]Check out y blog area for more[/QUOTE]

Please clarify, I would love to understand what you're saying, but I don't.

 science_man_88 2017-12-28 15:54

[QUOTE=jnml;475142]Please clarify, I would love to understand what you're saying, but I don't.[/QUOTE]
[url]http://www.mersenneforum.org/forumdisplay.php?f=140[/url]

 gophne 2017-12-28 15:57

Hi njml

I get positive results for M7,M13,M19,M31 using sagemath code (see example post #50). I could not test higher because of unknown run time.

 jnml 2017-12-28 16:04

[QUOTE=gophne;475141]
Using the algorithm (sagemath), I get positive result for M3, M5 & M17. I could not test beyound M29 (dividend) due to unknown run time).

e.g. M3 (2^7-1)

#1......a=2^7-1..................Divisor under test~127....n-2
#2......b=(2^7-1)-2.............n~125
#3......c=1/2*(b+1).............Target Congruant~63
#4......d=2^b-1...................Dividend~42,535,295,865,117,307,932,921,825,928,971,026,431
#5.......e=d mod a..............Congruant~63
#6.......c==e.......................True~127(divisor) is Prime[/QUOTE]

Before digging further we should agree on notation. I used this one:

[TEX]2^7-1 = M_7 = M4[/TEX]

meaning [TEX]M_n[/TEX] is [TEX]2^n-1[/TEX] and [TEX]Mn[/TEX] = [TEX]n[/TEX]th Mersenne Prime as listed at [url]https://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes[/url].

Using this notation, your method correctly detects eg. [TEX]M_3[/TEX], [TEX]M_5[/TEX] and [TEX]M_{17}[/TEX], but fails to detect for e.g. [TEX]M_7[/TEX], [TEX]M_{13}[/TEX] and [TEX]M_{19}[/TEX].

I don't know sagemath, nonetheless, it might be useful to show the sagemath code as an alternative to the proper description in math-notation.

 jnml 2017-12-28 16:05

[QUOTE=science_man_88;475143][url]http://www.mersenneforum.org/forumdisplay.php?f=140[/url][/QUOTE]

Thanks, I [I]do[/I] understand now :smile:

 gophne 2017-12-28 16:11

[QUOTE=jnml;475142]Please clarify, I would love to understand what you're saying, but I don't.[/QUOTE]
Hi njml

I use very basic SAGEMATH code, as listed in post #50. Since the algorithm is very simple (straight math calculations), the results for M7, M13, M19, M31 returns positive when I run it in SAGEMATH code.

 gophne 2017-12-28 16:13

[QUOTE=science_man_88;475143][url]http://www.mersenneforum.org/forumdisplay.php?f=140[/url][/QUOTE]
Hi science_man_88

Which thread should I look at on the page that comes up?

 science_man_88 2017-12-28 16:17

[QUOTE=gophne;475141]

Using the algorithm (sagemath), I get positive result for M3, M5 & M17. I could not test beyound M29 (dividend) due to unknown run time).
[/QUOTE]

That's where algorithmic complexity computation comes in.

 gophne 2017-12-28 16:19

[QUOTE=jnml;475145]Before digging further we should agree on notation. I used this one:

[TEX]2^7-1 = M_7 = M4[/TEX]

meaning [TEX]M_n[/TEX] is [TEX]2^n-1[/TEX] and [TEX]Mn[/TEX] = [TEX]n[/TEX]th Mersenne Prime as listed at [url]https://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes[/url].

Using this notation, your method correctly detects eg. [TEX]M_3[/TEX], [TEX]M_5[/TEX] and [TEX]M_{17}[/TEX], but fails to detect for e.g. [TEX]M_7[/TEX], [TEX]M_{13}[/TEX] and [TEX]M_{19}[/TEX].

I don't know sagemath, nonetheless, it might be useful to show the sagemath code as an alternative to the proper description in math-notation.[/QUOTE]
Hi jnml

Perhaps somebody else can run the code in SAGEMATH...the code is fairly straight forward since the algorithm is also simple. I will try to put it more "formally" looking at SAGE code posted by other users.

I will try to grap screen an example, but sinnce I am running SAGEMATH in "VMWare Workstation software, I can't seem to do that.

 jnml 2017-12-28 16:54

[QUOTE=gophne;475154]
Perhaps somebody else can run the code in SAGEMATH...the code is fairly straight forward since the algorithm is also simple. I will try to put it more "formally" looking at SAGE code posted by other users.

I will try to grap screen an example, but sinnce I am running SAGEMATH in "VMWare Workstation software, I can't seem to do that.[/QUOTE]

Okay, attempting to understand post #50, I really previously inferred a [I]completely[/I] different method.

Source

[CODE]package main

import (
"fmt"
"math/big"

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

var (
_1 = big.NewInt(1)
_2 = big.NewInt(2)
)

func main() {
var tests, ok, falsePos, falseNeg int
var negs []uint32
var last uint32
n := uint32(2)
for n <= mersenne.Knowns[21] {
last = n
n, _ = mathutil.NextPrime(n)
_, prime := mersenne.Known[n]

// http://www.mersenneforum.org/showpost.php?p=475141&postcount=50
//
// #1......a=2^7-1..................Divisor under test~127....n-2
// #2......b=(2^7-1)-2.............n~125
// #3......c=1/2*(b+1).............Target Congruant~63
// #4......d=2^b-1...................Dividend~42,535,295,865,117,307,932,921,825,928,971,026,431
// #5.......e=d mod a..............Congruant~63
// #6.......c==e.......................True~127(divisor) is Prime

a := mersenne.New(n)
var b, c big.Int
b.Sub(b.Set(a), _2)
x := mathutil.ModPowBigInt(_2, &b, a)
x.Sub(x, _1)
conj := x.Cmp(&c) == 0

tests++
switch {
case prime == conj:
ok++
case prime:
falseNeg++
negs = append(negs, n)
default:
falsePos++
}
}
fmt.Printf("False negatives: %8d\n", falseNeg)
fmt.Printf("False positives: %8d\n", falsePos)
fmt.Printf("Correct results: %8d\n", ok)
fmt.Printf("Prime exponents: %8d (tests performed)\n", tests)
fmt.Printf("Last exponent: %8d\n", last)
fmt.Println("False negatives:")
for _, v := range negs {
fmt.Printf("\tM_%d\n", v)
}
}
[/CODE]

Run

[CODE]
~/src/tmp/main> go build && time ./main
False negatives: 0
False positives: 1205
Correct results: 21
Prime exponents: 1226 (tests performed)
Last exponent: 9941
False negatives:

real 1m10.533s
user 1m11.096s
sys 0m0.428s
~/src/tmp/main>
[/CODE]
[LIST][*]Only exponents < 10000 were tested this time as the single test is not anymore that fast as it was in the misunderstood case.
[*]No more false negatives!
[*]However much more false positiives.
[*]Seems to run a bit than LL tests in PARI (see [url]http://www.mersenneforum.org/showpost.php?p=475116&postcount=40[/url])[/LIST]

 science_man_88 2017-12-28 17:28

[QUOTE=jnml;475157][LIST][*]Seems to run a bit than LL tests in PARI (see [url]http://www.mersenneforum.org/showpost.php?p=475116&postcount=40[/url])[/LIST][/QUOTE]
[url]http://www.mersenneforum.org/showthread.php?t=20803[/url] may also give useful comparisons

 Batalov 2017-12-28 18:24

[QUOTE=jnml;475157][*]However much more false positiives.
[/QUOTE]
I'd say. Much more. The test simply returns true every time, huh?

 jnml 2017-12-28 18:33

[QUOTE=Batalov;475176]I'd say. Much more. The test simply returns true every time, huh?[/QUOTE]

Oops :surrender

 gophne 2017-12-28 23:23

false positives

Hi njml and batalov

I get the following running the Algorithm in SAGEMATH

False Positives identified by the algorithm;

0-100..............0 ~100 value, number of odd numbers tested would be half
0-1,000............3
0-10,000...........22
0-100,000..........78
0-1,000,000........245

pi(x)~78,498 primes less than 1,000,000 (primes.utm.edu) and therefore potentially 421,502 odd numbers that could be potentially "false positives". The actual false positives up to 1,000,000 according to the algorithm (run in SAGE) is therefore approx. 0.058%

No false negatives encountered up to 1,000,000.

 Batalov 2017-12-29 00:06

[QUOTE=gophne;475101]The algorithm is this:

For <...> odd n, (2^n-1) mod (n+2) is congruant to (n+1)/2 for all odd prime numbers, and non-congruant for all composites <...>

Thats it!
[/QUOTE]
So you are saying that your test is (2^n-1) = (n+1)/2 (mod n+2).
This is the same as:
2^(n+1)-2 = n+1 (mod n+2) . . . . . . [COLOR="Blue"](equivalent to mulitply both sides by 2 because n is odd)[/COLOR]
2^(n+1) = n+3 (mod n+2) . . . . . . . . [COLOR="Blue"]rearrange, subtract n+2...[/COLOR]
2^(n+1) = 1 (mod n+2)
which is the 2-PRP test for n+2, not for n.

Why would this test work for n? It "sort of" works for n+2, for sure. But what does it have to do with the primality of n??

 science_man_88 2017-12-29 00:20

[QUOTE=gophne;475150]Hi science_man_88

Which thread should I look at on the page that comes up?[/QUOTE]

Well theory on mersenne primes is probably craziest.

 Batalov 2017-12-29 00:21

[QUOTE=gophne;475141]Hi jnml

Using the algorithm (sagemath), I get positive result for M3, M5 & M17. I could not test beyound M29 (dividend) due to unknown run time).

e.g. M3 (2^7-1)

#1......a=2^7-1..................Divisor under test~127....[COLOR="Red"]n-2[/COLOR] <-- what the hell is this?
#2......b=(2^7-1)-2.............[COLOR="Red"]n~125[/COLOR]
#3......c=1/2*(b+1).............[COLOR="Red"]Target Congruant~63[/COLOR]
#4......d=2^b-1...................Dividend~42,535,295,865,117,307,932,921,825,928,971,026,431
#5.......e=d mod a..............Congruant~63
#6.......c==e.......................True~127(divisor) is Prime[/QUOTE]
So after all your talk about n this, n that, your own scribbling show that you suddenly call n-2 "n". Then of course, your "n+2" is n.

Congratulations! You proved that all primes are 2-PRP.
What is even more impressive is that all composite Mersenne numbers are 2-PRPs (even if you don't know it), so your test will just call them all prime. No false negatives!

 gophne 2017-12-29 01:18

[QUOTE=Batalov;475223]So after all your talk about n this, n that, your own scribbling show that you suddenly call n-2 "n". Then of course, your "n+2" is n.

Congratulations! You proved that all primes are 2-PRP.
What is even more impressive is that all composite Mersenne numbers are 2-PRPs (even if you don't know it), so your test will just call them all prime. No false negatives![/QUOTE]
Hi batalov

That is how I coded the algorithm (in SAGE)....if you like I could(should?) have coded the algorithm as follows as well -I did the above to put the "number" being tested as step #1.

#1.......a=(2^7-1)-2.........[COLOR="Red"]Modulo Dividend???[/COLOR]~125 (should be the dividend "seed" value to get "d", the real Modulo dividend as per the algorithm.
#2.......b=2^7-1...............Modulo Divisor~(a+2=127)....NUMBER UNDER TEST
#3.......c=(a+1)/2............Modulo Target Congruant~63
#4.......d=2^a-1..............Modulo Divident~ As above
#5.......e=d mod a..........Algorithm Congruant=63
#6.......c==e....................True~127(Divisor) is Prime

To simplify further you could simply call the Divident seed [B]25[/B] in step #1. That would make the divisor in step #2, [B]27[/B]~(n+2). or (a+2) if you like. I only used mersenne notation because jnml was working with M[I]n[/I] notation, which would be more practical if very large numbers are to be considered.

I am trying my best to be clear, but bear with me that I am trying to translate my code into words. I will try to type some actual code of a working page as I code the algorithm in SAGEMATH. But everybody would code differently depending on their expertise in SAGEMATH. My coding skills in SAGE are moderate.

 ewmayer 2017-12-29 02:18

[QUOTE=Batalov;475223]Congratulations! You proved that all primes are 2-PRP.
What is even more impressive is that all composite Mersenne numbers are 2-PRPs (even if you don't know it), so your test will just call them all prime. No false negatives![/QUOTE]

No true negatives, either - but hey, who needs all that negativity, it's harshing the holiday spirit, and stuff.

 Batalov 2017-12-29 02:23

[QUOTE="old TV cartoon"]That's why we called him Neutron! He is always so positive![/QUOTE]
[COLOR=Wheat].[/COLOR]

 chalsall 2017-12-29 02:35

[QUOTE=Batalov;475233]That's why we called him Neutron! He is always so positive![/QUOTE]

Umm... Wasn't that the Protons?

At least one of the Electrons refused to play game.

 gophne 2017-12-29 04:57

[QUOTE=Batalov;475223]So after all your talk about n this, n that, your own scribbling show that you suddenly call n-2 "n". Then of course, your "n+2" is n.

Congratulations! You proved that all primes are 2-PRP.
What is even more impressive is that all composite Mersenne numbers are 2-PRPs (even if you don't know it), so your test will just call them all prime. No false negatives![/QUOTE]
hi batalov

I do not understand what you are saying about 2-PRP's ....are you running the algorithm? What are your results?

I do not get all "composite mersenne numbers" to be false positives, on the contrary, e.g [B]2^9-1 & 2^15-1[/B], do not register as a false positives but as composite in the algorithm.

Please post your results, you could even do the calculation on a calculator or Excel at this level of magnitude.

 gophne 2017-12-29 05:54

SAGEMATH CODE for False Positives

Here is SAGEMATH code to check for false positive (prime) results (for the algorithm) up to 1,000,000. Should only take a few minutes to run.

[1] x=0
[2] for y in range(1,1000000,2):
z= next_prime(y)
a= y+2; #Modulo Divisor....Number under test
b= 2^y-1; #Modulo Dividend
c= b%a; #Algorithm Modulo Congruent
d= (y+1)/2; #Target Congruent as per Algorithm
if c==d:
if z>a:
x=x+1
print(a,x); # 'a' is the False Positive identified, 'x' is a counter

The SAGEMATH software will automatically do the indentation for the code.

 gophne 2017-12-29 06:19

Restatement of Algorithm for Use and Testing

If (2^n-1) [B]mod[/B] (n+2) = (n+1)/2, then (n+2) is PRIME, else COMPOSITE, [I]n[/I] being an element of the set of positive integers =>1

 ewmayer 2017-12-29 06:41

[QUOTE=gophne;475261]If (2^n-1) [B]mod[/B] (n+2) = (n+1)/2, then (n+2) is PRIME, else COMPOSITE, [I]n[/I] being an element of the set of positive integers =>1[/QUOTE]

Yeah, we heard you the first million-and-six times. Try (n+2) = 2047 = 23*89 in your formula.

 Batalov 2017-12-29 06:45

[QUOTE=gophne;475252]
I do not understand what you are saying about 2-PRP's [/QUOTE]
A person who walks off a 1km cliff also doesn't understand that he is already dead.
But he is.
[QUOTE=gophne;475261][B]Restatement of Algorithm for Use and Testing
[/B]If (2^n-1) [B]mod[/B] (n+2) = (n+1)/2, then (n+2) is PRIME, else COMPOSITE, [I]n[/I] being an element of the set of positive integers =>1[/QUOTE]
This is exactly what is called a 2-PRP test. 1) It is >350 years old. 2) It is false.
Try n+2 == 341. (2^n-1) [B]mod[/B] (n+2) = (n+1)/2, then (n+2) is PRIME? Wrong. It is composite. [URL="https://en.wikipedia.org/wiki/Fermat%27s_little_theorem#Pseudoprimes"]F. Sarrus in 1820 found 341[/URL] as one of the first pseudoprimes, to base 2. That was 197 years ago.
Try n+2 == 561. (2^n-1) [B]mod[/B] (n+2) = (n+1)/2, then (n+2) is PRIME? Wrong. It is composite.
Try n+2 == 645. (2^n-1) [B]mod[/B] (n+2) = (n+1)/2, then (n+2) is PRIME? Wrong. It is composite.

 chalsall 2017-12-29 06:49

[QUOTE=Batalov;475266]A person who walks off a 1km cliff also doesn't understand that he is already dead.[/QUOTE]

It's not the fall which kills them. It's the hard stop at the end...

 Batalov 2017-12-29 06:53

Subjectively, they can feel as if they are still alive for a long time.
Ambrose Bierce described that in 'An Occurrence at Owl Creek Bridge'.

 gophne 2017-12-29 09:33

[QUOTE=ewmayer;475265]Yeah, we heard you the first million-and-six times. Try (n+2) = 2047 = 23*89 in your formula.[/QUOTE]
Hi ewmayer[B]

You are correct, that is a false positive (prime) result returned by the algorith. There are others as well. If you run the Code that I posted #73, you can identify many more. False positives are not uncommon with Primality algorithms, only the percentage of false positives w.r.t total number of "primes" tested

-Refer [B]Fermat Primality test[/B] which have "[B]......21853 pseudoprimes base 2 that are less than 2.5×10^10 (see page 1005 of [4]). This means that, for n up to 2.5×10^10, if 2n−1 (modulo n) equals 1, then n is prime, unless n is one of these 21853 pseudoprimes[/B]"......Source [url]https://en.wikipedia.org/wiki/Primality_test[/url]

Indications are that this algorithm will have less false positives at 2.5x10^10, currently sitting at +-750 at 10^7 and decreasing trend with increasing magnitude. Interestingly the smallest[I] false positive[/I] for the Fermat primality test is also the smallest [I]false positive[/I] for this algorithm!!! -[B]341[/B]

 gophne 2017-12-29 09:52

[QUOTE=Batalov;475266]A person who walks off a 1km cliff also doesn't understand that he is already dead.
But he is.

This is exactly what is called a 2-PRP test. 1) It is >350 years old. 2) It is false.
Try n+2 == 341. (2^n-1) [B]mod[/B] (n+2) = (n+1)/2, then (n+2) is PRIME? Wrong. It is composite. [URL="https://en.wikipedia.org/wiki/Fermat%27s_little_theorem#Pseudoprimes"]F. Sarrus in 1820 found 341[/URL] as one of the first pseudoprimes, to base 2. That was 197 years ago.
Try n+2 == 561. (2^n-1) [B]mod[/B] (n+2) = (n+1)/2, then (n+2) is PRIME? Wrong. It is composite.
Try n+2 == 645. (2^n-1) [B]mod[/B] (n+2) = (n+1)/2, then (n+2) is PRIME? Wrong. It is composite.[/QUOTE]
Hi Batalov

Fermat Primality Test has [B]21,853 pseudo-primes in 2.5x10^10[/B]....refer my [I]post #79[/I] for reference for this figure. Do you consider the Fermat Primality Test [I]fake[/I] as well based on your reasoning/reference?

You refer to 3 examples, I have listed ([I]and have provided Code[/I]) for [B]245[/B] false primes up to [B]1,000,000[/B] (magnitude)

 Batalov 2017-12-29 15:56

There is no reason for this self-flagellation to go on.

 ewmayer 2017-12-29 23:17

Briefly reopening the thread for the benefit of our less-mathematical readers who may not see why the test in question is simply a base-2 Fermat pseudoprime test in disguise - start with the OP's version:

(2^n-1) == (n+1)/2 mod (n+2)

Replace the silly 'n+2' modulus by n, i.e. everywhere in the formula subtract 2 from n:

2^(n-2) - 1 == (n-1)/2 (mod n)

Multiply by 2:

2^(n-1) - 2 == (n-1) (mod n) == -1 (mod n)

2^(n-1) == 1 (mod n) . QED

 gophne 2017-12-30 18:36

[QUOTE=ewmayer;475324]Briefly reopening the thread for the benefit of our less-mathematical readers who may not see why the test in question is simply a base-2 Fermat pseudoprime test in disguise - start with the OP's version:

(2^n-1) == (n+1)/2 mod (n+2)

Replace the silly 'n+2' modulus by n, i.e. everywhere in the formula subtract 2 from n:

2^(n-2) - 1 == (n-1)/2 (mod n)

Multiply by 2:

2^(n-1) - 2 == (n-1) (mod n) == -1 (mod n)

2^(n-1) == 1 (mod n) . QED[/QUOTE]
Hi ewmayer

I don't understand why you say my algorithm is;

(2^n-1) == (n+1)/2 mod (n+2)

I thought it was

[B](2^n-1) mod (n+2) == (n+1)/2[/B]

Retracing your steps would then give

[1] Replacing (n+2) with n

2^(n-2)-1 mod n == (n-1)/2

[2] Multiplying by 2

2^(n-1)-2 mod n == (n-1)

[3] Add 2 to both sides

[B]2^(n-1) mod n == (n+1)[/B]

This is different from your result and therefore [I]not[/I] the algorith you reduced. Similar, but very different, like 1 is different from 2

Am I mistaken with this? If you would concur it would still mean my algorithm is original.

 Batalov 2017-12-30 18:42

[QUOTE=gophne;475439]Am I mistaken with this? If you would concur it would still mean my algorithm is original.[/QUOTE]
You are.

Do you always read only the second explanation? First is not enough? It has to be repeated twice?
What Ernst wrote I already [URL="http://www.mersenneforum.org/showthread.php?p=475218#post475218"]spelled out for you two days ago[/URL].

 danaj 2017-12-30 18:57

[QUOTE=gophne;475439]
I don't understand why you say my algorithm is;

(2^n-1) == (n+1)/2 mod (n+2)[/quote]

It's the usual way of writing a congruence equation. Both sides use modular arithmetic. You seem to be assuming only one.

[quote] [...]
[B]2^(n-1) mod n == (n+1)[/B][/quote]

If this is a congruence, then n+1 also has mod n applied, which means it is equivalent to 1, as they said. If you insist it is not, then how exactly could it *ever* be true? The lifted result of x mod n is always in the range 0 to n-1, so clearly it cannot be n+1.

 gophne 2017-12-30 19:01

[QUOTE=Batalov;475440]You are.

Do you always read only the second explanation? First is not enough? It has to be repeated twice?
What Ernst wrote I already [URL="http://www.mersenneforum.org/showthread.php?p=475218#post475218"]spelled out for you two days ago[/URL].[/QUOTE]
Hi Batalov

I respect your opinions as an expert and a Mod. However I have a right to defend myself as well.

Please look at my reply to [I]ewmayer[/I] in post #83 and correct me where I am wrong/mistaken.

According to my humble understanding I do not think that the two are the same. Please explain how you can say the two algoriths are the same when ewmayer appears to have tweaked my algorithm, possibly unintentionally. Just juxtapose the two. They are [B]not[/B] the same -look at the formulas, not the same as what ewmayer reworked.

But thanks for taking me to task, but I will try to defend my position as I understand -sometimes ignorance is bliss.

I will also see how other users understand the issues, but for now I cannot agree that what ewmayer "re-worked" is the algorithm I posted.

Thanks

 ATH 2017-12-30 19:49

[QUOTE=gophne;475439]I don't understand why you say my algorithm is;

(2^n-1) == (n+1)/2 mod (n+2)

I thought it was

[B](2^n-1) mod (n+2) == (n+1)/2[/B]
[/QUOTE]

The top line is just the usual way of writing modular equations, it means the same thing as you intend.

[QUOTE]
[B]2^(n-1) mod n == (n+1)[/B]

This is different from your result and therefore [I]not[/I] the algorith you reduced. Similar, but very different, like 1 is different from 2

Am I mistaken with this? If you would concur it would still mean my algorithm is original.[/QUOTE]

If something is equal to (n+1) mod n, then it is also equal to 1 mod n, and equal to 2n+1 mod n and 3n+1 mod n and so on.

If say n=5:

Then:
31 mod n = 1 because 31=6*n + 1
31 mod n = 6 = n+1 because 31= 5*n + 6
31 mod n = 11 = 2n+1 because 31 = 4*n + 11
and so on.

 Batalov 2017-12-30 21:42

I wrote a ground-breaking new poem and I shall go around telling everyone that I've truly made something out of myself. Here is small bit of it. I have more, much more! --
[QUOTE]To be or not to be - that is the question:
If it is nobler in the mind to suffer
The slings and arrows of outrageous fortune
Or to take arms against a sea of troubles
And by opposing end them.[/QUOTE]Now some people keep telling me that some guy with a spear (never heard of him) already wrote something similar. But it is false. Mine is completely different. His version has some extra commas and the words are not the same; first of all, they are completely unnecessary, and secondly, surely this makes it not the same.

 chalsall 2017-12-30 21:52

[QUOTE=Batalov;475464]I wrote a ground-breaking new poem and I shall go around telling everyone that I've truly made something out of myself. Here is small bit of it. I have more, much more![/QUOTE]

ROFL! Do you have a team of monkeys?

I happened to come across a documentary called "Tim's Vermeer". Please see [url]http://www.sonyclassics.com/timsvermeer/[/url]

It is almost painful to watch, but I am a huge admirer of Tim Jenison. His Video Toaster changed the video creation world (for a little while).

 Batalov 2017-12-30 22:15

[QUOTE=chalsall;475466]ROFL! Do you have a team of monkeys?
[/QUOTE]
I noticed that you're citing my work...but coming to faulty conclusions. Your alleged "counter-example" is not a counter-example of my method at all. I do not have a team of monkeys, and being a true patriot, I am only using American ink, American paper, American Apple computer, American keyboard and an American printer. Get it?

At the end of the day, I am THRILLED people are actually thinking about my work, and I am more than happy to address any questions, comments, concerns, etc. you have regarding my poetry.

 chalsall 2017-12-30 22:22

[QUOTE=Batalov;475469]Get it?[/QUOTE]

Sure.

Have you read any prior es?

[QUOTE]To be, or not to be--that is the question:
Whether 'tis nobler in the mind to suffer
The slings and arrows of outrageous fortune
Or to take arms against a sea of troubles[/QUOTE]in fact the 'new' poem was shorter and more like:
[COLOR=Red]
QUESTION: 2b or 2b+1 ?[/COLOR]

[COLOR=Green]if by "2b+1" you actually mean "not 2b", then yes your poem is equivalent
to a monologue from a play by william shakespeare,[/COLOR]

[COLOR=Red]no no no ... this totally changes the intention of my poem !
why did you twist and change my words from "2b+1" to "not 2b" ?
the question "2b or 2b+1" is different from "2b or not 2b"[/COLOR]

[COLOR=Green]because if it is "2b+1" then it also "not 2b"
[/COLOR]
please forgive my poetical ignorance, but at the moment and in this thread i like the 'original poem' a better than that of shakespeare ... it shows originality and even shakespeare was a 'poetical baby' once :smile:

 Batalov 2017-12-30 23:22

I am THRILLED people are actually getting it, and that they clearly like "[URL="http://mersenneforum.org/showthread.php?p=475249#post475249"]my[/URL]" style.

Jim stayed in character for weeks (see below), ... I can't - so I'll break down laughing right now.

 chalsall 2017-12-30 23:53

[QUOTE=Batalov;475492]I am THRILLED people are actually getting it, and that they clearly like my style.[/QUOTE]

Yeah... "Man on the Moon" was amazing. It remains one of my favourite films (after Gattaca and A Beautiful Mind).

Kaufman pushed the envelope, as did Carrey portraying him.

 gophne 2017-12-31 02:25

[QUOTE=chalsall;475466]ROFL! Do you have a team of monkeys?

I happened to come across a documentary called "Tim's Vermeer". Please see [url]http://www.sonyclassics.com/timsvermeer/[/url]

It is almost painful to watch, but I am a huge admirer of Tim Jenison. His Video Toaster changed the video creation world (for a little while).[/QUOTE]
Hi chalsall

Name calling and insults doesn't advance your cause...and is not the scientific way to rebutt. :(

Why don't you try running the algorithm instead....they way the taught you to do at elementary school. Put in some values....TEST IT.

 chalsall 2017-12-31 02:34

[QUOTE=gophne;475513]Name calling and insults doesn't advance your cause...and is not the scientific way to rebutt. :([/QUOTE]

Hi gophne. With all due respect, I wasn't name calling, nor meaning to insult.

The referral to monkeys and typewriters and Shakespeare is a very common reference in statistics.

You have, of course, read the prior art.

I apologise if I manage to insult you, or anyone.

 gophne 2017-12-31 02:36

[QUOTE=guptadeva;475491]in fact the 'new' poem was shorter and more like:
[COLOR=Red]
QUESTION: 2b or 2b+1 ?[/COLOR]

[COLOR=Green]if by "2b+1" you actually mean "not 2b", then yes your poem is equivalent
to a monologue from a play by william shakespeare,[/COLOR]

[COLOR=Red]no no no ... this totally changes the intention of my poem !
why did you twist and change my words from "2b+1" to "not 2b" ?
the question "2b or 2b+1" is different from "2b or not 2b"[/COLOR]

[COLOR=Green]because if it is "2b+1" then it also "not 2b"
[/COLOR]
please forgive my poetical ignorance, but at the moment and in this thread i like the 'original poem' a better than that of shakespeare ... it shows originality and even shakespeare was a 'poetical baby' once :smile:[/QUOTE]

Again not a scientific approach to the issue, but very beautiful never-the-less. I love Shakespeare as well.

But in mathematics I was taught by my teachers that there was a universe of difference between "+1" and "-1" even though the appear to be very similar/close. OR in this case x==y versus x==y mod x.

I would have thought that that was elementary math...I am getting very scared about the so-called experts. What is to the LHS of the equal sign should be the same on the RHS, what is done to the equation on the LHS of the equal sign should be done to the equation on the RHS as well.

Elementary!

All times are UTC. The time now is 21:26.