Interesting Sources of Probable Primes

Joseph McLean

Primes have always been sought out in many different forms, most often in those forms that are susceptible to a simple primality proof. The most obvious examples of these are Mersenne Primes and Proth primes. However, the Brillhart-Lehmer-Selfridge theorems on primality are suitable for tackling most primes of the form f(n)±1 where f(n) is a recursive function of the positive integer n that has a lot of divisors, for instance the factorial n!, multifactorial n!m, primorial n# and the compositorial n!/n#. Much investigation has gone into finding ever-larger primes of this form.

However, in this article, I am more interested in slight deviations from these, for which no convenient primality proofs are available, and the best we can expect is that they pass sufficient pseudo-primality tests that our confidence in full primality is high. Of course, if the numbers are small enough, then straightforward trial division is enough to decide on primality. For slightly larger numbers, BLS may still pull off a result. For numbers of a new hundred digits, a general primality proving program such as ECPP or PRIMO can be used. In the following, where listed numbers have been proved prime, this is indicated, as is the number of digits to the base 10.

In general, we try to consider sequences with a suitable predisposition, that is, with a form that provides some sort of initial sieve of small primes. The most obvious sources of such forms involve factorials and primorials.

Factoprimorials

Factoprimorials are numbers of the form p=n!±n#±1. In this case, either p+1 or p-1 is divisible by n#, so p is not divisible by any primes up to n, providing a good initial sieve.

 2!+2#+1 = 5 (prime) 2!+2#-1 = 3 (prime) 1 3!+3#+1 = 13 (prime) 3!+3#-1 = 11 (prime) 2 & 1 4!+4#+1 = 31 (prime) 4!+4#-1 = 29 (prime) 4!-4#+1 = 19 (prime) 4!-4#-1 = 17 (prime) 2 5!+5#+1 = 151 (prime) 5!+5#-1 = 149 (prime) 5!-5#-1 = 89 (prime) 3 & 2 6!+6#+1 = 751 (prime) 6!-6#+1 = 691 (prime) 3 7!-7#+1 (prime) 4 8!+8#+1 (prime) 8!+8#-1 (prime) 8!-8#+1 (prime) 5 10!-10#+1 (prime) 7 17!+17#+1 (prime) 17!+17#-1 (prime) 15 18!+18#+1 (prime) 16 20!-20#+1 (prime) 20!-20#-1 (prime) 19 21!-21#+1 (prime) 20 23!+23#-1 (prime) 23 24!+24#+1 (prime) 24 26!+26#-1 (prime) 26!-26#+1 (prime) 27 35!+35#-1 (prime) 41 47!+47#-1 (prime) 60 82!+82#-1 (prime) 123 92!-92#-1 (prime) 143 95!+95#+1 (prime) 149 96!+96#+1 (prime) 150 100!+100#-1 (prime) 158 101!-101#+1 (prime) 160 106!-106#-1 (prime) 171 119!-119#+1 (prime) 197 142!+142#+1 246 147!+147#-1 257 172!-172#+1 312 183!+183#-1 337 266!-266#-1 532 271!+271#-1 544 308!-308#-1 635 343!-343#-1 723 409!-409#+1 893 492!+492#-1 1113 583!-583#-1 1361 597!-597#-1 1400 621!-621#+1 1467 708!+708#-1 1713 903!-903#-1 2279 1021!-1021#-1 2631 1022!+1022#+1 2634 1043!-1043#+1 2698 1116!+1116#-1 2919 1120!+1120#+1 2931 1204!-1204#+1 3189 1239!-1239#-1 3297 1283!-1283#+1 3433 1314!-1314#-1 3530 1538!+1538#-1 4236 1580!+1580#+1 4370 1673!-1673#+1 4669 2003!-2003#+1 5746 2458!-2458#-1 7269 2491!+2491#-1 7381 4207!+4207#-1 13422 4336!-4336#+1 13890 4468!+4468#-1 14371 5773!-5773#+1 19210 6160!-6160#-1 20671 6942!+6942#+1 23656 8147!+8147#-1 28328 9627!-9627#-1 34171 10649!-10649#-1 38265 12913!-12913#+1 47481 13517!-13517#+1 49970 16878!+16878#-1 64022 19255!+19255#+1 74140 19401!+19401#+1 74765

I re-discovered all the values up to n = 10649. The values from n = 5773 to 6942 had previously been identified by Mike Oates in 2003. The values from there up to n = 13517 were identified by Filho, and the last 3 by Filho & Teixeira, all in 2005.

Defactorials

