Removing the Restrictions

We have previously considered sequences n!m±x for locating large pseudoprimes, with the proviso that gcd(m,x) > 1. Let us loosen this restriction. Any prime p that divides n! can only divide n!±x if p divides x. If we let x be a small prime such that gcd(m,x) = 1, then this is impossible unless p = x. We therefore have our familiar sieve effect minus a single prime. If we are willing to divide out this prime prior to testing, then we have a possible source of pseudoprimes.

Consider
m=2 and x=3.

For
n sufficiently large (n > 8), n! is divisible by 3^{2} and so n!2±3 is exactly divisible by 3 with no higher
powers appearing. If n is even, then n!2 is even and so n!2±3 is odd, and we can divide out by 3.
However, these numbers are subject to BLS and so any probable prime can be
proved prime easily.

Of
more interest is the case when n is odd, so that n!2±3 is even. The exact power of 2 that divides
this number now becomes important. We shall use the same technique as before. The divisibility pattern of n!2 modulo 4 is a
repeating cycle of length 8 on n as follows: 1, 0, 3, 0, 3, 0, 1, 0. For n odd,
n!2+3 is therefore divisible exactly by 2 for n = 3 and 5 mod 8. Hence n!2+3 is
exactly divisible by 6, and so (n!2+3)/6 survives our sieve. Similarly, (n!2-3)/6 survives our sieve for n = 1 and 7 mod
8. We can take this further by considering the pattern of n!2 mod 8, which also
repeats modulo 8: 1, 0, 3, 0, 7, 0, 1, 0 (note that we only consider n
sufficiently large). In this case, considering offsets, it is obvious that
n!2+3 is exactly divisible by 4 when n = 1 and 7 mod 8 so that we may consider
numbers of the form (n!2+3)/12, while n!2-3 is exactly divisible by 4
only when n = 5 mod 8, whence we consider the form (n!2-3)/12. In the positive case, there are no
more values of n to consider, since all four odd positions mod 8 are accounted
for. However, in the negative case, it is possible to keep stepping up by
powers of 2 in order to cover one of the two remaining positions. We know that
for this to happen, we require n = 3 mod 8, which converts to 3 and 11 mod 16.
The second of these two provides division exactly by 2^{3}, so we may
consider in this case numbers of the form (n!2-3)/24. This leaves n = 3 mod
16, which doubles up to 3 and 19 mod 32. Again, the second of these divides
exactly by 2^{4}, and repeating, n = 35 mod 64 divides exactly by 3^{5}.
This process continues, always leaving n = 3 mod 2^{k+1} when
considering 2^{k}, so that n = (2^{k}+3) mod 2^{k+1} is
always exactly divisible by 2^{k}.

For
m=2 and x=5, a similar situation arises in that for the two cases, positive or
negative, one covers all possibilities at a certain power of 2, while the other
allows stepping up. We use the same divisibility pattern of n!2 mod 8 as above,
but adjusted by offsets of +5 and -5. In the negative case,
this leads us to consider (n!2-5)/10 for n = 3 and 5 mod 8
and (n!2-5)/20 for n = 1 and 7 mod 8,
with all positions accounted for. In the positive case, we can look at (n!2+5)/10
for n = 1 and 7 mod 8, but (n!2+5)/20 only for n = 5 mod 8, leaving room to
step up; for instance we can take (n!2+5)/40 for n = 3 mod 16. This time the
one unaccounted value alternates either side of 2^{k} mod 2^{k+1}
when considering division by 2^{k}, so that we can take (n!2+5)/80 for
n = 27 mod 32, (n!2+5)/160 for n = 11mod 64, (n!2+5)/320 for n = 107 mod 128,
etc.

A
simple program generates test data for m=2 and x=3 or x=5, leading to the
following table of probable primes.

(6351!2+5)/10 |
10698 |

(6517!2-5)/10 |
11014 |

(9233!2-5)/20 |
16303 |

(9269!2-3)/12 |
16374 |

