Heuristics
 

tl;dr: In the range of odd prime exponents up to 74207281, eliminate nearly 2/3 of the candidates while missing only 1/6 of the Mersenne prime exponents - in less than one minute.

Source (Go):
[CODE]
package main

import (
"fmt"

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

const (
maxMod = 1024
mods = 13
)

func main() {
n := uint32(2)
var last uint32
maxN := mersenne.Knowns[len(mersenne.Knowns)-1]
var tests, ok, falseNeg, falsePos int
var negs []uint32
for {
last = n
n, _ = mathutil.NextPrime(n)
if n > maxN {
break
}

var m1 int
for i := 2; i <= maxMod; i++ {
if i >= int(n) {
break
}

if int(n)%i == 1 {
m1++
}
}
conj := m1 >= mathutil.Min(mods, mathutil.BitLen(int(n))/2)
_, prime := mersenne.Known[n]
tests++
switch {
case prime == conj:
ok++
case prime:
falseNeg++
negs = append(negs, n)
default:
falsePos++
}
}
k := len(mersenne.Knowns) - 1
fmt.Printf("False negatives: %8d %5.2f%% of %d\n", falseNeg, 100*float64(falseNeg)/float64(k), k)
fmt.Printf("False positives: %8d\n", falsePos)
fmt.Printf("Correct results: %8d %5.2f%% of %d\n", ok, 100*float64(ok)/float64(tests), tests)
fmt.Printf("Prime exponents: %8d (tests performed)\n", tests)
fmt.Printf("Last exponent: %8d\n", last)
if len(negs) != 0 {
fmt.Println("False negatives:")
for _, v := range negs {
fmt.Printf("\tM_%d\n", v)
}
}
}
[/CODE]

Execution:
[CODE]
~/src/tmp/main> time ./main
False negatives: 8 16.67% of 48
False positives: 1566332
Correct results: 2784260 64.00% of 4350600
Prime exponents: 4350600 (tests performed)
Last exponent: 74207281
False negatives:
M_2203
M_4253
M_11213
M_756839
M_1257787
M_1398269
M_24036583
M_37156667

real 0m44.489s
user 0m44.500s
sys 0m0.012s
~/src/tmp/main>
[/CODE]

[QUOTE=jnml;475331]tl;dr: In the range of odd prime exponents up to 74207281, eliminate nearly 2/3 of the candidates while missing only 1/6 of the Mersenne prime exponents - in less than one minute.

Source (Go):
[CODE]
(...)
mersenne.Known[n]
(...)
k := len(mersenne.Knowns) - 1
[/CODE]
[/QUOTE]

That seems to be a pretty bad error rate, when you are using the table of known Mersenne prime's exponents. Improve your code!

[QUOTE=R. Gerbicz;475335]That seems to be a pretty bad error rate, when you are using the table of known Mersenne prime's exponents. Improve your code![/QUOTE]

You have misunderstood the code. The mersenne.Knowns and mersenne.Known and the variables based on them, 'k' and 'prime' are used solely to [I]evaluate the results[/I] of the heuristic based algorithm, [I]not[/I] at all to [I]compute[/I] the 'conj' value, which has the meaning 'is probably an exponent of a Mersenne prime'.

Here's the proof:
[CODE]
package main

import (
"fmt"

"github.com/cznic/mathutil"
)

const (
maxMod = 1024
mods = 13
)

func main() {
n := uint32(2)
var last uint32
maxN := uint32(74207281)
var tests, candidates int
for {
last = n
n, _ = mathutil.NextPrime(n)
if n > maxN {
break
}

var m1 int
for i := 2; i <= maxMod; i++ {
if i >= int(n) {
break
}

if int(n)%i == 1 {
m1++
}
}
conj := m1 >= mathutil.Min(mods, mathutil.BitLen(int(n))/2)
if conj {
candidates++
}
tests++
}
fmt.Printf("Candidates: %8d\n", candidates)
fmt.Printf("Last exponent: %8d\n", last)
}
[/CODE]

Execution:
[CODE]
~/src/tmp/main> time ./main
Candidates: 1566372
Last exponent: 74207281

real 0m42.951s
user 0m42.946s
sys 0m0.000s
~/src/tmp/main>
[/CODE]

Your algorithm seems to have a lot of adjustable parameters, enough that it wouldn’t seem hard to optimize for a result about as good as this just by overfitting the data. That doesn’t give me much confidence that the algorithm would usefully scale to further Mersenne numbers.

In any case, note that the algorithm only gives finitely many candidates — that is, it predicts that beyond some point all Mersenne numbers are composite. That gives me even less confidence.

[QUOTE=CRGreathouse;475506]
Your algorithm seems to have a lot of adjustable parameters, ...
[/QUOTE]

There are actually only two tuning knobs. 'maxMod' selects the "depth" of a single test and
'mods' sets the "decision" threshold.

[QUOTE=CRGreathouse;475506]
... enough that it wouldn’t seem hard to optimize for a result about as good as this just by
overfitting the data. That doesn’t give me much confidence that the algorithm would
usefully scale to further Mersenne numbers.[/QUOTE]

That's very much possible, but without actually knowing some yet uknown further
Mersenne primes the outcome is not crystal clear.

[QUOTE]
In any case, note that the algorithm only gives finitely many candidates — that is, it
predicts that beyond some point all Mersenne numbers are composite. That gives me
even less confidence.[/QUOTE]

I don't know where the impression that the test has some limit comes from. Let's just run
the same code, with only the upper limit doubled, no other parameter was changed:

[CODE]
package main

import (
"fmt"

"github.com/cznic/mathutil"
)

const (
maxMod = 1024
mods = 13
)

func main() {
n := uint32(2)
var last uint32
maxN := 2 * uint32(74207281)
var tests, candidates int
for {
last = n
n, _ = mathutil.NextPrime(n)
if n > maxN {
break
}

var m1 int
for i := 2; i <= maxMod; i++ {
if i >= int(n) {
break
}

if int(n)%i == 1 {
m1++
}
}
conj := m1 >= mathutil.Min(mods, mathutil.BitLen(int(n))/2)
if conj {
candidates++
}
tests++
}
fmt.Printf("Candidates: %9d\n", candidates)
fmt.Printf("Prime exponents: %9d (tests performed)\n", tests)
fmt.Printf("Last exponent: %9d\n", last)
}
[/CODE]

Execution:

[CODE]
~/src/tmp/main> time ./main
Candidates: 2930472
Prime exponents: 8360252 (tests performed)
Last exponent: 148414537

real 1m21.607s
user 1m21.448s
sys 0m0.040s
~/src/tmp/main>
[/CODE]

I wonder if it "detects" or misses M50. We will know soon. Chosen ones may try already,
just by running the outer loop once with 'n' set to the 7xxxxxxxx exponent. A single
test runs in about 10 microseconds.

I want to post the result of running the code in post [URL="http://www.mersenneforum.org/showpost.php?p=475331&postcount=1"]#1[/URL] once M50 goes public.

PS: FTR: The actual "algorithm" is the inner loop. The outer one just selects what range
one wants to test. And yes, knowing the actual primes in the range of course implies the
best-fit values of the test parameters. It's a heuristic based test, after all.

[QUOTE=jnml;475557]I don't know where the impression that the test has some limit comes from.[/quote]

From my analysis of your code. It’s easy to see that all n >= 2^2047 are detected as non-prime. A bit of effort shows that
[code]16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650496590712511252285651639106946065207945533638967006292554765249225998938041188226886788009973067856458696750906671494954059950549179271386985133075548549580134988472982802067434038956599873142170078749639418012172512091402357259754616754822564704948167365865823247013034124612050000707594985881023213092009269635091951503361482028872303431603984166237134290452175784064677481030687632778717485937144402213085086689203401384363706793986485885440001[/code]
is the last number detected as a Mersenne exponent, if you allow composites, or
[code]16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683649723338597261540859709106693445015368660108875402892037762722856601385686451583086379814239252957953005801733903235334768021827287204324559826013062959085878285717391588345261898837334566599719994757523969587123189603679962754697914110034263373229505763160429561915518489424177512542712831644517522108470961969379521122124794494954390525271086287089480256791021142308215454899587236903245344574894274601709193034606462056949274261957344278901120001[/code]
if you look only at primes.

[QUOTE=CRGreathouse;475585]From my analysis of your code. It’s easy to see that all n >= 2^2047 are detected as non-prime. A bit of effort shows that
[code]16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650496590712511252285651639106946065207945533638967006292554765249225998938041188226886788009973067856458696750906671494954059950549179271386985133075548549580134988472982802067434038956599873142170078749639418012172512091402357259754616754822564704948167365865823247013034124612050000707594985881023213092009269635091951503361482028872303431603984166237134290452175784064677481030687632778717485937144402213085086689203401384363706793986485885440001[/code]
is the last number detected as a Mersenne exponent, if you allow composites, or
[code]16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683649723338597261540859709106693445015368660108875402892037762722856601385686451583086379814239252957953005801733903235334768021827287204324559826013062959085878285717391588345261898837334566599719994757523969587123189603679962754697914110034263373229505763160429561915518489424177512542712831644517522108470961969379521122124794494954390525271086287089480256791021142308215454899587236903245344574894274601709193034606462056949274261957344278901120001[/code]
if you look only at primes.[/QUOTE]

Ha! You must have looked at the code much more thoroughly than I'd ever hoped for.
Please, please share the analysis. I hope to learn something, because I don't ATM see
why the test will cease to return true there.

Anyway, the exponent (sic!) limit you are talking about is in multiple orders
of magnitude higher than anything I had in my mind when I talked about "no limits". As
realizing the Mn for the exponent you've shown in the computer memory requires more bits
(IINM) than there are particles in the observed universe, I feel sorry for thinking in the dirty
"material" terms, which admitedly no mathematician should ever do! ;-)

