- **gophne**
(*https://www.mersenneforum.org/forumdisplay.php?f=149*)

- - **"New" primality test/check**
(*https://www.mersenneforum.org/showthread.php?t=22838*)

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

All times are UTC. The time now is 05:16. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.