Multifactorial Combinations

Joseph McLean

We have seen elsewhere that combining factorial, defactorial (that is, multifactorial with step 2) and primorials, that we can create sequences of numbers with built-in sieves. Let us take this process a step further, and consider multifactorial combinations in a more general way. I will refer to multifactorials with gap/step/degree/subscript of size n to be of modulus n, for reasons that should become apparent. Note that multifactorials n!m with odd modulus m are always even for all n>m, whereas when m is odd, the parity of n!m is the same as that if n itself.

Odd primes are equivalent to either 1 or 3 mod 4. Hence, if n is an odd number, then n!4 and (n-2)!4 contain between them all primes up to n. We then consider the construction n!4±(n-2)!4±1. This has a built-in sieve, with exceptions arising when a prime p, which is contained explicitly in one of the multifactorials, say n!4, also divides (n-2)!4±1. This occurs comparatively rarely. We also consider even n, where the built-in sieve acts in the same overall fashion, though slightly weaker. Throughout this article, I list only those values that have at least 10000 digits.

 11419!4+11417!4+1 10346 11488!4-11486!4-1 10416 12259!4+12257!4+1 11202 14034!4+14032!4-1 13029 14403!4+14401!4+1 13413 15691!4-15689!4-1 14758 15962!4+15960!4-1 15042 16059!4-16057!4-1 15144 16079!4-16077!4+1 15165 18001!4+17999!4-1 17198 18456!4-18454!4+1 17683 19875!4+19873!4-1 19202 20207!4-20205!4+1 19559 20499!4-20497!4+1 19874 22078!4−22076!4+1 21582 22635!4+22633!4+1 22188 22665!4+22663!4+1 22220 23399!4−23397!4+1 23021 23435!4+23433!4+1 23060 23969!4+23967!4−1 23644 26345!4−26343!4+1 26258 26997!4+26995!4+1 26980 27282!4−27280!4−1 27296 28257!4+28255!4−1 28379 28385!4−28383!4−1 28521

In terms of divisibility properties, there is a lot of symmetry, for instance if a prime p£n-4 divides n!4+(n-2)!4+1 where n is odd, and pºnmod4, then since p must divide n!4 and (n-4)!4, p must also divide (n-2)!4+1, and so p divides n!4-(n-2)!4-1, (n-2)!4+(n-4)!4+! and (n-2)!4-(n-4)!4+1. A similar set occurs if p divides n!4+(n-2)!4-1. Another similar symmetrical divisibility occurs when n is even, but the restriction on p is tighter, so that p£(n-4)/2. In the event that p=n/2, obviously in the even n case only, then the second pair of divisions fail, but the first two remain.

In fact, all the numbers in the above two tables are prime, since the form is easily handled by BLS, but we shall see forms using mod 4 later below for which BLS cannot be applied successfully.

The combinations mod 4 obviously rise in value at a slower rate than the mod 2 defactos, meaning that we have to do a lot more searching to higher values of n to find any probable primes of significant size. It makes sense therefore to consider next the possibility of using mod 3 multifactorials.

Let us first consider divisibility on n!3±1, which for n>3 is always odd. If nº0mod3, this is never divisible by 3, and has a built-in sieve of other primes up to n/3. If nº1mod3 then n!3º1mod3 and so n!3-1 is always divisible by 3. If nº2mod3 then n!3 alternates between 2 and 1 mod 3, so either one of n!3+1 or n!3-1 is divisible by 3, but not both at the same time obviously. Hence over a repetitive cycle of three consecutive integers, giving six numbers for testing, there are 2 of the 6 are divisible by 3.

All primes apart from 3 are equivalent to either 1 or 2 mod 3. Hence if nº2mod3, n!3 and (n-1)!3 involve every prime except 3. Since n!3 is even for all n>3 (even or odd), we consider the construct n!3±(n-1)!3±1. If n is even and nº2mod3, then n!3º-1mod3. Since (n-1)!º1mod3, the combination n!3-(n-1)!3-1 is divisible by 3. If n is odd and nº2mod3, then similarly, the combination n!3+(n-1)!3+1 is divisible by 3. In searching, we let n run through all positive integers. Suppose n is equivalent to either 1 or 0 mod 3. Then out of the four possible combinations, two of them will be divisible by 3. In total, over a repetitive cycle of six integers, giving 24 possible combinations, 5 out of every 12 will therefore be divisible by 3. Although this figure is poorer than for n!3±1, the built-in sieve is tighter, as depending on the circumstances, primes larger than n/3 can divide both multifactorials and so cannot divide the combination. Again I only list those with at least 10000 digits.

 9131!3+9130!3-1 10735 9612!3+9611!3+1 11372 11111!3+11110!3-1 13378 11562!3+11561!3+1 13988 12116!3+12115!3-1 14740 12530!3+12529!3-1 15305 12759!3-12758!3+1 15618 13037!3-13036!3+1 15999

