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 2x 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=2y, n odd

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

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

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

For m=6, x=2y, n odd, or x=3y, n even and not divisible by 3, or x=6y, 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=2y 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+215 10267 6151!2-28 10320 6275!2-23 10555 6411!2+28 10814 6469!2-212 10924 6599!2-213 11172 6663!2+216 11294 6817!2+23 11589 6895!2+211 11739 6937!2+22 11819 7077!2-210 12089 7093!2-210 12119 7297!2+212 12513 7351!2-215 12617 7495!2+21 12896 7743!2-214 13377 7823!2-216 13533 7899!2+214 13681 8123!2-214 14118 8179!2-29 14228 8197!2+211 14263 8357!2-216 14576 8367!2-211 14596 8481!2+214 14820 8519!2+23 14894 8655!2+210 15162 8835!2+24 15516 8861!2-210 15568 8977!2-27 15797 8981!2-28 15805 9069!2-25 15979 9157!2-21 16153 9537!2-213 16908 9789!2-25 17410 10153!2+210 18137 10283!2+24 18398 10617!2+26 19069 10675!2-213 19186 10699!2+216 19234 10875!2-21 19589 11103!2-212 20050 11157!2-22 20159 11157!2-23 20159 12081!2+213 12463!2−25 22818 12479!2−27 22851 12869!2−27 23651 13163!2−216 14061!2+24 26112 14315!2+27 26639 15137!2−25 28352 15263!2+29 28616 16491!2+29 31195 18967!2+29 36455 19661!2−26 37942 21951!2+24 42886 26313!2−25 52443 27499!2−25 55070 31191!2+28 63316 32455!2+29 66162 36095!2−26 74416 37837!2−26 78394 37845!2−26 78412 38303!2+28 79461 39505!2+27 82220 39967!2+210 83282 41487!2+28 86786 44725!2+27 94289 45369!2+210 95787 47599!2+210 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