If n is odd, then n!2 is divisible by n#. If n is even, then n!2 is divisible by all primes with exponent up to n/2, which includes all primes up to n/2, that is (n/2)#. We can therefore combine n! and n!2 in a similar manner to factoprimorials to consider n!±n!2±1 or n!±n!2±2 depending as n is even or odd, knowing that these numbers have already been subjected to an initial sieve.

 2!+2!2+1 = 5 (prime) 2!+2!2-1 = 3 (prime) 1 4!+4!2-1 = 31 (prime) 4!-4!2+1 = 17 (prime) 2 6!+6!2+1 = 769 (prime) 6!-6!2+1 = 673 (prime) 3 8!-8!2+1 (prime) 5 14!-14!2+1 (prime) 11 16!+16!2-1 (prime) 14 18!-18!2+1 (prime) 16 28!-28!2+1 (prime) 30 36!+36!2-1 (prime) 42 42!+42!2+1 (prime) 52 46!-46!2-1 (prime) 58 64!-64!2+1 (prime) 90 94!+94!2-1 (prime) 147 108!+108!2-1 (prime) 175 130!-130!2-1 220 324!-324!2+1 675 354!+354!2-1 751 428!+428!2-1 943 604!+604!2+1 1420 778!-778!2+1 1914 882!-882!2+1 2217 1976!+1976!2+1 5657 5126!+5126!2+1 16793 6374!-6374!2-1 21484 8068!-8068!2-1 28019 9878!+9878!2-1 35172

Even-numbered defactorials have a simple divisibility property. Suppose that a prime p divides n!+n!2+1 and (n/2<)p<n. Then p divides n! but not n!2 and so p must divide n!2+1. Subtracting 2x(n!2+1) implies that p divides n!-n!2-1. Similarly, if p divides n!+n!2-1 and p<n then p divides n!2-1 and so also divides n!-n!2+1. Note that n/2<p is guaranteed by the initial sieve condition. In fact, the numbers in the above table are all primes, since the form succumbs easily to BLS.

 3!+3!2+2 = 11 (prime) 3!+3!2-2 = 7 (prime) 3!-3!2+2 = 5 (prime) 2 & 1 5!+5!2+2 = 137 (prime) 5!-5!2+2 = 107 (prime) 5!-5!2-2 = 103 (prime) 3 7!+7!2+2 = (prime) 7!-7!2+2 (prime) 7!-7!2-2 (prime) 4 11!+11!2+2 (prime) 8 25!+25!2-2 (prime) 26 51!-51!2+2 (prime) 67 75!-75!2-2 (prime) 110 87!-87!2+2 (prime) 133 95!+95!2-2 (prime) 149 99!-99!2-2 (prime) 156 143!+143!2-2 248 175!+175!2-2 319 571!-571!2-2 1328 583!-583!2+2 1361 919!+919!2-2 2327 937!+937!2+2 2380 1041!+1041!2+2 2691 1201!-1201!2-2 3179 1349!+1349!2+2 3639 1667!-1667!2+2 4650 1687!+1687!2+2 4714 1863!-1863!2+2 5286 1941!+1941!2+2 5542 5359!-5359!2-2 17660 5585!-5585!2-2 18504 5697!+5697!2-2 18925 5963!+5963!2+2 19926 6759!-6759!2-2 22954 6817!-6817!2-2 23176 8775!-8775!2+2 30794 8809!+8809!2+2 30928 11487!−11487!2+2 41654

Defactoprimorials

