Interesting Sources of Probable Primes

Multifactorial Pseudoprimes

Joseph McLean

In the preceding article, we considered introducing the multifactorial n!2 in combination with n! and n# in order to produce sequences of numbers with built-in sieves. Now let us focus more directly on multifactorials alone. The standard form n!m±1, when a pseudoprime has been located, succumbs straightforwardly to the familiar Brillhart-Lehmer-Selfridge primality tests, and so has been subject to substantial investigation by many contributors. However, we are not necessarily interested in full primality at this point, and so it behoves us to consider slight deviations from this in our search for interesting pseudoprimes.

First, we remain with the n!2 case. If n is odd, then n!2 is both odd and divisible by n#. The obvious move is to consider the form n!2±2, which is also odd and cannot be divisible by any prime less than or equal to n. In keeping with previous nomenclature, I call these defactos.

1!2+2 = 3 (prime)		1
3!2+2 = 5 (prime)		1
5!2+2 = 17 (prime)	5!2-2 = 13 (prime)	2
7!2+2 = 107 (prime)	7!2-2 = 103 (prime)	3
9!2+2 = 947 (prime)		3
	15!2-2 (prime)	7
	17!2-2 (prime)	8
	19!2-2 (prime)	9
21!2+2 (prime)		11
23!2+2 (prime)		12
27!2+2 (prime)		15
	51!2-2 (prime)	34
57!2+2 (prime)		39
	73!2-2 (prime)	54
75!2+2 (prime)		56
	89!2-2 (prime)	69
103!2+2 (prime)		83
	131!2-2 (prime)	112
	153!2-2 (prime)	136
169!2+2 (prime)		153
219!2+2 (prime)		211
245!2+2 (prime)	245!2-2 (prime)	241
	333!2-2	350
	441!2-2	489
461!2+2		516
	463!2-2	519
695!2+2		839
	825!2-2	1026
1169!2+2		1541
	1771!2-2	2494
	2027!2-2	2914
3597!2+2		5617
3637!2+2		5688
7495!2+2		12896
	9157!2-2	16153
	10875!2-2	19589
	20515!2-2	39779
27743!2+2		55612
28799!2+2		57962
32501!2+2		66266

The pseudoprimes for n = 7495 & 9157 are credited to Ken Davis in 2003. Those for n 10875 & 20515 to me, and the larger values to Roberrt Price, the last in 2015.

Now let’s branch out a bit. Consider n!m where m can be any positive integer (less than n for good measure). Then n, n-m, n-2m, etc. is an arithmetic sequence with difference m, or more precisely -m. Suppose p is a prime, and p is less than or equal to n/m. Then, by the Chinese Remainder Theorem, p will divide at least one member of the sequence. Hence n!m is automatically pre-sieved to n/m. We may then consider deviations d from n!m such that n!m±d is odd and such that no odd prime can divide. If n is even, then n!m is even, and we can only choose d=1, which we have already excluded from consideration here. If n is odd, then n!m is even when m is odd and odd when m is even. Hence we consider the form n!m±2 for n odd and m even. The m=2 case is handled above. Let us now consider m = 4.

Since gcd(4,p) = 1 for all odd primes p, one of the sequence n, n+4, n+8, … ,n+4(p-1) is divisible by p. Hence if n³4p, n!4 is divisible by p and we have a sieve to n/4. In fact, if nºxmod4, where x is 1 or 3, then n!4 is divisible by all primes p<n where pºxmod4, and so the sieve is tighter than n/4. The following is a list of pseudoprimes for n>100.

	125!4-2 (prime)	53
	133!4-2 (prime)	58
143!4+2 (prime)		63
	153!4-2 (prime)	69
	157!4-2 (prime)	71
169!4+2 (prime)		77
185!4+2 (prime)	185!4-2 (prime)	86
	201!4-2 (prime)	96
	217!4-2 (prime)	105
	223!4-2 (prime)	109
235!4+2 (prime)		116
259!4+2 (prime)		130
	289!4-2	148
	323!4-2	169
363!4+2		195
365!4+2		196
457!4+2		256
	469!4-2	264
493!4+2		280
	533!4-2	307
	567!4-2	331
