20180106, 10:39  #221  
Nov 2008
2×3^{3}×43 Posts 
CRGreathouse has answered most of the questions so there isn't much more for me to say.
Quote:
Quote:
Quote:


20180106, 13:14  #222 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
My thought was work backwards as though the 2 in n+2 was n+1 and solve the congruence to be 0.
Last fiddled with by science_man_88 on 20180106 at 13:36 
20180106, 16:43  #223 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Equivalents generalize to:
2^(n1)==1 mod n Subtract 2^y or some natural yβ€n 2^(n1)2^y == n(2^y1) mod n Divide by 2^y 2^(ny1)1 == (n(2^y1))/(2^y) mod n Replace n by n+2^y 2^(n+2^yy1)1== (n+1)/(2^y) mod (n+2^y) Unless I messed up a step.edit: or the statement for Fermat's theorem like I did originally. Edit 2: I think you may find it can be changed still to a modular arithmetic statement about double mersennes with 2 more steps though. Last fiddled with by science_man_88 on 20180106 at 17:12 Reason: Fixed statement of theorem 
20180106, 21:50  #224 
Feb 2017
3×5×11 Posts 
Nth Value Primality Algorithm
Hi Everybody
Time for playing with another possible new/unusual ? Primality Algorithm on the mersenneforum.org>Extra Stuff>Blogorrhea>gophne>"New"primality test/check Forum. Not sure if anybody would be interested, but at risk of missing out on a possible "new" primality test/algorithm, which is the equivalent to missing out on M50 The Algorithm is as follows; For the series of odd numbers, where the 1st term of the series is 1, to the nth term VALUE, increment 2, step 1, where n is an element of the set of integers =>1, and the nth term results in the series having an odd number of terms, In sigma notation the series would look something like this: nth (VALUE) Z (2n1) Z representing Sigma in lieu of n=1 Then for any of the terms of the series so constituted, starting at the 2nd term to the term whose value would be equal to the value of the nth value 2. If any of the terms in the test range is a multiple of, or shares a common factor with, the nth value, then the nth value is Composite, else Prime. To do an example just so to clarify the wording (I am not familiar with Latex on this Site yet); Let the nthvalue be equal to 7, then the algorithm series, applying Sigma, would be; 01,03,05,07 The test "range" according to the algorithm would be; 03,05......................................................Constituting the "seed" terms in the test range. 03 + 14 =17 05 + 14 =19 Since both these derived values are not multiples, or do not share a common factor with any of the "seed" terms, the nth value , namely "7" is Prime, as per the algorithm. Let us try nth value is equal to 2047 The test range would be; 03,05,07,09,11,13,15.......2045.........Test range/Seed terms For this test range the derived algorithm values would be seed terms + 4094 The Seed/Algorithm pairs formed would be; (3,34097) (5,4099),(7,5001),(9,5003), (11, 5005), (13,5007)...... But the 5th term of these pairings share a common factor "11", so according to the algorithm the nth value is Composite. Could anybody confirm or refute that this primality algorithm is true for all Composites/Primes. Would the above constitute a legitimate primality algorithm? [I]Caveat: Not sure if anybody else worked on or published any similar primality algorithms, but I could not find anything similar looking it up in Wikipedia. Last fiddled with by gophne on 20180106 at 21:55 Reason: Formating spaces 
20180106, 21:59  #225  
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
Quote:
Last fiddled with by science_man_88 on 20180106 at 22:09 

20180107, 06:13  #226 
Feb 2017
3×5×11 Posts 
Hi science_man_88
I love you, but your monosyllabic answers does not help. Please explain some more or even better, do the "offuscated trial division" for the two examples given. Thanx. Last fiddled with by gophne on 20180107 at 06:14 Reason: typo's 
20180107, 06:44  #227 
Jun 2003
11370_{8} Posts 
So your algorithm:
Take odd N (which we're checking if it is prime or composite) For all odd n = 1,3,... < N, check if gcd(n, n+2*N) > 1. if so, you found a factor of N, and it is composite, otherwise it is prime. Trial division algortihm: Take odd N (which we're checking if it is prime or composite) For all odd prime n = 3,5,7,.. < sqrt(N), check if n divides N. if so, you found a factor of N, and it is composite, otherwise it is prime. As you can see, you're just doing a much slower version of trial division. What? The gcd(n, n+2*N) is nothing like checking if "n divides N"? Please... Stop kidding yourselves. 
20180107, 07:28  #228  
Feb 2017
3×5×11 Posts 
Quote:
Not exactly I think. Trial division divided the TEST number by the set of odd numbers up to the sqaure root of that number, until a possible divisor (that leaves a residue of 0 is found). If no such divisors are found, the number is Prime. The algorithm states that if any of the odd numbers + 2 times the nth Value in the test range has a common factor, independant of the number being tested. I know it would be cumbersome for very large numbers (so is trial division), but I am trying to establish a "Primality" Test relationship here. There are many Primality Tests out there that are very cumbersome or even incalculable after a few steps, but are still recognised as Primality Tests nevertheless. Thanks for distilling "my" algorithm into a more clear form for readers to evaluate the "primality test" aspect of it. Much better than my attempt, so if readers could please use axn's form of it. 

20180107, 09:24  #229  
Nov 2008
2×3^{3}×43 Posts 
Quote:
Quote:
I guess that technically counts as a "primality test" in that it does correctly determine primality or otherwise of N. But it's easy to come up with useless primality tests. Here's one: if N>4, then N is prime if and only if N does not divide (N1)!. Unlike trial division, it's got only one step, so what could possibly go wrong...? As for why gcd(n, n+2N) = gcd(n, N), it's time for another basic number theory lesson: Suppose d divides n and n+2N. Then d must divide their difference, which is 2N. But d divides n, which is odd, so d is odd, and thus d must divide N. Conversely, suppose d divides n and N. Then clearly d divides n+N+N = n+2N. So the sets of common factors of (n, n+2N) and (n, N) are exactly the same, and in particular gcd(n, n+2N) = gcd(n, N). Last fiddled with by 10metreh on 20180107 at 09:25 

20180107, 11:10  #230  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2960_{16} Posts 
Uncompromisingly monosyllabic
Quote:
I think "You hide a test which splits by small primes, one by one" may be good. Paul. Last fiddled with by xilman on 20180107 at 11:11 

20180107, 11:30  #231 
"Composite as Heck"
Oct 2017
2·383 Posts 
Petition to call the simplified form of this test the GophneAxn Little Lemma.
Last fiddled with by M344587487 on 20180107 at 11:31 Reason: word 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
gpuOwL: an OpenCL program for Mersenne primality testing  preda  GpuOwl  2691  20210212 13:53 
GQQ: a "deterministic" "primality" test in O(ln n)^2  Chair Zhuang  Miscellaneous Math  21  20180326 22:33 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
"New primality proving test from Alex Petrov"  ewmayer  Math  11  20070423 19:07 
P1 B1/B2 selection with "Test=" vs "Pfactor="  James Heinrich  Software  2  20050319 21:58 