Multifactorial
Combinations
We
have seen elsewhere that combining factorial, defactorial (that is,
multifactorial with step 2) and primorials, that we can create sequences of
numbers with builtin 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 (n2)!4
contain between them all primes up to n. We then consider the construction n!4±(n2)!4±1.
This has a builtin sieve, with exceptions arising when a prime p, which is
contained explicitly in one of the multifactorials, say n!4, also divides (n2)!4±1.
This occurs comparatively rarely. We also consider even n, where the builtin
sieve acts in the same overall fashion, though slightly weaker. Throughout this
article, I list only those values that have at least 10000 digits.
Even n:



11488!411486!41 
10416 

14034!4+14032!41 


13029 

15962!4+15960!41 


15042 


18456!418454!4+1 

17683 
Odd n:
11419!4+11417!4+1 



10346 
12259!4+12257!4+1 



11202 
14403!4+14401!4+1 



13413 



15691!415689!41 
14758 



16059!416057!41 
15144 


16079!416077!4+1 

15165 

18001!4+17999!41 


17198 

19875!4+19873!41 


19202 


20207!4(20205)!4+1 

19559 


20499!4(20497)!4+1 

19874 
In
terms of divisibility properties, there is a lot of symmetry, for instance if a
prime p£n4
divides n!4+(n2)!4+1
where n is odd, and pºnmod4,
then since p must divide n!4 and (n4)!4,
p must also divide (n2)!4+1,
and so p divides n!4(n2)!41,
(n2)!4+(n4)!4+!
and (n2)!4(n4)!4+1.
A similar set occurs if p divides n!4+(n2)!41.
Another similar symmetrical divisibility occurs when n is even, but the
restriction on p is tighter, so that p£(n4)/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 builtin sieve of other primes up to
n/3. If nº1mod3
then n!3º1mod3
and so n!31
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!31
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 (n1)!3
involve every prime except 3. Since n!3 is even for all n>3 (even or odd),
we consider the construct n!3±(n1)!3±1.
If n is even and nº2mod3,
then n!3º1mod3.
Since (n1)!º1mod3,
the combination n!3(n1)!31
is divisible by 3. If n is odd and nº2mod3,
then similarly, the combination n!3+(n1)!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 builtin 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+(91311)!31 


10735 
9612!3+(96121)!3+1 



11372 

11111!3+11110!31 


13378 
11562!3+11561!3+1 



13988 

12116!3+12115!31 


14740 

12530!3+12529!31 


15305 


12759!312758!3+1 

15618 


13037!313036!3+1 

15999 
Needless
to say, many divisibility properties can be identified here, where if (n1)/3<p<n1,
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 n1
item with n2,
as follows.



9274!3(92742)!31 
10924 

10736!3+10734!31 


12874 

11338!3+11336!31 


13685 

12799!3+12797!31 


15672 


13775!313773!3+1 

17014 



14881!314879!31 
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 n1
and n2.


8662!3(86621)!3+3 

10118 
9719!3+(97191)!3+3 



11514 


10096!310095!3+3 

12016 

10299!3+10298!33 


12288 
12886!3+12885!3+3 



15791 



13244!313243!33 
16283 
13354!3+13353!3+3 



16434 

13413!3+13412!33 


16515 

13737!3+13736!33 


16962 
14053!3+14052!3+3 



17398 


14523!314522!3+3 

18049 
&
8643!3+(86432)!3+3 



10093 
8753!3+(87532)!3+3 



10237 



9010!3(90102)!33 
10576 



10488!310486!33 
12541 


10791!310789!3+3 

12947 



10948!310946!33 
13159 



11696!311694!33 
14169 


11771!311769!3+3 

14271 



12636!312634!33 
15449 

14208!3+14206!33 


17612 
The
above constructs using trifactorials lose 5 out of every 12 possibles to
divisibility by 3. However, if we consider the more general form n!3±(n1)!3±(n2)!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+(83481)!3+(83482)!3+1 
9707 
8389!3+(83891)!3(83892)!31 
9760 
8879!3(88791)!3+(88792)!31 
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, zero mod 3. We require the three nonzero 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±(n2)!3±(n4)!3±1,
which acts almost identically to the previous one.
7928!3+(79282)!3(79284)!3+1 
9159 
8035!3+(80352)!3(80354)!31 
9298 
8671!3+(86712)!3(86714)!31 
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 (n1)!2.
Since if one of these is even, the other must be odd, this leads us to the
formula n!2±(n1)!2±2.



6403!2(64031)!22 
10798 



7386!2(73861)!22 
12685 
7959!2+(79591)!2+2 



13798 



8381!2(83811)!22 
14623 

