More Primes from the Factorials

A lot of effort has been expended in the past in searching for primes amongst numbers of the form n!±1. The in-built sieve also exists for any number of the form n!±a, excepting any primes dividing both n! and a. However, if we suppose that a £ n, then we can always divide by a, to obtain numbers that will easily fall to the Brillhart-Lehmer-Selfridge primality test. It remains to choose a so that the formula does not get out of hand, otherwise we would end up checking every number of the form (n!±a) / a for all a £ n!, which is nonsensical.

Consider a = 2. We could then check numbers of the form (n!±2)/2 for rising n. This has already taken place, since it is the most obvious form to select. However, we could equally well consider any power x of 2, as long as 2x £ n!. The highest power of 2 dividing n! can be obtained simply by counting first the even numbers, then those divisible by 4, etc., until 2x > n, that is, [n/2]+[n/4]+…+[n/2y] as long as 2y  £ n. In fact, for any prime p, the highest power of p dividing n!, which I will call fme(n,p), is [n/p]+[n/p2]+…[n/py] where py+1 > n. By the rules of convergent series, it is obvious that fme(n,p) is bounded above by n/(p-1). However, when a = pfme(n,p), the sieve quality is lost, as every power of p has been removed, leaving the possibility that the (n±a) / a is itself divisible by p. Hence, we consider prime powers only up to fme(n,p)-1.

Obviously the numbers (n!±px)/px vary in size with x, though the larger the value of p, the less numbers have to be considered, and also the smaller the size range of numbers to be considered. For instance, at n=1000, for p=2, we have fme(1000,2) = 994, and the numbers to be tested range from 2568 digits down to 2269, whereas for p=3, fme(1000,3) = 498 and the size range is 2568 down to 2331 digits. For p=5, fme(1000,5) = 249 and the size range is 2566 down to 2395 digits. Even so, the search space is enormous.

There are a few divisibility rules, based on the following result.

Lemma: For any prime q ¹ p, where the order of p to the base q is y, then the number (q-1)!+pmy is divisible by q for all m. Dividing by pmy does not affect this, since gcd(p, q) = 1.

Proof: Since (q-1)! º (q-1) mod q, and by definition, pmy º 1 mod q, we just add the two left hand sides and the two right hand sides of these equations to get our result.

In practice, very few primes q have low orders. However, for p=2, if q=My is a Mersenne Prime, then by definition, 2y º 1mod q and so ((q-1)!+2my)/2my is divisible by q for all m, including such (q, y) pairs as (8191,13). The only other (q, y) pair for p=2 with notably small y is (1801,25).

For p=3, we have the pairs (757,9), (1093,7), (1871,17) (3851,11), (4561,15) and (34511,17).

For p=5, we have (521,10), (829,9) and (19531,7)

For p=7, we have (1063,9), (1201,8), (2801,5) and (4733,5).

For p=11, we have (3221,5), (7321,8), (13421,10) and (45319,7)

For p=13, we have (2411,10), (14281,8) and (30941,5).

For the negative case, we would be looking for primes q for which we can find a solution of py º -1 mod q, so that (q-1)!-pmy would be divisible by q for all odd m (even m would reverse the sign).

For p=2, and for reasonably large q, this happens at the (q, y) pairs (257,8), (331,15), (683,11), (2731,13) and (43691,17).

For p=3, this happens at (547,7), (661,11), (1181,10), (6481,12) and (16493,14).

For p=5, we have (313,4), (449,7), (521,5), (601,6), (5167,9), (5227,13), (5281,11), (9161,10), (11489,8) and (38923,13).

For p=7 we have (911,7), (1201,4), (4021,10) and (51031,21).

For p=11 we have (1117,6), (7321,4), (13421,5) and (58367,11).

For p=13 we have (937,9), (2411,5), (14281,4), (22079,7) and (28393,6).