573!4+2		335
777!4+2		479
	821!4-2	511
	1001!4-2	644
1273!4+2		852
1275!4+2		854
1865!4+2		1325
	1999!4-2	1435
	2523!4-2	1874
	2533!4-2	1883
	2827!4-2	2135
	2843!4-2	2148
3621!4+2		2831
4523!4+2		3645
	4821!4-2	3918
5291!4+2		4353
5845!4+2		4872
7185!4+2		6149
	8153!4-2	7089
	8947!4-2	7870
10183!4+2		9100
	12739!4-2	11693
12845!4+2		11802
15057!4+2		14094
16281!4+2		15378
17945!4+2		17139
18771!4+2		18019
	19353!4-2	18642
22479!4+2		22018
	22929!4-2	22508
27235!4+2		27244
28089!4+2		28192
	30629!4−2	31029
31557!4+2		32071
	31809!4−2	32355
	37785!4−2	39139
39163!4+2		40719
45709!4+2		48291
46329!4+2		49014
52211!4+2		55914
	74913!4−2	83161
77779!4+2		86660
	97411!4−2	110913

Values with digits > 10000 and up to n = 18771 were discovered by Ken Davis in 2003. Those between n = 22479 & 37785 are credited to me and the larger values are credited to Robert Price, the latest in 2017. I note that the value for n = 39163 was discovered independently by me in 2015.

Let us now consider m=6. A slight problem now arises, that of divisibility by 3. If nº1mod3, then n!6+2 is divisible by 3, and if nº2mod3, then divisibility alternates between n!6+2 and n!6-2 depending on n. However, the remainder of the sieve to n/6 is intact. Again, I list pseudoprimes for n>100.

	157!6-2 (prime)	48
197!6+2 (prime)		63
213!6+2 (prime)		69
221!6+2 (prime)		72
245!6+2 (prime)		82
	265!6-2 (prime)	89
	267!6-2 (prime)	91
279!6+2 (prime)		95
	327!6-2 (prime)	115
	539!6-2	208
	555!6-2	216
	621!6-2	246
	715!6-2	290
845!6+2		353
	921!6-2	390
927!6+2		393
	979!6-2	419
	1633!6-2	758
	1821!6-2	860
2055!6+2		988
	2259!6-2	1102
	2697!6-2	1349
	2809!6-2	1413
	2863!6-2	1444
2895!6+2		1463
	2935!6-2	1486
3615!6+2		1885
	4213!6-2	2242
	4351!6-2	2326
5613!6+2		3104
	5937!6-2	3307
	6885!6-2	3780
	8743!6-2	5113
	10761!6-2	6455
12753!6+2		7806
	15159!6-2	9468
15737!6+2		9871
	17685!6-2	11243
17813!6+2		11333
18545!6+2		11853
22629!6+2		14789
47859!6+2		33869
48797!6+2		34601
	52075!6−2	37170
	55147!6−2	39591
	68677!6−2	50395
	99655!6−2	75811

All large values up to n = 52075 were discovered by me, the last in 2014. The largest values were discovered by Robert Price in 2017.

Another issue regarding m=6 is that, purely because there are less numbers involved in the product n!6, as n rises, n!6 rises much more slowly that for n!2. This effect applies more and more as m increases so that particularly large values are difficult to come by. Some of these are given later in this article.

Returning to the general case of n!m for n odd and m even, we require our deviation d to ensure that n!m±d is not divisible by any (small) prime up to n/m. We have until now chosen d=2. However, it is obvious that d can take any value of 2^x for x>0 and retain this property. With a little extra thought, we can obtain an even more general formula, as follows. Since n!m is divisible by every prime p up to n/m, any deviation x for which p does not divide x will preserve the sieve effect. If gcd(m,x)=1 then any primes dividing x will divide n!m±x (as long as x is no greater than n/m), and so we require gcd(m,x)>1. On the other hand, if gcd(n,x)>1 then there will be a prime that divides both x and n!m±x, and so we require gcd(n,x)=1. Obviously, we additionally require that the values for n, m and x guarantee that the overall formula is odd. We may therefore consider the following values.

For m=2, x=2^y, n odd

For m=3, x=3^y, n not divisible by 3