9273!2+(92731)!22 


16383 



10262!210261!22 
18356 


10398!210397!2+2 

18629 

11411!2+11410!22 


20674 
Since
we now have a standard form of n!2±(n1)!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±(n1)!3
to consider our first mod 5 case.



11753!411752!42 
10686 



12855!412854!42 
11813 



12961!412960!42 
11921 



13881!413880!42 
12871 

14213!4+14212!42 


13215 

15840!4+15839!42 


14914 
16426!4+16425!4+2 



15530 
17292!4+17291!4+2 



16445 


18347!418346!4+2 

17567 


20704!420703!4+2 

20095 



20787!420786!42 
20184 
The n1
term here can be replaced by n3
with similar results, as follows.

11161!4+11158!42 


10085 

11590!4+11587!42 


10520 


11762!411759!4+2 

10695 

11814!4+11811!42 


10748 
12178!4+12175!4+2 



11119 

12319!4+12316!42 


11263 


12423!412420!4+2 

11370 
12486!4+12483!4+2 



11434 

12825!4+12822!42 


11782 


12830!412827!4+2 

11787 

13056!4+13053!42 


12019 



13416!413413!42 
12390 


14553!414550!4+2 

13568 



15173!415170!42 
14215 



16929!416926!42 
16061 
17188!4+17185!4+2 



16335 


17340!417337!4+2 

16496 
17682!4+17679!4+2 



16859 
17837!4+17834!4+2 



17024 
19235!4+19232!4+2 



18516 

20132!4+20129!42 


19478 
21191!4+21188!4+2 



20621 


21280!421277!4+2 

20717 



21631!421628!42 
21097 

21847!4+21844!42 


21331 



22150!422147!42 
21660 
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!411352!4+4 

10279 


11805!411804!4+4 

10738 

12410!4+12409!44 


11356 


12620!412619!4+4 

11571 


12621!412620!4+4 

11572 


12634!412633!4+4 

11586 

12669!4+12668!44 


11621 



13078!413077!44 
12042 



14148!414147!44 
13148 


14337!414336!4+4 

13344 

14356!4+14355!44 


13364 

14431!4+14430!44 


13442 

14530!4+14529!44 


13545 



15528!415527!44 
14587 



16060!416059!44 
15145 
16157!4+16156!4+4 



15247 
&


11324!411321!4+4 

10250 

11707!4+11704!44 


10639 



12174!412171!44 
11115 

12730!4+12727!44 


11684 



12872!412869!44 
11830 


13302!413299!4+4 

12273 
13336!4+13333!4+4 



12308 

13857!4+13854!44 


12846 



14080!414077!44 
13077 



14473!414470!44 
13485 


14488!414485!4+4 

13501 
15618!4+15615!4+4 



14681 
The mod 6 case can be treated similarly.



16831!616830!62 
10639 


17099!617098!6+2 

10828 

18245!6+18244!62 


11640 
18440!6+18439!6+2 



11778 
18629!6+18628!6+2 



11913 

19569!6+19568!62 


12583 



19898!619897!62 
12819 
21198!6+21197!6+2 



13753 



21399!621398!62 
13898 


21561!621560!6+2 

14015 


22352!622351!6+2 

14588 
23705!6+23704!6+2 



15571 



24257!624256!62 
15974 



25275!625274!62 
16720 



25372!625371!62 
16791 
26189!6+26188!6+2 



17392 



28118!628117!62 
18817 



29131!629130!62 
19569 
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 n1
term can be replaced here by n3
or n5
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!51 


10815 



15458!515457!51 
11611 


16383!516382!5+1 

12389 
17777!5+17776!5+1 



13569 


17952!517951!5+1 

13717 



18070!518069!51 
13818 


18499!518498!5+1 

14184 
19357!5+19356!5+1 



14918 


19536!519535!5+1 

15071 
19966!5+19965!5+1 



15440 


20352!520351!5+1 

15773 



23560!523559!51 
18558 
23629!5+23628!5+1 



18618 



24367!524366!51 
19265 
24971!5+24970!5+1 



19795 
25066!5+25065!5+1 



19879 
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 builtin 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 n1
term with either n2,
n3
or n4
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!514280!55 
10629 



15410!515409!55 
11571 


15851!515850!5+5 

11941 

15961!5+15960!55 


12033 


16052!516051!5+5 

12110 



16531!516530!55 
12513 

16839!5+16838!55 


12774 

16864!5+16863!55 


12795 

17206!5+17205!55 


13084 

17615!5+17614!55 


13431 

18075!5+18074!55 


13822 
It can be seen that there is considerable
scope for expanding this search, providing a lucrative source of probable
primes.
Last updated: 19/11/2010