We may also consider combining n!2 and n# with the same initial sieve in operation. Again, since n!2 is odd or even depending on n, and n# is always even, we consider n!2±n#±1 when n is even and n!2±n#±2 if n is odd.

 2!2+2#+1 = 5 (prime) 2!2+2#-1 = 3 (prime) 1 4!2+4#-1 = 13 (prime) 4!2-4#+1 = 3 (prime) 2 & 1 6!2+6#+1 = 79 (prime) 6!2-6#+1 = 19 (prime) 6!2-6#-1 = 17 (prime) 2 8!2+8#-1 (prime) 8!2-8#-1 (prime) 3 10!2+10#+1 (prime) 10!2+10#-1 (prime) 10!2-10#+1 (prime) 3 14!2+14#+1 (prime) 6 16!2+16#+1 (prime) 16!2-16#+1 (prime) 8 18!2+18#-1 (prime) 18!2-18#+1 (prime) 9 22!2+22#-1 (prime) 11 26!2+26#+1 (prime) 26!2-26#+1 (prime) 14 28!2+28#-1 (prime) 16 30!2-30#-1 (prime) 17 36!2+36#-1 (prime) 36!2-36#-1 (prime) 22 38!2+38#-1 (prime) 23 42!2+42#+1 (prime) 27 48!2+48#-1 (prime) 32 82!2+82#+1 (prime) 62 104!2+104#-1 (prime) 84 110!2-110#-1 (prime) 90 114!2+114#-1 (prime) 94 126!2+126#+1 (prime) 107 146!2-146#+1 (prime) 128 174!2+174#-1 (prime) 159 184!2+184#-1 (prime) 170 304!2+304#+1 313 450!2-450#-1 501 586!2-586#-1 686 588!2+588#-1 689 652!2+652#-1 778 718!2-718#+1 872 810!2-810#+1 1004 902!2+902#-1 1139 2428!2+2428#+1 3585 2658!2+2658#-1 3977 2742!2-2742#+1 4121 3520!2-3520#+1 5480 3764!2-3764#+1 5915 4694!2-4694#-1 7600 4848!2-4848#-1 7884 4940!2-4940#+1 8053 6006!2-6006#+1 10046 6178!2-6178#+1 10371 6582!2-6582#-1 11140 8064!2-8064#-1 14003 8152!2+8152#+1 14175 8538!2-8538#+1 14932 8918!2+8918#-1 15680 10476!2-10476#+1 18786 10962!2+10962#+1 19765

Note that even defactoprimorials have an analogous divisibility property to even defactorials. Suppose a prime p divides n!2+n#+1 where (n/2<)p<n. Then since p divides n# by definition, we can subtract 2xn#, so we have that p divides n!2-n#+1. Similarly if p divides n!2+n#-1 and p<n then p divides n!2-n#-1.

 3!2+3#+2 = 11 (prime) 3!2+3#-2 = 7 (prime) 2 & 1 5!2+5#+2 = 47 (prime) 5!2+5#-2 = 43 (prime) 2 7!2+7#+2 (prime) 7!2+7#-2 (prime) 3 9!2+9#-2 (prime) 9!2-9#-2 (prime) 3 & 2 11!2+11#-2 (prime) 11!2-11#+2 (prime) 5 & 4 13!2-13#+2 (prime) 6 15!2+15#-2 (prime) 7 17!2-17#+2 (prime) 8 19!2+19#+2 (prime) 19!2+19#-2 (prime) 19!2-19#-2 (prime) 9 21!2+21#-2 (prime) 21!2-21#+2 (prime) 21!2-21#-2 (prime) 11 23!2-23#-2 (prime) 12 35!2+35#-2 (prime) 21 41!2-41#-2 (prime) 26 45!2-45#+2 (prime) 29 51!2-51#-2 (prime) 34 55!2+55#+2 (prime) 37 61!2+61#+2 (prime) 43 93!2+93#-2 (prime) 73 101!2-101#-2 (prime) 81 111!2+111#-2 (prime) 91 117!2+117#-2 (prime) 97 125!2+125#+2 (prime) 106 133!2+133#+2 (prime) 114 153!2-153#-2 (prime) 136 185!2+185#+2 (prime) 171 205!2-205#+2 194 211!2-211#+2 201 229!2-229#+2 222 245!2-245#-2 241 247!2-247#-2 244 303!2+303#+2 312 403!2-403#+2 439 443!2-443#+2 492 613!2+613#+2 723 721!2-721#-2 876 859!2-859#+2 1076 1011!2-1011#+2 1302 1035!2+1035#+2 1338 1083!2+1083#+2 1410 1099!2-1099#-2 1435 1223!2-1223#-2 1625 1281!2-1281#+2 1714 1319!2-1319#+2 1774 2437!2-2437#+2 3600 3439!2-3439#-2 5337 3635!2+3635#-2 5684 3717!2+3717#+2 5831 3825!2+3825#-2 6024 4121!2-4121#+2 6556 4417!2+4417#-2 7094 4433!2-4433#-2 7123 4475!2+4475#-2 7199 4617!2+4617#-2 7459 5335!2+5335#+2 8786 5647!2-5647#-2 9370 6695!2+6695#+2 11355 7965!2+7965#-2 13809 8815!2-8815#+2 15477 9287!2+9287#+2 16411 11841!2-11841#+2 21548 12871!2+12871#-2 23655 15337!2-15337#+2 28771 15423!2+15423#+2 28951 17201!2+17201#+2 32695 18779!2−18779+2 36053 18841!2+18841#+2 36185 19455!2−19455#−2 37500

Compoundorials