For m=4, x=2^y, n odd

For m=5, x=5^y, n not divisible by 5

For m=6, x=2^y, n odd, or x=3^y, n even and not divisible by 3, or x=6^y, n odd and not divisible by 3

For m=3, let us restrict ourselves to x=3. I list probable primes for n>1000.

	1039!3-3	896
	1045!3-3	902
	1190!3-3	1050
	1595!3-3	1474
	1679!3-3	1564
	1772!3-3	1665
	1789!3-3	1683
1952!3+3		1861
2197!3+3		2132
	2410!3-3	2370
2428!3+3		2391
	2920!3-3	2953
2960!3+3		2999
3430!3+3		3548
4618!3+3		4975
	5039!3-3	5492
7478!3+3		8576
	7919!3-3	9147
8209!3+3		9525
8422!3+3		9803
9235!3+3		10873
	10462!3-3	12506
11107!3+3		13373
	11846!3-3	14373
13481!3+3		16609
18194!3+3		23204
19229!3+3		24678
	23293!3−3	30539
	26705!3−3	35541
	30781!3−3	41598
29854!3+3		40213
	43694!3−3	61264
46532!3+3		65667

Larger values with n up to 26705 were discovered by me. Larger values are credited to Robert Price in 2014.

For m=4, let us consider x=4 only. The following lists pseudoprimes for n>1000.

1023!4+4		661
	1057!4-4	686
1107!4+4		724
	1433!4-4	977
	1453!4-4	993
1517!4+4		1044
	1519!4-4	1046
1557!4+4		1076
1625!4+4		1130
	1759!4-4	1238
	3047!4-4	2325
	3561!4-4	2777
	4151!4-4	3307
4215!4+4		3364
5297!4+4		4359
6291!4+4		5294
6499!4+4		5492
	7025!4-4	5995
7357!4+4		6315
11639!4+4		10570
	11917!4-4	10853
	11971!4-4	10908
12963!4+4		11924
13989!4+4		12983
	15295!4-4	14343
15825!4+4		14898
	18919!4-4	18177
	19449!4-4	18745
19993!4+4		19329
20535!4+4		19913
	20765!4-4	20160
35391!4+4		36408

All but the last were found me on or before 2006. The last value was discovered by Robert Price in 2017.

For m=5, let us restrict ourselves to x=5. Again, I list probable primes for n>1000 only.

	1012!5-5	522
1017!5+5		525
1033!5+5		535
1104!5+5		578
1342!5+5		725
1371!5+5		743
	1388!5-5	754
1426!5+5		778
1918!5+5		1095
2146!5+5		1246
	2207!5-5	1287
	2619!5-5	1565
	2714!5-5	1630
3081!5+5		1884
	3229!5-5	1988
	3689!5-5	2314
	3967!5-5	2513
	3992!5-5	2531
4263!5+5		2727
	4588!5-5	2964
4962!5+5		3239
5112!5+5		3350
	5704!5-5	3792
	6133!5-5	4116
	6139!5-5	4120
6269!5+5		4219
	6842!5-5	4656
	8397!5-5	5863
9829!5+5		6997
	10141!5-5	7247
11494!5+5		8339
	11831!5-5	8612
	15948!5-5	12022
16671!5+5		12631
17623!5+5		13438
	18322!5-5	14033
	18721!5-5	14373
	19004!5-5	14615
19672!5+5		15188
20572!5+5		15962
	22177!5-5	17352
24698!5+5		19556
	24888!5-5	19723
	24922!5-5	19752
25227!5+5		20021
	25617!5-5	20364
	32265!5−5	26295
	33317!5−5	27245
	35317!5−5	29060
	36041!5−5	29719
37986!5+5		31496
39176!5+5		32587
39933!5+5		33283

All large values are credited to me.

For m=6, we consider x=6 and then x=3 and x=4 for n>1000.

	1517!6-6	697
	1799!6-6	848
	3355!6-6	1731
12049!6+6		7326
16457!6+6		10376
17143!6+6		10859
17543!6+6		11142
18391!6+6		11743
	24619!6-6	16239
25829!6+6		17127
25945!6+6		17212
31307!6+6		21194
34601!6+6		23675
	40375!6−6	28076
	40793!6−6	28397
