"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?

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.)

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.

Thanks for the initial advise.

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

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?

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

[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?

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

[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.

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

[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?

[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.

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

[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]
Hi guptadeva

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?

[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.

[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.

[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?

[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.

[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.

[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.

[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.

[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.

[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.

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

Publish. And then we all will know.

[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.

[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.

[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).

[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]
Thanx for advice.

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"

[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 ...

[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.

[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!

@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?

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.

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

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]

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

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

[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!

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:

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

I shall perservere, without the bravado.

[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)

[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?

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

[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.

[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.

[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

[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.

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

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.

[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.

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

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

[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.

[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?

[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.

[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.

[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)
c.Div(c.Add(c.Set(&b), _1), _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]

[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

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

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


Oops :surrender

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.

[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??

[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.

[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!

[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.

[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.

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

[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.

[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.

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.

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

[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.

[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.

[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...

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'.

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

[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)

There is no reason for this self-flagellation to go on.
Please meditate in silence. [SPOILER]Or ask for your own logorrhea thread.[/SPOILER]

The thread is locked.

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)

Add 2 to both sides:

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

[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)

Add 2 to both sides:

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

Thanks for your post.

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.

[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].

[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.

[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

[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.

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.

[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).

[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.

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

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.
[YOUTUBE]kB15UFO5ebA[/YOUTUBE]

[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.

[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.

[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.

[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]
Hi guptadeva

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!