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