+/- 6 Primality Test

a1call · 2018-11-04, 17:42

Hi all,
Is there an efficient way of primality testing p+6 and/or p-6 when it is known that p is prime or otherwise (more generally) all its factors are known?
I am assuming that there is not even for any special forms.
Thank you for your time.

ETA I am only interested in deterministic tests here.

Batalov · 2018-11-04, 18:02

"Walk before running", some people say.

What's wrong with +/-2 Primality Test? Or are you saying that this one is too easy?

a1call · 2018-11-04, 18:24

I don't have a solution for either but for what I am working on +/-6 shortcut would be useful while +/-2 won't be of any use. Any prime +/-2 will have one of them with a factor of 3 and won't be prime (5 not withstanding). Not so with 6.

science_man_88 · 2018-11-04, 18:58

Quote:

Originally Posted by a1call

I don't have a solution for either but for what I am working on +/-6 shortcut would be useful while +/-2 won't be of any use. Any prime +/-2 will have one of them with a factor of 3 and won't be prime (5 not withstanding). Not so with 6.

via a version of the sieve of sundaram p a prime

is not
6*((6*j+1)*i+j)+1 or 6*((6*j-1)*i+j)-1or 6*((6*j-1)*i-j)+1
enjoy

a1call · 2018-11-04, 19:18

Interesting algorithm SM. Thank you for introducing me to it.
But I suspect that won't be of direct use for record primes. In particular I assume some of the record (Mersenne perhaps) primes are (not highly but still) likely to have neighboring primes that are 6 off. Knowing that they are prime does not seem to have been useful in proving therm prime. I recall the board members here checking to see if the M50 was twin before publication. I assume if it was they would have been restricted to usual primality tests based on +/-1 factoring independent of M50 being prime.

science_man_88 · 2018-11-04, 19:27

Quote:

Originally Posted by a1call

Interesting algorithm SM. Thank you for introducing me to it.
But I suspect that won't be of direct use for record primes. In particular I assume some of the record (Mersenne perhaps) primes are (not highly but still) likely to have neighboring primes that are 6 off. Knowing that they are prime does not seem to have been useful in proving therm prime. I recall the board members here checking to see if the M50 was twin before publication. I assume if it was they would have been restricted to usual primality tests based on +/-1 factoring independent of M50 being prime.

aka you suspect http://oeis.org/A002450
to have members a(n) such that a(n)-1 or a(n)+1 create primes.

a1call · 2018-11-04, 19:49

Nah, that's not it. If you must know I am working on projecting triples of primes which are 6 off into twins. It's work in progress and I am too lazy to continue right now.

If you (or anyone else for that matter) can find any prior research in the area, I would appreciate a reference to save me time.

science_man_88 · 2018-11-04, 21:56

Quote:

Originally Posted by a1call

Nah, that's not it. If you must know I am working on projecting triples of primes which are 6 off into twins. It's work in progress and I am too lazy to continue right now.

If you (or anyone else for that matter) can find any prior research in the area, I would appreciate a reference to save me time.

there are 4 triples that work mod 5 (without creating 5 itself):

(6*Mod(0,5)+1,6*Mod(1,5)+1,6*Mod(2,5)+1)
(6*Mod(1,5)+1,6*Mod(2,5)+1,6*Mod(3,5)+1)
(6*Mod(2,5)-1,6*Mod(3,5)-1,6*Mod(4,5)-1)
(6*Mod(3,5)-1,6*Mod(4,5)-1,6*Mod(0,5)-1)

Dr Sardonicus · 2018-11-04, 21:57

It's gratuitously confusing to use p for a prime -- then say "or otherwise."

We have n - a, n, n + a is an "admissible triple" in the sense of the "prime k-tuples conjecture" when x^3 - a^2*x is not automatically divisible by some prime.

Since the characteristic polynomial of the field of p elements is x^p - x, here we can only have x^3 - a^2*x automatically divisible by p = 2 or 3.

If a is not divisible by 2,

x^3 - a^2*x == a^3 - x (mod 2) which is divisible by x^2 - x; hence x^2 - a^2*x is always even. Thus, in order for n - a, n, n + a to be admissible, a must be even.

If a is not divisible by 3, then a^2 == 1 (mod 3) and x^3 - a^2*x == x^3 - x (mod 3), so x^2 - a^2*x is divisible by 3. So in order to be admissible, a must be divisible by 3.

If a is divisible by 6, then n - a, n, n + a is admissible. According to the prime k-tuples conjecture, the number of n's up to X for which all three of n - a, n, n + a are prime, is, asymptotically, a constant (which depends on a) times X/(ln(X))^3.