41687!6+6		29084
51601!6+6		36797
	53135!6−6	38004

	1360!6-3	614
1426!6+3		649
	1502!6-3	689
	1516!6-3	696
	1568!6-3	724
	1646!6-3	765
1682!6+3		785
1928!6+3		918
3596!6+3		1873
	3628!6-3	1892
	3716!6-3	1944
3796!6+3		1992
	4048!6-3	2143
	7982!6-3	4616
	12776!6-3	7822
15058!6+3		9398
	18070!6-3	11515
	20594!6-3	13318
25654!6+3		16998
	29902!6-3	20144
37330!6+3		25747
	39632!6−3	27506
	52988!6−3	37888
	53864!6−3	38579
	55610!6−3	39957

	1025!6-4	442
1389!6+4		629
1423!6+4		647
1515!6+4		696
1871!6+4		887
2059!6+4		990
2677!6+4		1338
3095!6+4		1579
	4263!6-4	2273
	4365!6-4	2335
4473!6+4		2400
	5175!6-4	2831
	5655!6-4	3130
5691!6+4		3152
5927!6+4		3300
8149!6+4		4724
	9221!6-4	5428
	9327!6-4	5498
	9681!6-4	5733
10789!6+4		6473
12171!6+4		7409
14683!6+4		9137
	19685!6-4	12666
	24777!6-4	16355
26383!6+4		17534
34227!6+4		23392
40945!6+4		28513

All of these are credited to me.

For higher values of m, the growth rates in the sequence n!m get lower and lower and so the amount of checking increases. The fastest rate of growth of course if for m=2, which we have investigated for d=2. Let us broaden this out

To consider d=2^y for all y up to a “reasonable” limit of y=16. For y=4 and y=8 we have the following:

	105!2-4 (prime)	85
	171!2-4 (prime)	156
	243!2-4	239
	271!2-4	273
	295!2-4	302
315!2+4		327
	355!2-4	378
	523!2-4	599
549!2+4		635
	591!2-4	693
	1211!2-4	1606
2059!2+4		2967
	3073!2-4	4694
5543!2+4		9175
6937!2+4		11819
	11157!2-4	20159
	12887!2−4	23688
	19825!4−4	38294
22819!2+4		44774
34523!2+4		70841

103!2+8 (prime)		83
	143!2-8 (prime)	125
299!2+8	299!2-8	307
	307!2-8	317
341!2+8	341!2-8	360
	381!2-8	411
431!2+8		476
445!2+8		495
465!2+8		521
519!2+8		594
	585!2-8	684
	995!2-8	1278
	1019!2-8	1314
	1027!2-8	1326
1251!2+8		1668
	2043!2-8	2940
2469!2+8		3654
2507!2+8		3719
2549!2+8		3790
	4301!2-8	6883
	6275!2-8	10555
6817!2+8		11589
8519!2+8		14894
	11157!2-8	20159
	11621!2-8	21100
	12315!2-8	22515
	17505!2−8	33340
18983!2+8		36489
	24771!2−8	49045
	30535!2−8	61844
	38635!2−8	80222
38715!2+8		80406

Larger values for n up to 12887 for these two tables were discovered by me, and above this by Robert Price.

From now on, I only list numbers that have at least 10000 digits, as the volume of probable primes greatly increases.

For higher values of y, we have:

6123!2+2¹⁵		10267
	6151!2-2⁸	10320
	6275!2-2³	10555
6411!2+2⁸		10814
	6469!2-2¹²	10924
	6599!2-2¹³	11172
6663!2+2¹⁶		11294
6817!2+2³		11589
6895!2+2¹¹		11739
6937!2+2²		11819
	7077!2-2¹⁰	12089
	7093!2-2¹⁰	12119
7297!2+2¹²		12513
	7351!2-2¹⁵	12617
7495!2+2¹		12896
	7743!2-2¹⁴	13377
	7823!2-2¹⁶	13533
7899!2+2¹⁴		13681
	8123!2-2¹⁴	14118
	8179!2-2⁹	14228
8197!2+2¹¹		14263
	8357!2-2¹⁶	14576
	8367!2-2¹¹	14596
