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² 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³, 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⁴, and repeating, n = 35 mod 64 divides exactly by 3⁵. 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², 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² at n = 20 and 38 mod 54, and exact divisibility by 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