Needless to say, many divisibility properties can be identified here, where if  (n-1)/3<p<n-1, then if p divides one of the possibles, it will also divide certain others, the exact occurrences depending on the different values of p and n mod 3 at any time. A similar set of divisibility properties arises if we replace the n-1 item with n-2, as follows.

 9274!3-(9274-2)!3-1 10924 10736!3+10734!3-1 12874 11338!3+11336!3-1 13685 12799!3+12797!3-1 15672 13775!3-13773!3+1 17014 14881!3-14879!3-1 18546

All of these mod 3 forms succumb to BLS, so that all values are in fact prime. However, if we replace the deviation ±1 by ±3, we obtain values that cannot be handled by BLS and so remain probable primes. I present probable primes in order for n-1 and n-2.

 8662!3-8661!3+3 10118 9719!3+9718!3+3 11514 10096!3-10095!3+3 12016 10299!3+10298!3-3 12288 12886!3+12885!3+3 15791 13244!3-13243!3-3 16283 13354!3+13353!3+3 16434 13413!3+13412!3-3 16515 13737!3+13736!3-3 16962 14053!3+14052!3+3 17398 14523!3-14522!3+3 18049 16044!3-(16044-1)!3-3 17728!3+(17728-1)!3-3 18681!3−(18680)!3−3

&

 8643!3+8641!3+3 10093 8753!3+8751!3+3 10237 9010!3-9008!3-3 10576 10488!3-10486!3-3 12541 10791!3-10789!3+3 12947 10948!3-10946!3-3 13159 11696!3-11694!3-3 14169 11771!3-11769!3+3 14271 12636!3-12634!3-3 15449 14208!3+14206!3-3 17612 16760!3−16758!3−3 21176 16889!3−16887!3+3 21358 17112!3−17110!3−3 21672 17809!3+17807!3+3 22658 18328!3−18326!3−3 23394 21927!3−21925!3+3 28557

The above constructs using tri-factorials lose 5 out of every 12 possibles to divisibility by 3. However, if we consider the more general form n!3±(n-1)!3±(n-2)!3±1, then every prime p>3 is directly involved in one of the multifactorials, and we can cut down the failure rate to 2 out of every 8 possibles. Primes proliferate, and I give only the largest found.

 8348!3+(8348-1)!3+(8348-2)!3+1 9707 8389!3+(8389-1)!3-(8389-2)!3-1 9760 8879!3-(8879-1)!3+(8879-2)!3-1 10403

Divisibility by 3 occurs as follows: If nº0mod3, n!3º0mod3, if nº1mod3, n!3º1mod3 and if nº2mod3, n!3 alternates in sign. One of the 3 multifactorials is always divisible by 3, that is, 0mod3. We require the three non-zero items to align so that they are all negative or all positive. In the above case, this happens as follows:

When n º 0 mod 3 and n is even, then we require the signs to be +,+,+ or -,-,-

When n º 0 mod 3 and n is odd, then we require the signs to be +,-,- or -,+,+

When n º 1 mod 3 and n is even, then we require the signs to be +,-,+ or -,-,+

When n º 1 mod 3 and n is odd, then we require the signs to be +,+,+ or -,+,+

When n º 2 mod 3 and n is even, then we require the signs to be -,+,- or -,-,-

When n º 2 mod 3 and n is odd, then we require the signs to be +,+,+ or +,-,+

We have just considered combinations based on 0, 1 and 2 as being three numbers producing three different modulii mod 3. However, we may just as well consider any other set involving 0, for example 0, 2 and 4, giving the general form n!3±(n-2)!3±(n-4)!3±1, which acts almost identically to the previous one.

 7928!3+(7928-2)!3-(7928-4)!3+1 9159 8035!3+(8035-2)!3-(8035-4)!3-1 9298 8671!3+(8671-2)!3-(8671-4)!3-1 10130

Divisibility by 3 still occurs in 2 out of every 8 possibles, with slightly differing sign patterns. Obviously we could get bogged down considering every possible triple, with diminishing returns. However, I have focussed on the {0, 2, 4} combination for a particular reason, as will be seen soon. Other triples that perform similarly include {0, 1, 5}, {0, 4, 5}, {0, 2, 7}, etc.

The next logical step is to consider mod 5 multifactorials. However, since all primes except 5 are equivalent to 1, 2, 3 or 4 mod 5, the number of combinations gets too high. I am only interested in going to at most three signs (i.e. four items) in any single combination, so mod 5, and for that matter mod 8, multifactorial combinations are not considered in their fullest form, although I will come back to a limited version of the mod 5 case later.