8481!2+2¹⁴		14820
8519!2+2³		14894
8655!2+2¹⁰		15162
8835!2+2⁴		15516
	8861!2-2¹⁰	15568
	8977!2-2⁷	15797
	8981!2-2⁸	15805
	9069!2-2⁵	15979
	9157!2-2¹	16153
	9537!2-2¹³	16908
	9789!2-2⁵	17410
10153!2+2¹⁰		18137
10283!2+2⁴		18398
10617!2+2⁶		19069
	10675!2-2¹³	19186
10699!2+2¹⁶		19234
	10875!2-2¹	19589
	11103!2-2¹²	20050
	11157!2-2²	20159
	11157!2-2³	20159
12081!2+2¹³
	12463!2−2⁵	22818
	12479!2−2⁷	22851
	12869!2−2⁷	23651
	13163!2−2¹⁶
14061!2+2⁴		26112
14315!2+2⁷		26639
	15137!2−2⁵	28352
15263!2+2⁹		28616
16491!2+2⁹		31195
18967!2+2⁹		36455
	19661!2−2⁶	37942
21951!2+2⁴		42886
	26313!2−2⁵	52443
	27499!2−2⁵	55070
31191!2+2⁸		63316
32455!2+2⁹		66162
	36095!2−2⁶	74416
	37837!2−2⁶	78394
	37845!2−2⁶	78412
38303!2+2⁸		79461
39505!2+2⁷		82220
39967!2+2¹⁰		83282
41487!2+2⁸		86786
44725!2+2⁷		94289
45369!2+2¹⁰		95787
47599!2+2¹⁰		100991

All values up to n = 13163 were discovered by me with higher values credited to Robert Price. There is some duplication of entries on the Lifchitz page. Also note that this list is not exhaustive.

I now push to even higher values of m, running from m=7 to 12, where we consider all possible values of d£m. For m=7, we only consider d=7.

18509!7+7		10138
	18863!7-7	10354
19286!7+7		10612
	20470!7-7	11340
	22171!7-7	12392
	22376!7-7	12519
	23195!7-7	13029
	25142!7-7	14248
	25216!7-7	14294
	25604!7-7	14539
	26360!7-7	15015
26939!7+7		15382
26940!7+7		15382
	30700!7−7	17777
31039!7+7		17995
	31356!7−7	18198
34534!7+7		20249

For m=8, we can consider d=2, 4 or 8.

	20671!8-2	10031
	21539!8-2	10500
22631!8+8		11093
22753!8+4		11159
23349!8+2		11485
	24487!8-8	12107
	25371!8-4	12593
	25371!8-8	12593
	26787!8-8	13375
	28377!8-2	14257
	29147!8-4	14687
29347!8+2		14798
29477!8+2		14871
	30149!8-8	15247
30181!8+2		15265
	30365!8-8	15368
	31369!8-4	15931
32435!8+4		16531
	32567!8−4	16606
32653!8+4		16654
33325!8+8		17034
33461!8+4		17111
	33625!8−2	17203
34053!8+4		17446
34133!8+2		17491
	34171!8−8	17513
	35597!8−4	18323
	35645!8−2	18350
36687!8+2		18943
	36831!8−2	19026
40985!8+2		21409
43395!8+2		22802
47499!8+2		25192
	56223!8−2	30333
	65299!8−2	35759
	66159!8−2	36277
	68121!8−2	37461
	69339!8−2	38197
	70579!8−2	38948
	73511!8−2	40729
	77745!8−2	43310
	94601!8−2	53708

Those after n = 31369 are credited to Robert Price, the latest in 2017, who has only searched for d=2 range.

For m=9, we consider d=3 and 9.

	23758!9-9	10407
	23897!9-3	10475
24622!9+3		10828
	26528!9-9	11762
	26755!9-9	11873
27265!9+3		12125
	27410!9-9	12196
	28265!9-9	12618
28412!9+9		12691
28526!9+3		12747
29477!9+9		13219
	30601!9-9	13778
	30775!9-9	13865
31540!9+3		14247
32221!9+3		14587
32324!9+3		14639
	32354!9−9	14654
33137!9+9		15047
	34790!9−9	15879
