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