(I'm serious, infinities are important, I should have not ignored it when talking about a
particular method having "no limit". Instead my thinking was like "64 bit exponent is infinity
for all practical purposes".).

PS: Does the limit appy to all values of 'maxMod'? Because it's just a parameter of the test...

@CRGreathouse

Something does not add up. Here the test continues to produce candidates.

Source:

[CODE]
package main

import (
"fmt"
"math/big"
)

const (
maxMod = 1024
mods = 13

first = "16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683649723338597261540859709106693445015368660108875402892037762722856601385686451583086379814239252957953005801733903235334768021827287204324559826013062959085878285717391588345261898837334566599719994757523969587123189603679962754697914110034263373229505763160429561915518489424177512542712831644517522108470961969379521122124794494954390525271086287089480256791021142308215454899587236903245344574894274601709193034606462056949274261957344278901120001"
)

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

func main() {
n := big.NewInt(0)
if _, ok := n.SetString(first, 10); !ok {
panic("invalid 'first'")
}

ok := 0
for {
var m1 int
var m big.Int
i := big.NewInt(2)
for i.Cmp(_maxMod) <= 0 {
if m.Mod(n, i).Cmp(_1) == 0 {
m1++
}
i.Add(i, _1)
}
conj := m1 >= mods
if conj {
fmt.Println(n)
ok++
if ok > 5 {
return
}
}

for ok := false; !ok; {
n.Add(n, _2)
ok = n.ProbablyPrime(10)
}
}
}
[/CODE]

Execution:

[CODE]
~/src/tmp/main> time ./main | tee log
16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683649723338597261540859709106693445015368660108875402892037762722856601385686451583086379814239252957953005801733903235334768021827287204324559826013062959085878285717391588345261898837334566599719994757523969587123189603679962754697914110034263373229505763160429561915518489424177512542712831644517522108470961969379521122124794494954390525271086287089480256791021142308215454899587236903245344574894274601709193034606462056949274261957344278901120001
16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683649723338597261540859709106693445015368660108875402892037762722856601385686451583086379814239252957953005801733903235334768021827287204324559826013062959085878285717391588345261898837334566599719994757523969587123189603679962754697914110034263373229505763160429561915518489424177512542712831644517522108470961969379521122124794494954390525271086287089480256791021142308215454899587236903245344574894274601709193034606462056949274261957344278901121117
16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683649723338597261540859709106693445015368660108875402892037762722856601385686451583086379814239252957953005801733903235334768021827287204324559826013062959085878285717391588345261898837334566599719994757523969587123189603679962754697914110034263373229505763160429561915518489424177512542712831644517522108470961969379521122124794494954390525271086287089480256791021142308215454899587236903245344574894274601709193034606462056949274261957344278901122551
16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683649723338597261540859709106693445015368660108875402892037762722856601385686451583086379814239252957953005801733903235334768021827287204324559826013062959085878285717391588345261898837334566599719994757523969587123189603679962754697914110034263373229505763160429561915518489424177512542712831644517522108470961969379521122124794494954390525271086287089480256791021142308215454899587236903245344574894274601709193034606462056949274261957344278901123251
16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683649723338597261540859709106693445015368660108875402892037762722856601385686451583086379814239252957953005801733903235334768021827287204324559826013062959085878285717391588345261898837334566599719994757523969587123189603679962754697914110034263373229505763160429561915518489424177512542712831644517522108470961969379521122124794494954390525271086287089480256791021142308215454899587236903245344574894274601709193034606462056949274261957344278901124931
16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683649723338597261540859709106693445015368660108875402892037762722856601385686451583086379814239252957953005801733903235334768021827287204324559826013062959085878285717391588345261898837334566599719994757523969587123189603679962754697914110034263373229505763160429561915518489424177512542712831644517522108470961969379521122124794494954390525271086287089480256791021142308215454899587236903245344574894274601709193034606462056949274261957344278901125441

real 0m4.922s
user 0m4.923s
sys 0m0.000s
~/src/tmp/main>
[/CODE]

I guess I've made a mistake somewhere when changing the code to start at the prime
you've indicated to be the last one to pass the test. Can you please kindly take a look at
the code if you can perhaps see where the problem is?

[QUOTE=jnml;475625]I guess I've made a mistake somewhere when changing the code to start at the prime
you've indicated to be the last one to pass the test. Can you please kindly take a look at
the code if you can perhaps see where the problem is?[/QUOTE]

You used the second number instead of the first. If you use the first you should find no more examples. To get none with the second you would need to include a primality test on the exponent itself.

[QUOTE=jnml;475605]PS: Does the limit appy to all values of 'maxMod'? Because it's just a parameter of the test...[/QUOTE]

No, my analysis requires those parameters to have the value they take in your code. But for every choice of maxMod there are only finitely many exponents chosen.

[QUOTE=CRGreathouse;475631]
You used the second number instead of the first. If you use the first you should find no
more examples.[/QUOTE]

Retrying with your first number:

[CODE]
package main

import (
"fmt"
"math/big"
)

const (
maxMod = 1024
mods = 13

first = "16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650496590712511252285651639106946065207945533638967006292554765249225998938041188226886788009973067856458696750906671494954059950549179271386985133075548549580134988472982802067434038956599873142170078749639418012172512091402357259754616754822564704948167365865823247013034124612050000707594985881023213092009269635091951503361482028872303431603984166237134290452175784064677481030687632778717485937144402213085086689203401384363706793986485885440001"
)

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

func main() {
n := big.NewInt(0)
if _, ok := n.SetString(first, 10); !ok {
panic("invalid 'first'")
}

ok := 0
for {
var m1 int
var m big.Int
i := big.NewInt(2)
for i.Cmp(_maxMod) <= 0 {
if m.Mod(n, i).Cmp(_1) == 0 {
m1++
}
i.Add(i, _1)
}
conj := m1 >= mods
if conj {
fmt.Println(n)
ok++
if ok > 5 {
return
}
}

n.Add(n, _2)
}
}
[/CODE]

Execution:

[CODE]
~/src/tmp/main> time ./main | tee log
16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650496590712511252285651639106946065207945533638967006292554765249225998938041188226886788009973067856458696750906671494954059950549179271386985133075548549580134988472982802067434038956599873142170078749639418012172512091402357259754616754822564704948167365865823247013034124612050000707594985881023213092009269635091951503361482028872303431603984166237134290452175784064677481030687632778717485937144402213085086689203401384363706793986485885440001
16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650496590712511252285651639106946065207945533638967006292554765249225998938041188226886788009973067856458696750906671494954059950549179271386985133075548549580134988472982802067434038956599873142170078749639418012172512091402357259754616754822564704948167365865823247013034124612050000707594985881023213092009269635091951503361482028872303431603984166237134290452175784064677481030687632778717485937144402213085086689203401384363706793986485885440121
16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650496590712511252285651639106946065207945533638967006292554765249225998938041188226886788009973067856458696750906671494954059950549179271386985133075548549580134988472982802067434038956599873142170078749639418012172512091402357259754616754822564704948167365865823247013034124612050000707594985881023213092009269635091951503361482028872303431603984166237134290452175784064677481030687632778717485937144402213085086689203401384363706793986485885440145
16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650496590712511252285651639106946065207945533638967006292554765249225998938041188226886788009973067856458696750906671494954059950549179271386985133075548549580134988472982802067434038956599873142170078749639418012172512091402357259754616754822564704948167365865823247013034124612050000707594985881023213092009269635091951503361482028872303431603984166237134290452175784064677481030687632778717485937144402213085086689203401384363706793986485885440169
16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650496590712511252285651639106946065207945533638967006292554765249225998938041188226886788009973067856458696750906671494954059950549179271386985133075548549580134988472982802067434038956599873142170078749639418012172512091402357259754616754822564704948167365865823247013034124612050000707594985881023213092009269635091951503361482028872303431603984166237134290452175784064677481030687632778717485937144402213085086689203401384363706793986485885440181
16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650496590712511252285651639106946065207945533638967006292554765249225998938041188226886788009973067856458696750906671494954059950549179271386985133075548549580134988472982802067434038956599873142170078749639418012172512091402357259754616754822564704948167365865823247013034124612050000707594985881023213092009269635091951503361482028872303431603984166237134290452175784064677481030687632778717485937144402213085086689203401384363706793986485885440193

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

It still seems to produce candidates.

[QUOTE]
To get none with the second you would need to include a primality test on the exponent
itself.[/QUOTE]

I used the second one because the heuristic was made over prime exponents only. However, the primality test (confidence [TEX]1-(1/4)^{10}[/TEX]) [I]is[/I] there (in post [URL="http://www.mersenneforum.org/showpost.php?p=475625&postcount=8"]#8[/URL]), it consist of these lines
[CODE]
for ok := false; !ok; {
n.Add(n, _2)
ok = n.ProbablyPrime(10)
}[/CODE]

The primality test seems to work, as all the produced exponents are now indeed classified to be a PRP by factordb:

[url]http://factordb.com/index.php?query=16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683649723338597261540859709106693445015368660108875402892037762722856601385686451583086379814239252957953005801733903235334768021827287204324559826013062959085878285717391588345261898837334566599719994757523969587123189603679962754697914110034263373229505763160429561915518489424177512542712831644517522108470961969379521122124794494954390525271086287089480256791021142308215454899587236903245344574894274601709193034606462056949274261957344278901120001[/url]
[url]http://factordb.com/index.php?query=16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683649723338597261540859709106693445015368660108875402892037762722856601385686451583086379814239252957953005801733903235334768021827287204324559826013062959085878285717391588345261898837334566599719994757523969587123189603679962754697914110034263373229505763160429561915518489424177512542712831644517522108470961969379521122124794494954390525271086287089480256791021142308215454899587236903245344574894274601709193034606462056949274261957344278901121117[/url]
[url]http://factordb.com/index.php?query=16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683649723338597261540859709106693445015368660108875402892037762722856601385686451583086379814239252957953005801733903235334768021827287204324559826013062959085878285717391588345261898837334566599719994757523969587123189603679962754697914110034263373229505763160429561915518489424177512542712831644517522108470961969379521122124794494954390525271086287089480256791021142308215454899587236903245344574894274601709193034606462056949274261957344278901122551[/url]
[url]http://factordb.com/index.php?query=16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683649723338597261540859709106693445015368660108875402892037762722856601385686451583086379814239252957953005801733903235334768021827287204324559826013062959085878285717391588345261898837334566599719994757523969587123189603679962754697914110034263373229505763160429561915518489424177512542712831644517522108470961969379521122124794494954390525271086287089480256791021142308215454899587236903245344574894274601709193034606462056949274261957344278901123251[/url]
[url]http://factordb.com/index.php?query=16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683649723338597261540859709106693445015368660108875402892037762722856601385686451583086379814239252957953005801733903235334768021827287204324559826013062959085878285717391588345261898837334566599719994757523969587123189603679962754697914110034263373229505763160429561915518489424177512542712831644517522108470961969379521122124794494954390525271086287089480256791021142308215454899587236903245344574894274601709193034606462056949274261957344278901124931[/url]
[url]http://factordb.com/index.php?query=16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683649723338597261540859709106693445015368660108875402892037762722856601385686451583086379814239252957953005801733903235334768021827287204324559826013062959085878285717391588345261898837334566599719994757523969587123189603679962754697914110034263373229505763160429561915518489424177512542712831644517522108470961969379521122124794494954390525271086287089480256791021142308215454899587236903245344574894274601709193034606462056949274261957344278901125441[/url]

That all makes me think the problem must be somewhere else. However, I haven't found
where yet. Please take another look, thank you in advance.