In general, the Chinese Remainder Theorem guarantees that for all primes p for which mp£n and p does not divide m, then p divides n!m, and so any combination involving multifactorials of the same modulus and ±1 or ±2 (to ensure that the overall combination is always odd) is automatically sieved to n/m, except for when p divides m, for example when m is 3, 5, 6, etc, in which case certain combinations will result in divisibility by p.

For completeness, let us return to the mod 2 case. I have already considered the straightforward case n!2±2 for n odd. However, it would be nice to have a symmetric version that can be used when n is even. Since n is 0 or 1 mod 2, n occurs in either n!2 or (n-1)!2. Since if one of these is even, the other must be odd, this leads us to the formula n!2±(n-1)!2±2.

 6403!2-(6403-1)!2-2 10798 7386!2-(7386-1)!2-2 12685 7959!2+(7959-1)!2+2 13798 8381!2-(8381-1)!2-2 14623 9273!2+(9273-1)!2-2 16383 10262!2-10261!2-2 18356 10398!2-10397!2+2 18629 11411!2+11410!2-2 20674 12974!2−12973!2+2 23867 15366!2−15365!2−2 28832 16761!2+16760!2+2 31765 17413!2+17412!2−2 33145 18924!2+18923!2−2 36363 20012!2+20011!2+2 38696 20099!2−20098!2+2 38883

Since we now have a standard form of n!2±(n-1)!2±2 for the mod 2 case, we stretch this for mod 4 and mod 6 respectively, and then stretch the mod 3 standard form n!3±(n-1)!3 to consider our first mod 5 case.

 11753!4-11752!4-2 10686 12855!4-12854!4-2 11813 12961!4-12960!4-2 11921 13881!4-13880!4-2 12871 14213!4+14212!4-2 13215 15840!4+15839!4-2 14914 16426!4+16425!4+2 15530 17292!4+17291!4+2 16445 18347!4-18346!4+2 17567 20704!4-20703!4+2 20095 20787!4-20786!4-2 20184 21176!4+21175!4+2 20605 22363!4+22362!4−2 21892 22535!4−22534!4+2 22079 26249!4+26248!4+2 26152 28373!4−28372!4+2 28508 30309!4−30308!4+2 30670 31145!4−31144!4−2 31608 31236!4+31235!4−2 31710 31326!4−31325!4+2 31811 31334!4+31333!4−2 31820 31551!4−31550!4+2 32064 31968!4−31967!4+2 32534 32157!4−32156!4−2 32746

The n-1 term here can be replaced by n-3 with similar results, as follows.

 11161!4+11158!4-2 10085 11590!4+11587!4-2 10520 11762!4-11759!4+2 10695 11814!4+11811!4-2 10748 12178!4+12175!4+2 11119 12319!4+12316!4-2 11263 12423!4-12420!4+2 11370 12486!4+12483!4+2 11434 12825!4+12822!4-2 11782 12830!4-12827!4+2 11787 13056!4+13053!4-2 12019 13416!4-13413!4-2 12390 14553!4-14550!4+2 13568 15173!4-15170!4-2 14215 16929!4-16926!4-2 16061 17188!4+17185!4+2 16335 17340!4-17337!4+2 16496 17682!4+17679!4+2 16859 17837!4+17834!4+2 17024 19235!4+19232!4+2 18516 20132!4+20129!4-2 19478 21191!4+21188!4+2 20621 21280!4-21277!4+2 20717 21631!4-21628!4-2 21097 21847!4+21844!4-2 21331 22150!4-22147!4-2 21660 22461!4+22458!4−2 21998 23189!4−23186!4−2 22792 23747!4−23744!4−2 23401

As with the single factorial versions, the deviation can basically take any value that divides the modulus, so that we can consider replacing the 2 in the above forms with 4.

 11353!4-11352!4+4 10279 11805!4-11804!4+4 10738 12410!4+12409!4-4 11356 12620!4-12619!4+4 11571 12621!4-12620!4+4 11572 12634!4-12633!4+4 11586 12669!4+12668!4-4 11621 13078!4-13077!4-4 12042 14148!4-14147!4-4 13148 14337!4-14336!4+4 13344 14356!4+14355!4-4 13364 14431!4+14430!4-4 13442 14530!4+14529!4-4 13545 15528!4-15527!4-4 14587 16060!4-16059!4-4 15145 16157!4+16156!4+4 15247 17473!4−17472!4−4 16637 18229!4−18228!4+4 17441 18953!4+18952!4+4 18214 19427!4+19426!4+4 18721 20633!4−20632!4+4 20018 20801!4+20800!4−4 20199 21467!4+21466!4−4 20920 21552!4−21551!4+4 21012