The above concepts can be taken to the logical conclusion to combine n!, n!2 and n# all at once. The even/odd split is still in evidence in terms of the deviation value (that is ±2 or ±1), the initial sieve (up to n or n/2), and the obvious divisibility properties for even n. For each of the even or odd forms, there are 8 possibilities, and a proliferation of primes for small n. For n>1000, we have the following probable primes.

 1030!-1030!2-1030#-1 2661 1085!+1085!2+1085#-2 2825 1206!-1206!2+1206#+1 3195 1369!-1369!2+1369#+2 3702 1497!+1497!2-1497#+2 4106 1533!+1533!2-1533#-2 4220 1606!-1606!2+1606#+1 4453 1779!-1779!2+1779#+2 5012 1841!+1841!2-1841#+2 5214 1845!-1845!2-1845#-2 5227 1853!+1853!2+1853#+2 5253 1863!+1863!2+1863#-2 5286 1956!-1956!2-1956#-1 5591 2523!-2523!2+2523#+2 7490 2881!-2881!2-2881#+2 8718 2896!-2896!2-2896#-1 8770 3049!+3049!2+3049#-2 9302 3108!-3108!2-3108#-1 9507 3291!+3291!2+3291#-2 10149 3301!+3301!2-3301#-2 10184 3471!+3471!2-3471#+2 10784 3539!-3539!2+3539#-2 11025 3647!+3647!2-3647#+2 11409 3750!+3750!2+3750#+1 11777 4143!-4143!2-4143#+2 13190 4286!-4286!2+4286#+1 13708 4387!+4387!2+4387#+2 14076 4424!+4424!2+4424#-1 14210 4460!-4460!2-4460#+1 14342 4533!+4533!2-4533#+2 14608 4973!-4973!2+4973#+2 16226 5190!-5190!2-5190#-1 17030 5217!-5217!2-5217#+2 17131 5597!-5597!2+5597#+2 18549 5938!-5938!2-5938#+1 19832 6159!+6159!2-6159#-2 20668 6705!-6705!2+6705#+2 22747 9278!+9278!2-9278#-1 32784 12763!+12763!2+12763#+2 46864 13201!+13201!2+13201#-2 48666

Factonentials

In the factoprimorial and defactorial cases, the second term is a large divisor of the first term. Another example of this can be found using powers of small primes. We shall restrict ourselves to the forms n!±2n±1 and n!2±2n±1. These have very high levels of divisibility, so that very few values have to be tested fully.

 2!+22+1 = 7 (prime) 2!+22-1 = 5 (prime) 1 3!+23-1 = 13 (prime) 2 4!+24+1 = 41 (prime) 4!-24-1 = 7 (prime) 2 & 1 5!+25-1 = 153 (prime) 5!-25+1 = 89 (prime) 3 & 2 7!+27-1 = 5167 (prime) 4 8!+28+1 (prime) 8!-28-1 (prime) 5 11!+211-1 (prime) 8 23!-223+1 (prime) 23 25!-225+1 (prime) 26 72!+272+1 (prime) 104 144!-2144-1 (prime) 250 167!+2167-1 301 208!-2208-1 394 2609!+22609-1 7783 4880!-24880-1 15883 6217!-26217+1 20887 6247!+26247-1 21001 7841!+27841-1 27133 13537!-213537+1 50052

Defactonentials

Similar to factonentials, we can replace the factorial with a defactorial.

 2!2+22+1 = 7 (prime) 2!2+22-1 = 5 (prime) 1 4!2+24-1 = 23 (prime) 2 6!2+26+1 = 113 (prime) 3 8!2+28+1 = 641 (prime) 8!2-28-1 = 127 (prime) 3 12!2+212+1 (prime) 12!2 -212-1 (prime) 5 20!2+220+1 (prime) 10 28!2-228-1 (prime) 16 56!2+256+1 (prime) 38 2704!2-22704-1 4055 14656!2+214656-1 27349 33408!−233408−1 68315

&

 49!2−249−2 32 193!2−2193−2 180

These are remarkably rare.

Trefactorials

More recently, I have extended the concept to investigating numbers of the form n!±n!3±1 & n!±n!3±3.

 33!+33!3+1 37 54!−54!3+1 72 94!+94!3+1 147 221!−221!3−1 424 236!+236!3−1 460 242!−242!3+1 474 274!+274!3+1 551 282!−282!3−1 571 360!+360!3+1 766 369!+369!3+1 789 376!−376!3−1 807 432!−432!3−1 953 453!−453!3+1 1009 528!+528!3−1 1211 1252!+1252!3+1 3337 1318!+1318!3+1 3542 1354!−1354!3−1 3655 2237!−2237!3−1 6524 2579!−2579!3−1 7681 2861!−2861!3−1 8649 3685!+3685!3+1 11545 4000!−4000!3−1 12674 5388!+5388!3−1 17768 5571!+5571!3−1 18452 6511!−6511!3−1 22006 7134!−7134!3+1 24394