Now the pair n - a, n + a is also admissible (in fact, this pair is admissible for any positive integer a, but let's stick to a divisible by 6). In this case, the conjecture says that the number of n's up to X for which both n - a and n + a are prime, is asymptotically a constant (which depends on a) times X/(ln(X))^2.

So, the number of prime pairs n - a, n + a is likely much greater than the number of prime triples n - a, n, n + a, assuming 6|a. It's almost certainly greater if gcd(6,a) < 6
:-D

I doubt knowing the factorization of n has much bearing on deciding whether n - a and n + a are both prime. What I would look at, is eliminating n's for which either n - a or n + a have any small prime factors.

a1call · 2018-11-04, 23:21

I will have to get back to work tomorrow. So if anyone can finish solving the algorithm be my guest.

PARI-GP Code:

Code:

\\CJZ-100-B Twin-Prime Generator based on Wilson's Theorem & my infamous Theorem 1 by Rashid Naimi


p=6
forprime (q=19^0,19^5,{
  \\print(q);
  a=((q-2)!-1)/q;
  if(gcd(a-p,(q-2)!)<2 && gcd(a+p,(q-2)!)<2,
    c=(a+p)*q-(q-2)!;
    d=(q-2)!-(a-p)*q;
    print("\n**** Found Twin-Primes based on Prime ",q," ****");
    print("** ",c," & ",d," **");
  );
})

Code:

**** Found Twin-Primes based on Prime 2 ****
** 11 & 13 **

**** Found Twin-Primes based on Prime 3 ****
** 17 & 19 **

**** Found Twin-Primes based on Prime 5 ****
** 29 & 31 **

**** Found Twin-Primes based on Prime 7 ****
** 41 & 43 **

**** Found Twin-Primes based on Prime 17 ****
** 101 & 103 **

**** Found Twin-Primes based on Prime 23 ****
** 137 & 139 **

**** Found Twin-Primes based on Prime 47 ****
** 281 & 283 **

**** Found Twin-Primes based on Prime 103 ****
** 617 & 619 **

**** Found Twin-Primes based on Prime 107 ****
** 641 & 643 **

**** Found Twin-Primes based on Prime 137 ****
** 821 & 823 **

**** Found Twin-Primes based on Prime 283 ****
** 1697 & 1699 **

**** Found Twin-Primes based on Prime 313 ****
** 1877 & 1879 **

**** Found Twin-Primes based on Prime 347 ****
** 2081 & 2083 **

**** Found Twin-Primes based on Prime 373 ****
** 2237 & 2239 **

**** Found Twin-Primes based on Prime 397 ****
** 2381 & 2383 **

**** Found Twin-Primes based on Prime 443 ****
** 2657 & 2659 **

**** Found Twin-Primes based on Prime 467 ****
** 2801 & 2803 **

**** Found Twin-Primes based on Prime 577 ****
** 3461 & 3463 **

**** Found Twin-Primes based on Prime 593 ****
** 3557 & 3559 **

**** Found Twin-Primes based on Prime 653 ****
** 3917 & 3919 **

**** Found Twin-Primes based on Prime 773 ****
** 4637 & 4639 **

**** Found Twin-Primes based on Prime 787 ****
** 4721 & 4723 **

**** Found Twin-Primes based on Prime 907 ****
** 5441 & 5443 **

**** Found Twin-Primes based on Prime 1033 ****
** 6197 & 6199 **

**** Found Twin-Primes based on Prime 1117 ****
** 6701 & 6703 **

**** Found Twin-Primes based on Prime 1423 ****
** 8537 & 8539 **

**** Found Twin-Primes based on Prime 1433 ****
** 8597 & 8599 **

**** Found Twin-Primes based on Prime 1613 ****
** 9677 & 9679 **

**** Found Twin-Primes based on Prime 1823 ****
** 10937 & 10939 **

**** Found Twin-Primes based on Prime 2027 ****
** 12161 & 12163 **

**** Found Twin-Primes based on Prime 2063 ****
** 12377 & 12379 **

**** Found Twin-Primes based on Prime 2137 ****
** 12821 & 12823 **

**** Found Twin-Primes based on Prime 2153 ****
** 12917 & 12919 **

**** Found Twin-Primes based on Prime 2203 ****
** 13217 & 13219 **

**** Found Twin-Primes based on Prime 2287 ****
** 13721 & 13723 **

**** Found Twin-Primes based on Prime 2293 ****
** 13757 & 13759 **

**** Found Twin-Primes based on Prime 2333 ****
** 13997 & 13999 **

**** Found Twin-Primes based on Prime 2347 ****
** 14081 & 14083 **

**** Found Twin-Primes based on Prime 2677 ****
** 16061 & 16063 **

**** Found Twin-Primes based on Prime 2903 ****
** 17417 & 17419 **

**** Found Twin-Primes based on Prime 3257 ****
** 19541 & 19543 **

**** Found Twin-Primes based on Prime 3307 ****
** 19841 & 19843 **

**** Found Twin-Primes based on Prime 3407 ****
** 20441 & 20443 **

**** Found Twin-Primes based on Prime 3413 ****
** 20477 & 20479 **

**** Found Twin-Primes based on Prime 3593 ****
** 21557 & 21559 **

**** Found Twin-Primes based on Prime 3623 ****
** 21737 & 21739 **

**** Found Twin-Primes based on Prime 3673 ****
** 22037 & 22039 **

**** Found Twin-Primes based on Prime 3923 ****
** 23537 & 23539 **

**** Found Twin-Primes based on Prime 4153 ****
** 24917 & 24919 **

**** Found Twin-Primes based on Prime 4217 ****
** 25301 & 25303 **

**** Found Twin-Primes based on Prime 4447 ****
** 26681 & 26683 **

**** Found Twin-Primes based on Prime 4547 ****
** 27281 & 27283 **

**** Found Twin-Primes based on Prime 4597 ****
** 27581 & 27583 **

**** Found Twin-Primes based on Prime 4657 ****
** 27941 & 27943 **

**** Found Twin-Primes based on Prime 5023 ****
** 30137 & 30139 **

**** Found Twin-Primes based on Prime 5197 ****
** 31181 & 31183 **

**** Found Twin-Primes based on Prime 5387 ****
** 32321 & 32323 **

**** Found Twin-Primes based on Prime 5407 ****
** 32441 & 32443 **

**** Found Twin-Primes based on Prime 5693 ****
** 34157 & 34159 **

**** Found Twin-Primes based on Prime 5717 ****
** 34301 & 34303 **

**** Found Twin-Primes based on Prime 5807 ****
** 34841 & 34843 **

**** Found Twin-Primes based on Prime 5827 ****
** 34961 & 34963 **

**** Found Twin-Primes based on Prime 6373 ****
** 38237 & 38239 **

**** Found Twin-Primes based on Prime 6673 ****
** 40037 & 40039 **

**** Found Twin-Primes based on Prime 6857 ****
** 41141 & 41143 **

**** Found Twin-Primes based on Prime 6863 ****
** 41177 & 41179 **

**** Found Twin-Primes based on Prime 6997 ****
** 41981 & 41983 **

**** Found Twin-Primes based on Prime 7297 ****
** 43781 & 43783 **

**** Found Twin-Primes based on Prime 7523 ****
** 45137 & 45139 **

**** Found Twin-Primes based on Prime 7963 ****
** 47777 & 47779 **

**** Found Twin-Primes based on Prime 8377 ****
** 50261 & 50263 **

**** Found Twin-Primes based on Prime 8573 ****
** 51437 & 51439 **

**** Found Twin-Primes based on Prime 9067 ****
** 54401 & 54403 **

**** Found Twin-Primes based on Prime 9203 ****
** 55217 & 55219 **

**** Found Twin-Primes based on Prime 9277 ****
** 55661 & 55663 **

**** Found Twin-Primes based on Prime 9413 ****
** 56477 & 56479 **

**** Found Twin-Primes based on Prime 9433 ****
** 56597 & 56599 **

**** Found Twin-Primes based on Prime 9767 ****
** 58601 & 58603 **

**** Found Twin-Primes based on Prime 9907 ****
** 59441 & 59443 **

**** Found Twin-Primes based on Prime 10357 ****
** 62141 & 62143 **

**** Found Twin-Primes based on Prime 10973 ****
** 65837 & 65839 **

**** Found Twin-Primes based on Prime 11483 ****
** 68897 & 68899 **

**** Found Twin-Primes based on Prime 11743 ****
** 70457 & 70459 **

**** Found Twin-Primes based on Prime 11807 ****
** 70841 & 70843 **

**** Found Twin-Primes based on Prime 11813 ****
** 70877 & 70879 **

**** Found Twin-Primes based on Prime 11833 ****
** 70997 & 70999 **

**** Found Twin-Primes based on Prime 12037 ****
** 72221 & 72223 **

**** Found Twin-Primes based on Prime 12227 ****
** 73361 & 73363 **

**** Found Twin-Primes based on Prime 12757 ****
** 76541 & 76543 **

**** Found Twin-Primes based on Prime 13163 ****
** 78977 & 78979 **

**** Found Twin-Primes based on Prime 13463 ****
** 80777 & 80779 **

**** Found Twin-Primes based on Prime 14087 ****
** 84521 & 84523 **

**** Found Twin-Primes based on Prime 14143 ****
** 84857 & 84859 **

**** Found Twin-Primes based on Prime 14303 ****
** 85817 & 85819 **

**** Found Twin-Primes based on Prime 14537 ****
** 87221 & 87223 **

**** Found Twin-Primes based on Prime 14593 ****
** 87557 & 87559 **

**** Found Twin-Primes based on Prime 14723 ****
** 88337 & 88339 **

**** Found Twin-Primes based on Prime 14983 ****
** 89897 & 89899 **

**** Found Twin-Primes based on Prime 15073 ****
** 90437 & 90439 **

**** Found Twin-Primes based on Prime 15137 ****
** 90821 & 90823 **

**** Found Twin-Primes based on Prime 15493 ****
** 92957 & 92959 **

**** Found Twin-Primes based on Prime 15733 ****
** 94397 & 94399 **

**** Found Twin-Primes based on Prime 15907 ****
** 95441 & 95443 **

**** Found Twin-Primes based on Prime 16193 ****
** 97157 & 97159 **

**** Found Twin-Primes based on Prime 16217 ****
** 97301 & 97303 **

**** Found Twin-Primes based on Prime 16427 ****
** 98561 & 98563 **

**** Found Twin-Primes based on Prime 17033 ****
** 102197 & 102199 **

**** Found Twin-Primes based on Prime 17467 ****
** 104801 & 104803 **

**** Found Twin-Primes based on Prime 17713 ****
** 106277 & 106279 **

**** Found Twin-Primes based on Prime 17827 ****
** 106961 & 106963 **

**** Found Twin-Primes based on Prime 18077 ****
** 108461 & 108463 **

**** Found Twin-Primes based on Prime 18253 ****
** 109517 & 109519 **

**** Found Twin-Primes based on Prime 18307 ****
** 109841 & 109843 **

**** Found Twin-Primes based on Prime 18413 ****
** 110477 & 110479 **

**** Found Twin-Primes based on Prime 18793 ****
** 112757 & 112759 **

**** Found Twin-Primes based on Prime 19267 ****
** 115601 & 115603 **

**** Found Twin-Primes based on Prime 19423 ****
** 116537 & 116539 **

**** Found Twin-Primes based on Prime 19507 ****
** 117041 & 117043 **

**** Found Twin-Primes based on Prime 19583 ****
** 117497 & 117499 **

**** Found Twin-Primes based on Prime 19603 ****
** 117617 & 117619 **

**** Found Twin-Primes based on Prime 19997 ****
** 119981 & 119983 **

**** Found Twin-Primes based on Prime 20123 ****
** 120737 & 120739 **

**** Found Twin-Primes based on Prime 20177 ****
** 121061 & 121063 **

**** Found Twin-Primes based on Prime 20563 ****
** 123377 & 123379 **

**** Found Twin-Primes based on Prime 20717 ****
** 124301 & 124303 **

**** Found Twin-Primes based on Prime 20983 ****
** 125897 & 125899 **

**** Found Twin-Primes based on Prime 21143 ****
** 126857 & 126859 **

**** Found Twin-Primes based on Prime 22073 ****
** 132437 & 132439 **

**** Found Twin-Primes based on Prime 22447 ****
** 134681 & 134683 **

**** Found Twin-Primes based on Prime 22853 ****
** 137117 & 137119 **

**** Found Twin-Primes based on Prime 23447 ****
** 140681 & 140683 **

**** Found Twin-Primes based on Prime 23473 ****
** 140837 & 140839 **

**** Found Twin-Primes based on Prime 23537 ****
** 141221 & 141223 **

**** Found Twin-Primes based on Prime 23917 ****
** 143501 & 143503 **

**** Found Twin-Primes based on Prime 24337 ****
** 146021 & 146023 **

**** Found Twin-Primes based on Prime 24677 ****
** 148061 & 148063 **

**** Found Twin-Primes based on Prime 25037 ****
** 150221 & 150223 **

**** Found Twin-Primes based on Prime 25147 ****
** 150881 & 150883 **

**** Found Twin-Primes based on Prime 25693 ****
** 154157 & 154159 **

**** Found Twin-Primes based on Prime 25847 ****
** 155081 & 155083 **

**** Found Twin-Primes based on Prime 25867 ****
** 155201 & 155203 **

**** Found Twin-Primes based on Prime 26113 ****
** 156677 & 156679 **

**** Found Twin-Primes based on Prime 26203 ****
** 157217 & 157219 **

**** Found Twin-Primes based on Prime 26357 ****
** 158141 & 158143 **

**** Found Twin-Primes based on Prime 26393 ****
** 158357 & 158359 **

**** Found Twin-Primes based on Prime 26813 ****
** 160877 & 160879 **

**** Found Twin-Primes based on Prime 26927 ****
** 161561 & 161563 **

**** Found Twin-Primes based on Prime 26987 ****
** 161921 & 161923 **

**** Found Twin-Primes based on Prime 27437 ****
** 164621 & 164623 **

**** Found Twin-Primes based on Prime 27617 ****
** 165701 & 165703 **

**** Found Twin-Primes based on Prime 27767 ****
** 166601 & 166603 **

**** Found Twin-Primes based on Prime 28513 ****
** 171077 & 171079 **

**** Found Twin-Primes based on Prime 28627 ****
** 171761 & 171763 **

**** Found Twin-Primes based on Prime 28703 ****
** 172217 & 172219 **

**** Found Twin-Primes based on Prime 28753 ****
** 172517 & 172519 **

**** Found Twin-Primes based on Prime 28837 ****
** 173021 & 173023 **

**** Found Twin-Primes based on Prime 29297 ****
** 175781 & 175783 **

**** Found Twin-Primes based on Prime 29327 ****
** 175961 & 175963 **

**** Found Twin-Primes based on Prime 29803 ****
** 178817 & 178819 **

**** Found Twin-Primes based on Prime 29983 ****
** 179897 & 179899 **

**** Found Twin-Primes based on Prime 30133 ****
** 180797 & 180799 **

**** Found Twin-Primes based on Prime 30293 ****
** 181757 & 181759 **

**** Found Twin-Primes based on Prime 30553 ****
** 183317 & 183319 **

**** Found Twin-Primes based on Prime 30817 ****
** 184901 & 184903 **

**** Found Twin-Primes based on Prime 31063 ****
** 186377 & 186379 **

**** Found Twin-Primes based on Prime 31223 ****
** 187337 & 187339 **

**** Found Twin-Primes based on Prime 31477 ****
** 188861 & 188863 **

**** Found Twin-Primes based on Prime 31573 ****
** 189437 & 189439 **

**** Found Twin-Primes based on Prime 31883 ****
** 191297 & 191299 **

**** Found Twin-Primes based on Prime 32057 ****
** 192341 & 192343 **

**** Found Twin-Primes based on Prime 32077 ****
** 192461 & 192463 **

**** Found Twin-Primes based on Prime 32083 ****
** 192497 & 192499 **

**** Found Twin-Primes based on Prime 32323 ****
** 193937 & 193939 **

**** Found Twin-Primes based on Prime 32713 ****
** 196277 & 196279 **

**** Found Twin-Primes based on Prime 32933 ****
** 197597 & 197599 **

**** Found Twin-Primes based on Prime 32993 ****
** 197957 & 197959 **

**** Found Twin-Primes based on Prime 33037 ****
** 198221 & 198223 **

**** Found Twin-Primes based on Prime 33073 ****
** 198437 & 198439 **

**** Found Twin-Primes based on Prime 33637 ****
** 201821 & 201823 **

**** Found Twin-Primes based on Prime 33773 ****
** 202637 & 202639 **

**** Found Twin-Primes based on Prime 34667 ****
** 208001 & 208003 **

**** Found Twin-Primes based on Prime 35053 ****
** 210317 & 210319 **

**** Found Twin-Primes based on Prime 35747 ****
** 214481 & 214483 **

**** Found Twin-Primes based on Prime 35753 ****
** 214517 & 214519 **

**** Found Twin-Primes based on Prime 36263 ****
** 217577 & 217579 **

**** Found Twin-Primes based on Prime 36923 ****
** 221537 & 221539 **

**** Found Twin-Primes based on Prime 36943 ****
** 221657 & 221659 **

**** Found Twin-Primes based on Prime 37223 ****
** 223337 & 223339 **

**** Found Twin-Primes based on Prime 37307 ****
** 223841 & 223843 **

**** Found Twin-Primes based on Prime 37537 ****
** 225221 & 225223 **

**** Found Twin-Primes based on Prime 37657 ****
** 225941 & 225943 **

**** Found Twin-Primes based on Prime 38273 ****
** 229637 & 229639 **

**** Found Twin-Primes based on Prime 38327 ****
** 229961 & 229963 **

**** Found Twin-Primes based on Prime 38903 ****
** 233417 & 233419 **

**** Found Twin-Primes based on Prime 39163 ****
** 234977 & 234979 **

**** Found Twin-Primes based on Prime 39727 ****
** 238361 & 238363 **

**** Found Twin-Primes based on Prime 40343 ****
** 242057 & 242059 **

**** Found Twin-Primes based on Prime 40693 ****
** 244157 & 244159 **

**** Found Twin-Primes based on Prime 40903 ****
** 245417 & 245419 **

**** Found Twin-Primes based on Prime 40927 ****
** 245561 & 245563 **

**** Found Twin-Primes based on Prime 41333 ****
** 247997 & 247999 **

...

Notes:
* There is a way to test the candidacy of q for Twin-Primes generation directly using q rather than a via Modular-Arithmetic. Mod (q,p') x Mod (a,p') = p'-1 for all primes p' < q
But I am too lazy to implement it. Find an efficient way of determining that a-6 & a+6 are coprime to (q-2)! and you will potentially have a formulaic method for generating twin primes.

That's all I have so far and can't think of a way to proceed any further.

Thank you for your time and all the replies.

science_man_88 · 2018-11-05, 00:13

Quote:

Originally Posted by a1call

I will have to get back to work tomorrow. So if anyone can finish solving the algorithm be my guest.

PARI-GP Code:

Code:

\\CJZ-100-B Twin-Prime Generator based on Wilson's Theorem & my infamous Theorem 1 by Rashid Naimi


p=6
forprime (q=19^0,19^5,{
  \\print(q);
  a=((q-2)!-1)/q;
  if(gcd(a-p,(q-2)!)<2 && gcd(a+p,(q-2)!)<2,
    c=(a+p)*q-(q-2)!;
    d=(q-2)!-(a-p)*q;
    print("\n**** Found Twin-Primes based on Prime ",q," ****");
    print("** ",c," & ",d," **");
  );
})

Code:

**** Found Twin-Primes based on Prime 2 ****
** 11 & 13 **

**** Found Twin-Primes based on Prime 3 ****
** 17 & 19 **

**** Found Twin-Primes based on Prime 5 ****
** 29 & 31 **

**** Found Twin-Primes based on Prime 7 ****
** 41 & 43 **

**** Found Twin-Primes based on Prime 17 ****
** 101 & 103 **

**** Found Twin-Primes based on Prime 23 ****
** 137 & 139 **

**** Found Twin-Primes based on Prime 47 ****
** 281 & 283 **

**** Found Twin-Primes based on Prime 103 ****
** 617 & 619 **

**** Found Twin-Primes based on Prime 107 ****
** 641 & 643 **

**** Found Twin-Primes based on Prime 137 ****
** 821 & 823 **

**** Found Twin-Primes based on Prime 283 ****
** 1697 & 1699 **

**** Found Twin-Primes based on Prime 313 ****
** 1877 & 1879 **

**** Found Twin-Primes based on Prime 347 ****
** 2081 & 2083 **

**** Found Twin-Primes based on Prime 373 ****
** 2237 & 2239 **

**** Found Twin-Primes based on Prime 397 ****
** 2381 & 2383 **

**** Found Twin-Primes based on Prime 443 ****
** 2657 & 2659 **

**** Found Twin-Primes based on Prime 467 ****
** 2801 & 2803 **

**** Found Twin-Primes based on Prime 577 ****
** 3461 & 3463 **

**** Found Twin-Primes based on Prime 593 ****
** 3557 & 3559 **

**** Found Twin-Primes based on Prime 653 ****
** 3917 & 3919 **

**** Found Twin-Primes based on Prime 773 ****
** 4637 & 4639 **

**** Found Twin-Primes based on Prime 787 ****
** 4721 & 4723 **

**** Found Twin-Primes based on Prime 907 ****
** 5441 & 5443 **

**** Found Twin-Primes based on Prime 1033 ****
** 6197 & 6199 **

**** Found Twin-Primes based on Prime 1117 ****
** 6701 & 6703 **

**** Found Twin-Primes based on Prime 1423 ****
** 8537 & 8539 **

**** Found Twin-Primes based on Prime 1433 ****
** 8597 & 8599 **

**** Found Twin-Primes based on Prime 1613 ****
** 9677 & 9679 **

**** Found Twin-Primes based on Prime 1823 ****
** 10937 & 10939 **

**** Found Twin-Primes based on Prime 2027 ****
** 12161 & 12163 **

**** Found Twin-Primes based on Prime 2063 ****
** 12377 & 12379 **

**** Found Twin-Primes based on Prime 2137 ****
** 12821 & 12823 **

**** Found Twin-Primes based on Prime 2153 ****
** 12917 & 12919 **

**** Found Twin-Primes based on Prime 2203 ****
** 13217 & 13219 **

**** Found Twin-Primes based on Prime 2287 ****
** 13721 & 13723 **

**** Found Twin-Primes based on Prime 2293 ****
** 13757 & 13759 **

**** Found Twin-Primes based on Prime 2333 ****
** 13997 & 13999 **

**** Found Twin-Primes based on Prime 2347 ****
** 14081 & 14083 **

**** Found Twin-Primes based on Prime 2677 ****
** 16061 & 16063 **

**** Found Twin-Primes based on Prime 2903 ****
** 17417 & 17419 **

**** Found Twin-Primes based on Prime 3257 ****
** 19541 & 19543 **

**** Found Twin-Primes based on Prime 3307 ****
** 19841 & 19843 **

**** Found Twin-Primes based on Prime 3407 ****
** 20441 & 20443 **

**** Found Twin-Primes based on Prime 3413 ****
** 20477 & 20479 **

**** Found Twin-Primes based on Prime 3593 ****
** 21557 & 21559 **

**** Found Twin-Primes based on Prime 3623 ****
** 21737 & 21739 **

**** Found Twin-Primes based on Prime 3673 ****
** 22037 & 22039 **

**** Found Twin-Primes based on Prime 3923 ****
** 23537 & 23539 **

**** Found Twin-Primes based on Prime 4153 ****
** 24917 & 24919 **

**** Found Twin-Primes based on Prime 4217 ****
** 25301 & 25303 **

**** Found Twin-Primes based on Prime 4447 ****
** 26681 & 26683 **

**** Found Twin-Primes based on Prime 4547 ****
** 27281 & 27283 **

**** Found Twin-Primes based on Prime 4597 ****
** 27581 & 27583 **

**** Found Twin-Primes based on Prime 4657 ****
** 27941 & 27943 **

**** Found Twin-Primes based on Prime 5023 ****
** 30137 & 30139 **

**** Found Twin-Primes based on Prime 5197 ****
** 31181 & 31183 **

**** Found Twin-Primes based on Prime 5387 ****
** 32321 & 32323 **

**** Found Twin-Primes based on Prime 5407 ****
** 32441 & 32443 **

**** Found Twin-Primes based on Prime 5693 ****
** 34157 & 34159 **

**** Found Twin-Primes based on Prime 5717 ****
** 34301 & 34303 **

**** Found Twin-Primes based on Prime 5807 ****
** 34841 & 34843 **

**** Found Twin-Primes based on Prime 5827 ****
** 34961 & 34963 **

**** Found Twin-Primes based on Prime 6373 ****
** 38237 & 38239 **

**** Found Twin-Primes based on Prime 6673 ****
** 40037 & 40039 **

**** Found Twin-Primes based on Prime 6857 ****
** 41141 & 41143 **

**** Found Twin-Primes based on Prime 6863 ****
** 41177 & 41179 **

**** Found Twin-Primes based on Prime 6997 ****
** 41981 & 41983 **

**** Found Twin-Primes based on Prime 7297 ****
** 43781 & 43783 **

**** Found Twin-Primes based on Prime 7523 ****
** 45137 & 45139 **

**** Found Twin-Primes based on Prime 7963 ****
** 47777 & 47779 **

**** Found Twin-Primes based on Prime 8377 ****
** 50261 & 50263 **

**** Found Twin-Primes based on Prime 8573 ****
** 51437 & 51439 **

**** Found Twin-Primes based on Prime 9067 ****
** 54401 & 54403 **

**** Found Twin-Primes based on Prime 9203 ****
** 55217 & 55219 **

**** Found Twin-Primes based on Prime 9277 ****
** 55661 & 55663 **

**** Found Twin-Primes based on Prime 9413 ****
** 56477 & 56479 **

**** Found Twin-Primes based on Prime 9433 ****
** 56597 & 56599 **

**** Found Twin-Primes based on Prime 9767 ****
** 58601 & 58603 **

**** Found Twin-Primes based on Prime 9907 ****
** 59441 & 59443 **

**** Found Twin-Primes based on Prime 10357 ****
** 62141 & 62143 **

**** Found Twin-Primes based on Prime 10973 ****
** 65837 & 65839 **

**** Found Twin-Primes based on Prime 11483 ****
** 68897 & 68899 **

**** Found Twin-Primes based on Prime 11743 ****
** 70457 & 70459 **

**** Found Twin-Primes based on Prime 11807 ****
** 70841 & 70843 **

**** Found Twin-Primes based on Prime 11813 ****
** 70877 & 70879 **

**** Found Twin-Primes based on Prime 11833 ****
** 70997 & 70999 **

**** Found Twin-Primes based on Prime 12037 ****
** 72221 & 72223 **

**** Found Twin-Primes based on Prime 12227 ****
** 73361 & 73363 **

**** Found Twin-Primes based on Prime 12757 ****
** 76541 & 76543 **

**** Found Twin-Primes based on Prime 13163 ****
** 78977 & 78979 **

**** Found Twin-Primes based on Prime 13463 ****
** 80777 & 80779 **

**** Found Twin-Primes based on Prime 14087 ****
** 84521 & 84523 **

**** Found Twin-Primes based on Prime 14143 ****
** 84857 & 84859 **

**** Found Twin-Primes based on Prime 14303 ****
** 85817 & 85819 **

**** Found Twin-Primes based on Prime 14537 ****
** 87221 & 87223 **

**** Found Twin-Primes based on Prime 14593 ****
** 87557 & 87559 **

**** Found Twin-Primes based on Prime 14723 ****
** 88337 & 88339 **

**** Found Twin-Primes based on Prime 14983 ****
** 89897 & 89899 **

**** Found Twin-Primes based on Prime 15073 ****
** 90437 & 90439 **

**** Found Twin-Primes based on Prime 15137 ****
** 90821 & 90823 **

**** Found Twin-Primes based on Prime 15493 ****
** 92957 & 92959 **

**** Found Twin-Primes based on Prime 15733 ****
** 94397 & 94399 **

**** Found Twin-Primes based on Prime 15907 ****
** 95441 & 95443 **

**** Found Twin-Primes based on Prime 16193 ****
** 97157 & 97159 **

**** Found Twin-Primes based on Prime 16217 ****
** 97301 & 97303 **

**** Found Twin-Primes based on Prime 16427 ****
** 98561 & 98563 **

**** Found Twin-Primes based on Prime 17033 ****
** 102197 & 102199 **

**** Found Twin-Primes based on Prime 17467 ****
** 104801 & 104803 **

**** Found Twin-Primes based on Prime 17713 ****
** 106277 & 106279 **

**** Found Twin-Primes based on Prime 17827 ****
** 106961 & 106963 **

**** Found Twin-Primes based on Prime 18077 ****
** 108461 & 108463 **

**** Found Twin-Primes based on Prime 18253 ****
** 109517 & 109519 **

**** Found Twin-Primes based on Prime 18307 ****
** 109841 & 109843 **

**** Found Twin-Primes based on Prime 18413 ****
** 110477 & 110479 **

**** Found Twin-Primes based on Prime 18793 ****
** 112757 & 112759 **

**** Found Twin-Primes based on Prime 19267 ****
** 115601 & 115603 **

**** Found Twin-Primes based on Prime 19423 ****
** 116537 & 116539 **

**** Found Twin-Primes based on Prime 19507 ****
** 117041 & 117043 **

**** Found Twin-Primes based on Prime 19583 ****
** 117497 & 117499 **

**** Found Twin-Primes based on Prime 19603 ****
** 117617 & 117619 **

**** Found Twin-Primes based on Prime 19997 ****
** 119981 & 119983 **

**** Found Twin-Primes based on Prime 20123 ****
** 120737 & 120739 **

**** Found Twin-Primes based on Prime 20177 ****
** 121061 & 121063 **

**** Found Twin-Primes based on Prime 20563 ****
** 123377 & 123379 **

**** Found Twin-Primes based on Prime 20717 ****
** 124301 & 124303 **

**** Found Twin-Primes based on Prime 20983 ****
** 125897 & 125899 **

**** Found Twin-Primes based on Prime 21143 ****
** 126857 & 126859 **

**** Found Twin-Primes based on Prime 22073 ****
** 132437 & 132439 **

**** Found Twin-Primes based on Prime 22447 ****
** 134681 & 134683 **

**** Found Twin-Primes based on Prime 22853 ****
** 137117 & 137119 **

**** Found Twin-Primes based on Prime 23447 ****
** 140681 & 140683 **

**** Found Twin-Primes based on Prime 23473 ****
** 140837 & 140839 **

**** Found Twin-Primes based on Prime 23537 ****
** 141221 & 141223 **

**** Found Twin-Primes based on Prime 23917 ****
** 143501 & 143503 **

**** Found Twin-Primes based on Prime 24337 ****
** 146021 & 146023 **

**** Found Twin-Primes based on Prime 24677 ****
** 148061 & 148063 **

**** Found Twin-Primes based on Prime 25037 ****
** 150221 & 150223 **

**** Found Twin-Primes based on Prime 25147 ****
** 150881 & 150883 **

**** Found Twin-Primes based on Prime 25693 ****
** 154157 & 154159 **

**** Found Twin-Primes based on Prime 25847 ****
** 155081 & 155083 **

**** Found Twin-Primes based on Prime 25867 ****
** 155201 & 155203 **

**** Found Twin-Primes based on Prime 26113 ****
** 156677 & 156679 **

**** Found Twin-Primes based on Prime 26203 ****
** 157217 & 157219 **

**** Found Twin-Primes based on Prime 26357 ****
** 158141 & 158143 **

**** Found Twin-Primes based on Prime 26393 ****
** 158357 & 158359 **

**** Found Twin-Primes based on Prime 26813 ****
** 160877 & 160879 **

**** Found Twin-Primes based on Prime 26927 ****
** 161561 & 161563 **

**** Found Twin-Primes based on Prime 26987 ****
** 161921 & 161923 **

**** Found Twin-Primes based on Prime 27437 ****
** 164621 & 164623 **

**** Found Twin-Primes based on Prime 27617 ****
** 165701 & 165703 **

**** Found Twin-Primes based on Prime 27767 ****
** 166601 & 166603 **

**** Found Twin-Primes based on Prime 28513 ****
** 171077 & 171079 **

**** Found Twin-Primes based on Prime 28627 ****
** 171761 & 171763 **

**** Found Twin-Primes based on Prime 28703 ****
** 172217 & 172219 **

**** Found Twin-Primes based on Prime 28753 ****
** 172517 & 172519 **

**** Found Twin-Primes based on Prime 28837 ****
** 173021 & 173023 **

**** Found Twin-Primes based on Prime 29297 ****
** 175781 & 175783 **

**** Found Twin-Primes based on Prime 29327 ****
** 175961 & 175963 **

**** Found Twin-Primes based on Prime 29803 ****
** 178817 & 178819 **

**** Found Twin-Primes based on Prime 29983 ****
** 179897 & 179899 **

**** Found Twin-Primes based on Prime 30133 ****
** 180797 & 180799 **

**** Found Twin-Primes based on Prime 30293 ****
** 181757 & 181759 **

**** Found Twin-Primes based on Prime 30553 ****
** 183317 & 183319 **

**** Found Twin-Primes based on Prime 30817 ****
** 184901 & 184903 **

**** Found Twin-Primes based on Prime 31063 ****
** 186377 & 186379 **

**** Found Twin-Primes based on Prime 31223 ****
** 187337 & 187339 **

**** Found Twin-Primes based on Prime 31477 ****
** 188861 & 188863 **

**** Found Twin-Primes based on Prime 31573 ****
** 189437 & 189439 **

**** Found Twin-Primes based on Prime 31883 ****
** 191297 & 191299 **

**** Found Twin-Primes based on Prime 32057 ****
** 192341 & 192343 **

**** Found Twin-Primes based on Prime 32077 ****
** 192461 & 192463 **

**** Found Twin-Primes based on Prime 32083 ****
** 192497 & 192499 **

**** Found Twin-Primes based on Prime 32323 ****
** 193937 & 193939 **

**** Found Twin-Primes based on Prime 32713 ****
** 196277 & 196279 **

**** Found Twin-Primes based on Prime 32933 ****
** 197597 & 197599 **

**** Found Twin-Primes based on Prime 32993 ****
** 197957 & 197959 **

**** Found Twin-Primes based on Prime 33037 ****
** 198221 & 198223 **

**** Found Twin-Primes based on Prime 33073 ****
** 198437 & 198439 **

**** Found Twin-Primes based on Prime 33637 ****
** 201821 & 201823 **

**** Found Twin-Primes based on Prime 33773 ****
** 202637 & 202639 **

**** Found Twin-Primes based on Prime 34667 ****
** 208001 & 208003 **

**** Found Twin-Primes based on Prime 35053 ****
** 210317 & 210319 **

**** Found Twin-Primes based on Prime 35747 ****
** 214481 & 214483 **

**** Found Twin-Primes based on Prime 35753 ****
** 214517 & 214519 **

**** Found Twin-Primes based on Prime 36263 ****
** 217577 & 217579 **

**** Found Twin-Primes based on Prime 36923 ****
** 221537 & 221539 **

**** Found Twin-Primes based on Prime 36943 ****
** 221657 & 221659 **

**** Found Twin-Primes based on Prime 37223 ****
** 223337 & 223339 **

**** Found Twin-Primes based on Prime 37307 ****
** 223841 & 223843 **

**** Found Twin-Primes based on Prime 37537 ****
** 225221 & 225223 **

**** Found Twin-Primes based on Prime 37657 ****
** 225941 & 225943 **

**** Found Twin-Primes based on Prime 38273 ****
** 229637 & 229639 **

**** Found Twin-Primes based on Prime 38327 ****
** 229961 & 229963 **

**** Found Twin-Primes based on Prime 38903 ****
** 233417 & 233419 **

**** Found Twin-Primes based on Prime 39163 ****
** 234977 & 234979 **

**** Found Twin-Primes based on Prime 39727 ****
** 238361 & 238363 **

**** Found Twin-Primes based on Prime 40343 ****
** 242057 & 242059 **

**** Found Twin-Primes based on Prime 40693 ****
** 244157 & 244159 **

**** Found Twin-Primes based on Prime 40903 ****
** 245417 & 245419 **

**** Found Twin-Primes based on Prime 40927 ****
** 245561 & 245563 **

**** Found Twin-Primes based on Prime 41333 ****
** 247997 & 247999 **

...

Notes:
* There is a way to test the candidacy of q for Twin-Primes generation directly using q rather than a via Modular-Arithmetic. Mod (q,p') x Mod (a,p') = p'-1 for all primes p' < q
But I am too lazy to implement it. Find an efficient way of determining that a-6 & a+6 are coprime to (q-2)! and you will potentially have a formulaic method for generating twin primes.

That's all I have so far and can't think of a way to proceed any further.

Thank you for your time and all the replies.

Code:

my(p=6); parforprime (q=19^0,5^5,(q-2)!,e,a=(e-1)/q; if(gcd(a-p,a+p-e)==1, c=(a+p)*q-e; d=e-(a-p)*q; print("\n**** Found Twin-Primes based on Prime ",q," ****"); print("** ",c," & ",d," **"); );)

At that lower limit, this cuts off about 33% off of a normal forprime loop and two checks in the if. I assume the output is correct. ( Assumption FAILED)

2018-11-04, 17:42	#1
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 4514₈ Posts	+/- 6 Primality Test Hi all, Is there an efficient way of primality testing p+6 and/or p-6 when it is known that p is prime or otherwise (more generally) all its factors are known? I am assuming that there is not even for any special forms. Thank you for your time. ETA I am only interested in deterministic tests here. Last fiddled with by a1call on 2018-11-04 at 17:52

2018-11-04, 18:24	#3
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 2²·5·7·17 Posts	I don't have a solution for either but for what I am working on +/-6 shortcut would be useful while +/-2 won't be of any use. Any prime +/-2 will have one of them with a factor of 3 and won't be prime (5 not withstanding). Not so with 6. Last fiddled with by a1call on 2018-11-04 at 18:28

2018-11-04, 19:18	#5
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 4514₈ Posts	Interesting algorithm SM. Thank you for introducing me to it. But I suspect that won't be of direct use for record primes. In particular I assume some of the record (Mersenne perhaps) primes are (not highly but still) likely to have neighboring primes that are 6 off. Knowing that they are prime does not seem to have been useful in proving therm prime. I recall the board members here checking to see if the M50 was twin before publication. I assume if it was they would have been restricted to usual primality tests based on +/-1 factoring independent of M50 being prime. Last fiddled with by a1call on 2018-11-04 at 19:19

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Primality Test - CBZ-100-A	a1call	Miscellaneous Math	37	2018-05-19 17:57
Modifying the Lucas Lehmer Primality Test into a fast test of nothing	Trilo	Miscellaneous Math	25	2018-03-11 23:20
there is another way to test the primality of a no	shawn	Miscellaneous Math	5	2007-07-17 17:55
N-1 primality test	Citrix	Math	3	2005-09-19 15:06
A primality test for Fermat numbers faster than Pépin's test ?	T.Rex	Math	0	2004-10-26 21:37

2018-11-04, 18:02	#2
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23731₈ Posts	"Walk before running", some people say. What's wrong with +/-2 Primality Test? Or are you saying that this one is too easy?

2018-11-04, 19:49	#7
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 2²×5×7×17 Posts	Nah, that's not it. If you must know I am working on projecting triples of primes which are 6 off into twins. It's work in progress and I am too lazy to continue right now. If you (or anyone else for that matter) can find any prior research in the area, I would appreciate a reference to save me time.

2018-11-04, 21:57	#9
Dr Sardonicus Feb 2017 Nowhere 2×3²×5×71 Posts	It's gratuitously confusing to use p for a prime -- then say "or otherwise." We have n - a, n, n + a is an "admissible triple" in the sense of the "prime k-tuples conjecture" when x^3 - a^2x is not automatically divisible by some prime. Since the characteristic polynomial of the field of p elements is x^p - x, here we can only have x^3 - a^2x automatically divisible by p = 2 or 3. If a is not divisible by 2, x^3 - a^2x == a^3 - x (mod 2) which is divisible by x^2 - x; hence x^2 - a^2x is always even. Thus, in order for n - a, n, n + a to be admissible, a must be even. If a is not divisible by 3, then a^2 == 1 (mod 3) and x^3 - a^2x == x^3 - x (mod 3), so x^2 - a^2x is divisible by 3. So in order to be admissible, a must be divisible by 3. If a is divisible by 6, then n - a, n, n + a is admissible. According to the prime k-tuples conjecture, the number of n's up to X for which all three of n - a, n, n + a are prime, is, asymptotically, a constant (which depends on a) times X/(ln(X))^3. Now the pair n - a, n + a is also admissible (in fact, this pair is admissible for any positive integer a, but let's stick to a divisible by 6). In this case, the conjecture says that the number of n's up to X for which both n - a and n + a are prime, is asymptotically a constant (which depends on a) times X/(ln(X))^2. So, the number of prime pairs n - a, n + a is likely much greater than the number of prime triples n - a, n, n + a, assuming 6\|a. It's almost certainly greater if gcd(6,a) < 6 :-D I doubt knowing the factorization of n has much bearing on deciding whether n - a and n + a are both prime. What I would look at, is eliminating n's for which either n - a or n + a have any small prime factors.