&

 11324!4-11321!4+4 10250 11707!4+11704!4-4 10639 12174!4-12171!4-4 11115 12730!4+12727!4-4 11684 12872!4-12869!4-4 11830 13302!4-13299!4+4 12273 13336!4+13333!4+4 12308 13857!4+13854!4-4 12846 14080!4-14077!4-4 13077 14473!4-14470!4-4 13485 14488!4-14485!4+4 13501 15618!4+15615!4+4 14681 17219!4+17216!4−4 16368 19534!4+19531!4+4 18836 19999!4−19996!4+4 19335 20649!4−20646!4−4 20035 21022!4+21019!4−4 20438 22113!4+22110!4+4 21620 22627!4−22624!4−4 22179

The mod 6 case can be treated similarly.

 16831!6-16830!6-2 10639 17099!6-17098!6+2 10828 18245!6+18244!6-2 11640 18440!6+18439!6+2 11778 18629!6+18628!6+2 11913 19569!6+19568!6-2 12583 19898!6-19897!6-2 12819 21198!6+21197!6+2 13753 21399!6-21398!6-2 13898 21561!6-21560!6+2 14015 22352!6-22351!6+2 14588 23705!6+23704!6+2 15571 24257!6-24256!6-2 15974 25275!6-25274!6-2 16720 25372!6-25371!6-2 16791 26189!6+26188!6+2 17392 28118!6-28117!6-2 18817 29131!6-29130!6-2 19569 31103!6−31102!6−2 21041 34913!6−34912!6−2 23911 34943!6−34942!6+2 23933 35033!6−35032!6−2 24002 38373!6−38372!6+2 26543 39768!6+39767!6−2 27610 40921!6+40920!6−2 28495 41830!6−41829!6−2 29195 42279!6−42278!6−2 29541 43016!6−43015!6−2 30109 44813!6+44812!6−2 31500 46991!6+46990!6+2 33192

Divisibility by 3 here follows the m=3 case, with the single multifactorial form having 1 out of 3 excluded, whereas the twin case has 5 of 12 failing, and there is also more general divisibility due to the combination effect. This means that there are less values than one might think that require a full pseudoprimality test. The n-1 term can be replaced here by n-3 or n-5 to get combinations will almost identical properties, and the deviation d=2 can be replaced by d=3, d=4 or d=6.

Finally, we consider the mod 5 case.

 14504!5+14503!5-1 10815 15458!5-15457!5-1 11611 16383!5-16382!5+1 12389 17777!5+17776!5+1 13569 17952!5-17951!5+1 13717 18070!5-18069!5-1 13818 18499!5-18498!5+1 14184 19357!5+19356!5+1 14918 19536!5-19535!5+1 15071 19966!5+19965!5+1 15440 20352!5-20351!5+1 15773 23560!5-23559!5-1 18558 23629!5+23628!5+1 18618 24367!5-24366!5-1 19265 24971!5+24970!5+1 19795 25066!5+25065!5+1 19879 26603!5+26602!5−1 21235 28502!5−28501!5+1 22922 34026!5+34025!5+1 27887

As expected, certain combinations here are automatically divisible by 5, in this case 11 out of 40 possibles, the remainder sieved to n / 5 at least. This is actually an improvement over the mod 3 case, although again we have the problem of a more slowly rising search limit. For the simplest form n!5±1, out of every 40 possibles there are 20 divisible by 5, so including an extra term has had a significant impact. As elsewhere, the built-in sieve itself has also been tightened (that is, the survival rate has increased) due to the increased likelihood of a prime p<n dividing one or other of the multifactorials. Adding additional terms to the combination will improve the automatic sieve and reduce divisibility by 5, but generates too large a search space. We could also consider replacing the n-1 term with either n-2, n-3 or n-4 to get combinations with similar properties.

In the mod 5 case above, we may yet again apply BLS to prove primality in all cases. However, if we replace the deviation ±1 by ±5, we get a new set of numbers that cannot be proved prime by BLS, as follows.

 14281!5-14280!5-5 10629 15410!5-15409!5-5 11571 15851!5-15850!5+5 11941 15961!5+15960!5-5 12033 16052!5-16051!5+5 12110 16531!5-16530!5-5 12513 16839!5+16838!5-5 12774 16864!5+16863!5-5 12795 17206!5+17205!5-5 13084 17615!5+17614!5-5 13431 18075!5+18074!5-5 13822 19498!5+19497!5+5 15038 19560!5−19559!5−5 15092 19786!5+19785!5+5 15286 20051!5+20050!5−5 15513 25390!5−25389!5−5 20164 26012!5+26011!5−5 20713 26740!5+26739!5+5 21357

It can be seen that there is considerable scope for expanding this search, providing a lucrative source of probable primes.

Last updated: 10/01/2018