Interesting Sources of Probable Primes

 

 

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!21 or n!n!22 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

 

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!2n#1 when n is even and n!2n#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

 

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

 

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!2n1 and n!22n1. 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

 

and

 

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

 

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

 

2nn

 

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

 

 

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

 

2nn2

 

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

 

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

 

 

25515-55152

 

26825-68252

 

28303-83032

 

29029-90292

 

212103-121032

229355+293552

 

234653+346532

 

 

249989-499892

 

255525-555252

257285+572852

 

 

264773-647732

 

280307-803072

299069+990692

 

 

2119087-1190872

 

Note that numbers of the form 2nnm for higher exponents m>2 were considered for this survey and then rejected as being of less interest (that is, less productive of pseudoprimes).