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