&

 13!−13!3+3 10 16!−16!3+3 14 17!−17!3+3 15 23!+23!3+3 23 25!+25!3−3 25!−25!3−3 26 26!+26!3−3 26!−26!3+3 27 28!−28!3−3 30 29!+29!3−3 31 32!+32!3+3 32!−32!3−3 36 41!41!3−3 50 52!+52!3−3 68 71!−71!3+3 102 82!+82!3+3 123 86!+86!3+3 131 91!+91!3+3 141 124!+124!3+3 208 140!+140!3+3 242 148!−148!3+3 259 176!+176!3+3 321 184!+184!3−3 339 226!−226!3−3 436 337!+337!3−3 708 406!−406!3−3 885 433!−433!3+1 956 443!+443!3+3 982 547!−547!3−3 1262 553!−553!3−3 1279 559!+559!3+3 1295 605!+605!3+3 1423 713!−713!3+3 1727 1931!+1931!3+3 5509 2867!−2867!3+3 8670 3326!−3326!3−3 10272 4228!−4228!3−3 13498 5386!−5386!3+3 17760 6605!+6605!3+3 22365 7876!−7876!3+3 27270 8210!−8210!3+3 28574

TDFs (Tredefactorials)

Combining single, double and triple factorials, we obtain numbers of the form n!±n!2±n!3±1

 14!+14!2+14!3−1 11 24!+24!2+24!3−1 24!+24!2-24!3+1 24 26!−26!2−26!3+1 27 40!+40!2+40!3+1 48 58!−58!2+58!3+1 79 60!+60!2−60!3+1 82 108!−108!2+108!3-1 175 144!−144!2−144!3+1 250 148!+148!2+148!3+1 259 330!−330!2+330!3+1 690 384!−384!2−384!3−1 828 984!−984!2−984!3+1 2520 1002!−1002!2+1002!3+1 2574 1328!−1328!2+1328!3−1 3573 2536!−2536!2−2536!3−1 7534 2540!−2540!2−2540!3+1 7548 2752!+2752!2+2752!3+1 8273 3612!−3612!2+3612!3+1 11285 4184!+4184!2+4184!3−1 13338 6212!+6212!2−6212!3+1 20869 9528!+9528!2−9528!3+1 33777

To finish, I return to a couple of simpler forms that have had only cursory investigation until now.

2n±n

This is a conveniently tight form that does not succumb to BLS. Obviously, we require n to be odd.

 21+1 = 3 (prime) 23+3 = 11 (prime) 23-3 = 5 (prime) 25+5 = 37 (prime) 29+9 = 521 (prime) 29-9 = 503 (prime) 213-13 (prime) 215+15 (prime) 219-19 (prime) 221-21 (prime) 239+39 (prime) 255-55 (prime) 275+75 (prime) 281+81 (prime) 289+89 (prime) 2261-261 (prime) 2317+317 (prime) 2701+701 (prime) 2735+735 (prime) 21311+1311 21881+1881 23201+3201 23225+3225 23415-3415 24185-4185 27353-7353 211795+11795 212213-12213 244169- 44169 260975-60975 261011-61011 288071+88071 2108049-108049 2182451-182451 2204129+204129 2228271-228271 2481801-481801 2500899-500899 2505431-505431 2678561+678561 21015321−1015321 21061095−1061095

I re-discovered the values up to n = 108049, and the remaining large values were all identified by Henri Lifchitz, the last one in 2013.

2n±n2

This is an obvious extension of the previous form, which provides a better symmetry. Similarly, we require n to be odd. In the “+” case, n can be restricted further, since 2n+n2 is divisible by 3 unless n is divisible by 3, and so we have nº3mod6.

 21+12 23+32 25-52 = 7 (prime) 27-72 = 79 (prime) 29+92 = 561 (prime) 29-92 = 463 (prime) 215+152 (prime) 217-172 (prime) 219-192 (prime) 221+212 (prime) 233+332 (prime) 251-512 (prime) 253-532 (prime) 281-812 (prime) 283-832 (prime) 2119-1192 (prime) 2189-1892 (prime) 2219-2192 (prime) 2227-2272 (prime) 2301-3012 (prime) 2455-4552 (prime) 2461-4612 (prime) 2623-6232 (prime) 22007+20072 22037-20372 22127+21272 22221-22212 22455-24552 23547-35472 23759+37592