In order to restrict the search space for numbers of the form (n!±px)/px, it makes sense to consider restricting x in some meaningful way. The most obvious move is to consider x = f(n), where f is a function of n such that f(n) < n (and preferably f(n) << n) and f(n) is a positive integer. This turns out to be more difficult than one would imagine, and it makes more sense to consider x = f(p), since we already have the restriction x < fme(n,p). Since we want to keep things manageable, consider x = p. Since fme(n,p) is bounded above, but not substantially less than, n/(p-1), then, for each prime p, as n approaches p2, fme(n,p) increases in value beyond p, whereupon n! can be divided by pp and retain its full sieve-effect. For each n, we then only have to search through the primes for which p < fme(n,p), which is a slowly growing set bounded above by [Ön]. For instance, at n = 1000, we only have to search through the primes up to 31. The following table lists primes found in this way with digit length greater than 10000.

 (3281!+17^17)/17^17 10093 (3320!-3^3)/3^3 10250 (3325!+41^41)/41^41 10202 (3447!-29^29)/29^29 10657 (3500!+47^47)/47^47 10808 (3613!+19^19)/19^19 11264 (3622!+31^31)/31^31 11274 (3646!-43^43)/43^43 11335 (3710!+11^11)/11^11 11622 (3717!-19^19)/19^19 11635 (3801!-7^7)/7^7 11953 (4134! -43^43)/43^43 13087

We note that in the standard form, the positive and negative versions differ by 2. Since the search space is so large, it therefore makes more sense to consider searching for twin primes. A fast sieve across either positive or negative values typically reduces the search space by 50%, and so a combined sieve leaves some 25% of the total search space on which to perform pseudoprimality tests. I have completed this for p=2 across the range n=1001 to 2000, which left 1128 probable primes with positive sign, which provided enough of a sample set to produce 6 probable primes with negative sign. These numbers were subsequently proved prime, as follows.

(1079!+2^470)/2^470 & (1079!-2^470)/2^470

(1124!+2^917)/2^917 & (1124!-2^917)/2^917

(1160!+2^732)/2^732 & (1160!-2^732)/2^732

(1257!+2^564)/2^564 & (1257!-2^564)/2^564

(1438!+2^544)/2^544 & (1438!-2^544)/2^544

(1905!+2^259)/2^259 & (1905!-2^259)/2^259

I had to perform the sieving separately for positives and negative. A preferable method would be a combined sieve, but this was not available at the time, and discourages me from pushing higher for p=2.

For p=3, only 525 primes with positive sign survived a combined sieve, and from this, only one produced a twin:

(1168!+3^433)/3^433 & (1168!-3^433)/3^433

For p=5, only 246 primes with a positive sign survived a combined sieve. From this, two produced twins:

(1142!+5^94)/5^94 & (1142!-5^94)/5^94

(1966!+5^275)/5^275 & (1966!-5^275)/5^275

For p=7 we have

(259!+7^21)/7^21 & (259!-7^21)/7^21

(301!+7^26)/7^26 & (301!-7^26)/7^26

To take this concept forward would require an efficient sieving mechanism for twin primes of the appropriate form. Unfortunately none of the freely available sieving routines are able to operate of these forms. The best option at the moment is to perform a sieve over both positive and negative values at the same time and remove all entries for which either or both have a small factor before performing a pseudoprime test on all the positive values and only subjecting the survivors to a pseudoprime test on the negative side.

Since the fme(n,p) powers of p in the product n! divide every p-th entry, we can consider restricting to (n!p±px)/px, as long as n itself is divisible by p. In this way we can search for twin primes over additional, slower rising sets of multifactorials with reduced search ranges.

For p=2 and n < 2000 this gives twin primes at:

(1072!2+2^47)/2^47 & (1072!2-2^47)/2^47

(1154!2+2^83)/2^83 & (1154!2-2^83)/2^83

(1318!2+2^1139)/2^1139 & (1318!2-2^1139)/2^1139

(1448!2+2^46)/2^46 & (1448!2-2^46)/2^46

(1582!2+2^1320)/2^1320 & (1582!2-2^1320)/2^1320

(1724!2+2^1491)/2^1491 & (1724!2-2^1491)/2^1491

(1980!2+2^1474)/2^1474 & (1980!2-2^1474)/2^1474

(1992!2+2^1934)/2^1934 & (1992!2-2^1934)/2^1934

And for p=3 we have

(1770!3+3^202)/3^202 & (1770!3-3^202)/3^202

(1962!3+3^649)/3^649 & (1962!3-3^649)/3^649

(2184!3+3^920)/3^920 & (2184!3-3^920)/3^920

(2187!3+3^927)/3^927 & (2187!3-3^927)/3^927

(2565!3+3^392)/3^392 & (2565!3-3^392)/3^392

Last updated: 19/11/2010