Complex MultiFactorials

Multifactorials of the form n!m±1 have been heavily mined for primes, as is totally justified by their tractability, by which we mean susceptibility to BLS. The form n!m is just a shorthand for denoting the multiple n.(n-m).(n-2m)…(n-km), where k is such that n-km > 0 but n-(k+1)m ³ 0, that is, the product of a descending sequence of positive integers starting at n and separated by a constant value m.  It occurred to me to consider sequences where the separator between consecutive terms was not a constant, for example alternating or monotonically increasing.

The most simple deviation would be to consider alternating the separator between 1 and 2, obtaining the product n.(n-1).(n-3).(n-4).(n-6).(n-8)…, etc. In effect, this can be represented in a closed form as n!3.(n-1)!3, and in general a repeating set of separators can readily be expressed in closed form as a product of multifactorials, as follows.

Let {a1, a2, … , am} represent a repeating set of separators between consecutive terms of a descending sequence of positive integers starting at n. Let bi be the intermediate sums of this sequence, i.e. b0 = 0, b1 = a1, bi = bi-1 + ai, and let p = bm (that is, p is the sum of all the ai). Then the product of the sequence can alternatively be written in closed form as

The product Π from i =0 to m-1 of the multifactorials (n-bi)!p.

For example, if the sequence is {2, 1}, then b0 = 0,  b1 = 2, p = 3 and so n.(n-2).(n-3).(n-5)… = n!3.(n-2)!3

Also, for a1 = 1, a2 = 2, a3 = 3, we have b0 = 0, b1 = 1, b2 = 3, b3 = m = 6, so the product can be represented by n!6.(n-1)!6.(n-3)!6.

It is then perfectly reasonable to consider adding or subtracting 1 in order to search for primes, while retaining tractability.

So far, this is a variation on a familiar scene. However, let us now consider increasing sequences. Obviously the simplest sequence is to consider ai = i, which can also be represented by n.(n-1).(n-3).(n-6).(n-10)…, etc. We note the occurrence of triangular numbers in this formula as the intermediate sums bi. This is a side-effect of our definition, and it is obvious that alternative sequences may be derived based on this idea (one such is mentioned below). Be that as it may, the separator sequence defined by ai = i leads to a sequence of complex multifactorial numbers that rises very much more slowly than normal multifactorials because of the scarcity of individual elements. For instance, at n = 1000 the decimal expansion of the product has only 123 digits, and for n = 10000 has 528 digits. Since the product has a substantial degree of built-in divisibility, this is a reasonable source of primes and possibly prime pairs.

For n up to 10000, prime pairs occur for n = 3, 22, 31, 93, 162, 327 & 2272.

Divisibility properties of these numbers are complex. The only obvious pattern is for divisibility by 3. These numbers also provide a nice sequence for factoring.

I then considered ai = Fi, the Fibonacci numbers, and denote the complex multifactorial so generated as n!F. Then n!F = n.(n-1).(n-2).(n-4).(n-7)…, etc. Since the Fibonacci numbers rise much faster than sequentially, the product has fewer elements. This produces a much more slowly rising sequence of numbers (for n = 10000, the product has only 75 digits).

For n up to 10000, prime pairs occur for n = 3, 5, 6, 14, 23, 28, 33, 41, 43, 48, 265, 897, 909, 1142, 1625, 2378, 2476, 2534, 2822, 3055, 3434, 3837, 4286, 4372, 5865, 8261, 8685, 9195, 9255, 11366, 12984, 16029, 17497, 18278, 18560, 19730, 20450, 21442, 24490, 24603, 25005, 25220, 26243, 29321, 29460, 30518, 31309, 33639, 35143, 35251, 35545, 36085, 37002, 37420, 38536, 38609, 39915, 41303, 47067, 52939, 53485, 53649, 55439, 58004, 58522, 63899, 65529, 65917, 66078, 71720, 72229, 74926, 77744, 79595, 80911, 83279, 83428, 84407, 86386, 87996, 89808, 89912, 94513, 95425, 96933, 98419

Any other strictly monotonically rising sequences with a simple form such as the two just considered, for example the triangular numbers, rise faster and so the products rise much slower, meaning that although there are much larger solution spaces, it takes a lot of effort to reach numbers of a size that makes them interesting. In order to speed up the rate of increase, we therefore must consider removing the strictness of the sequences.

Consider the staggered sequence defined by a2i = a2i-1 = i (that is, 1, 1, 2, 2, 3, 3, …m, etc), giving the product

n.(n-1).(n-2).(n-4).(n-6).(n-9).(n-12).(n-16).(n-20).(n-25).(n-30)…

In fact, this can be broken down into a product of the two separate sequences:

n.(n-1).(n-4).(n-9).(n-16).(n-25)…      and       (n-2).(n-6).(n-12).(n-20).(n-30)…

where the first sequence has a separator sequence of the odd numbers and the second has a separator sequence of the even numbers. If we represent the complex multifactorial based on the odd numbers as n!O and the one based on even numbers as n!E, then the combination can be represented as n!O.n!E divided by an extra occurrence of n.

This is a cumbersome combination, but more appealing is the n!O form (the n!E being a unsuitable as this is odd or even depending on n and so every second value of n!E+1 would be even). The n!O form, as can be seen by inspection, contains square numbers as its intermediate sums. At n = 1000, the digit length is 88 and at n = 10000 this rises to 375.

For n up to 10000, there are prime pairs for n!O±1 at n = 3, 4, 6, 12, 48, 60, 781 and 1354.

In order to preserve a noticeable size increase as n rises, we may consider reducing a monotonically increasing separator sequence modulo a particular integer. In this case, we could either ignore elements in the sequences that are zero, or include them, the latter choice meaning repetition of values in the full expansion. For instance, if we let ai be the triangular number Ti modulo 10, then the separator sequence becomes {1, 3, 6, 0, 5, 1, 8, 6, 5, 5, …} with intermediate sum bi taking values {1, 4, 10, 10, 15, 16, …} and we may consider the expansion n.(n-1).(n-4).(n-10) and then either include another (n-10) for the zero separator, or ignore it and go straight to (n-15). As ever, the expansion for a particular n continues only while bi < n.

We could even replace a modulated rising sequence by the digits in the decimal expansion of any of a number of well known transcendental numbers such as p, e, l, etc. Assuming that we can expand these numbers to the required accuracy (which should not be a problem as there are published expansions well beyond the millionth term), the multifactorials based on these modulated sequences will rise at a rate much faster than for a rising sequence, providing fewer but hopefully larger primes.