(9365!2-5)/10 |
16565 |

(9735!2-3)/6 |
17301 |

(9835!2-3)/24 |
17500 |

For m=3, let us consider x=2. It is obvious that n!3±2 is always divisible by 2 exactly (that is, no higher powers of 2 appear). The divisibility pattern of n!3 mod 6 is: 4, 2, 0, 4, 4, 0, giving offset patterns of 6, 4, 2, 6, 6, 2 and 2, 6, 4, 2, 2, 4 for the positive and negative cases respectively. These allow us to identify when the numbers are divisible by 2 and not 3. In the positive case, this happens for n = 2, 3, and 6 mod 6, and in the negative case, for n = 1, 3, 4, 5 and 6 mod 6. These provide a source of potential primes, since BLS kicks in. If, on the other hand, we are interested in finding probable primes that cannot be reconciled by BLS, then we must consider divisibility by 3. The pattern for n!3 mod 9 is:

1,
2, 0, 4, 1, 0, 1, 8, 0, 1, 7, 0, 4, 8, 0, 1, 1, 0, a repeating cycle of length
18.

In
the positive case, this provides divisibility by 3 exactly at n = 1, 4, 5, 7,
10, 13, 16 and 17 mod 18, and so for these values of n, we may consider the
form (n!3+2)/6. The only position where higher powers of 3 appear is at n = 11
mod 18. We could expand n!3 modulo 54 to locate divisibility by exactly 3^{2},
but it is easier simply to use observation and expectation to deduce that we
can also use the form (n!3+2)/18 for n = 11 and 47 mod 54, leaving n = 29 mod
54 for stepping up. In this particular case, for each step up in power, 2 out
of 3 possibilities are used up, so that we may consider (n!3+2)/54 for n = 29
and 137 mod 162, leaving n = 83 mod 162 for stepping up, ad infinitum.

In
the negative case, using the n!3 mod 6 pattern above, we have that n!3-2 is divisible by 2 exactly, and not 3, when
n = 1, 3, 4, 5 and 6 mod 6, providing a large source of potential primes. Using
the n!3 mod 9 pattern, the occurrence of exact divisibility by 3 is less
frequent, at n = 8 and 14 mod 18 only, with higher powers possible for n = 2
mod 18. For completeness, we have exact divisibility by 3^{2} at n = 20
and 38 mod 54, and exact divisibility by 3^{3} at n = 56 and 110 mod
162, leaving n = 2 mod 162 for stepping up. A generated list of test data
provides:

(10490!3-2)/6 |
12542 |

(16051!3+2)/6 |
20179 |

Lastly,
we consider m=4 and x=3. Again, all these numbers (for sufficiently large n ³ 24) are divisible exactly by 3, leaving us
to investigate divisibility by powers of 2, which again obviously can only
occur when n is odd. The n!4 divisibility pattern modulo 4 is: 1, 0, 3, 0, 1,
0, 1, 0 so we may consider (n!4+3)/6 when n = 3 mod 8 and (n!4-3)/6 for n = 1, 5 and 7 mod 8. For each
higher power of 2, the divisibility pattern doubles in length, and we can
consider (n!4+3)/12 when n = 1, 13 and 15 mod 16, (n!4+3)/24 for n = 5, 7, and
25 mod 32, (n!4+3)/48 for n = 9, 21 and 55 mod 64, etc. and also (n!4-3)/12 for n = 11 mod 16, (n!4-3)/24 for n = 19 mod 32, (n!4-3)/48 for n = 35 mod 64, etc. A generated
list of test data fed into openpfgw gives us:

(12885!4-3)/6 |
11842 |

(13603!4-3)/48 |
12582 |

(15749!4+3)/24 |
14817 |

(18873!4-3)/6 |
18127 |

(20587!4-3)/12 |
19968 |

(20997!4+3)/24 |
20410 |

(22639!4+3)/12 |
22191 |

(23413!4-3)/6 |
23035 |

(23419!4-3)/12 |
23042 |