34825!9+9		15897
	34991!9−3	15981
	38530!9−3	17776
38773!9+3		17900
42028!9+9		19566
42952!9+3		20041
43081!9+9		20107
	45833!9−3	21529
	46282!9−9	21761
	48169!9−9	22741
	48362!9−9	22842
48578!9+9		22954

For m=10, we have d=2, 4, 8, or 10 for odd n and d=5 for even n.

25235!10+2		10015
25247!10+2		10021
	25453!10-10	10111
	25575!10-4	10165
	25831!10-10	10278
	25969!10-8	10339
26029!10+10		10365
	26159!10-4	10423
	26164!10-5	10425
	26225!10-8	10452
26329!10+2		10498
26583!10+4		10610
	27033!10-2	10810
27675!10+2		11094
27768!10+5		11136
28043!10+10		11258
28402!10+5		11418
28547!10+10		11482
	28601!10-2	11506
29463!10+10		11891
	30082!10-5	12168
	31245!10-2	12690
	31957!10-2	13010
31968!10+5		13015
32023!10+10		13040
	33215!10-4	13578
	33289!10-2	13611
33391!10+2		13657
34302!10+5		14070
	34961!10−8	14369
	35773!10−2	14739
	35911!10−8	14801
36015!10+4		14849
	36059!10−8	14869
	36279!10−10	14969
36997!10+8		15297
37371!10+10		15468
	37637!10−10	15590
	38539!10−4	16003
38659!10+8		16058
	38761!10−8	16104
38876!10+5		16157
39075!10+2		16249
39897!10+10		16627
40287!10+10		16806
40939!10+10		17106
41195!10+2		17225
	41226!10-5	17239
	42093!10−8	17640
42189!10+4		17684
42562!10+5		17856
	43281!10−8	18189
	43547!10−10	18313
43896!10+5		18475
	45011!10−2	18993
45989!10+10		19449
54312!10+5		23360
58264!10+5		25238
	59378!10−5	25769
	65188!10−5	28554
68218!10+5		30016

For m=11, we just have d=11.

	27832!11-11	10149
28222!11+11		10307
	28326!11-11	10349
	29473!11-11	10814
32922!11+11		12223
	34516!11-11	12880
35333!11+11		13217
	38353!11−11	14471
39411!11+11		14912
	40101!11−11	15201
40104!11+11		15202
43683!11+11		16706
43739!11+11		16729
	44158!11−11	16906
	45607!11−11	17519
	46771!11−11	18013
47537!11+11		18338
	48009!11−11	18539
	48553!11−11	18770
	48603!11−11	18792
	50514!11−11	19607
	51886!11−11	20195
52605!11+11		20503
53371!11+11		20832
53659!11+11		20956
	54082!11−11	21138
	55060!11−11	21559
60223!11+11		23794

For m=12, d can be 2, 4, 6, 8 or 12 when n is odd, and 3 or 9 when n is even.

29769!12+8		10024
29881!12+6		10065
29936!12+3		10086
30839!12+12		10423
30933!12+8		10458
31232!12+9		10570
31313!12+12		10601
	31622!12-3	10717
31699!12+4		10746
32051!12+12		10877
	32335!12-8	10984
	32356!12-9	10992
32587!12+6		11079
33225!12+8		11319
33437!12+8		11399
33775!12+12		11527
	33844!12-9	11553
	35917!12−2	12337
	36447!12−8	12539
	37106!12-9	12789
	37417!12−12	12908
	38271!12−4	13234
	38668!12-9	13385
39573!12+4		13732
	39971!12−4	13884
	40113!12−8	13939
40549!12+6		14106
40912!12+9		14246
41349!12+8		14414
	41723!12−6	14557
41789!12+2		14583
	41903!12−2	14627
42712!12+3		14939
42800!12+3		14973
42982!12+9		15043
43439!12+4		15219
	43689!12−4	15316
43985!12+6		15431
	44176!12-9	15505
48836!12+9		17317
	51440!12−9	18337

The benefits of being able to test more small numbers as m increase is offset by the slowing of the rate of growth. For m=12 and even n above, the effort in reaching 10000 digits is hugely more expensive than for lower m.

Last updated: 10/01/2018