- Feb 8, 2005As you may recall, I resumed Mike Oakes' search for primo-factorials, primes
of the form n! +/- n# +/- 1. Mike had stopped at n = 7039, and I picked up
the search until 10000. 2 PRPs were found, 8147! + 8147# - 1 and 9627! -
9627# - 1. Maybe I'll keep on searching for n > 10000, but I don't feel very
inclined to do so unless I can do better than PRP-ing all the candidates.
Specifically, I'm thinking of sieving them. However, the first sieve that
comes to mind (computing n! +/- n# +/- 1 mod 2, 3, 5, 7, ...) is largely
ineffective for the task, since n! +/- n# have as common factors all primes
up to n. One might argue `fine, let's sieve with primes larger than n them.'
However, this is a very inefficient sieve: by Mertens' theorem, only 6.1%
percent of random integers aren't divisible by primes up to 10,000, while
2.71% percent of random integers aren't divisible by primes up to a billion
(a very very optimistic sieve bound). Thus, using this sieve I could at best
eliminate 55.5% (= 1 - 2.71/6.1) of candidates, certainly not a worthwhile
effort for the time it would take to sieve up to a billion.
Thus I am led to ask the group for other strategies to sieve this sequence of
primes. Everything I've come up with until now relies on the following facts:
1. n! +/- n# +/- 1 = n#*(n!/n# +/- 1) +/- 1, where n!/n# is an integer.
2. For a given prime p, then n#*(n!/n# +/- 1) +/- 1 == 0 mod p implies
n#*(n!/n# +/- 1) == +/-1 mod p, so that n# or -n# is an inverse mod p of
(n!/n# +/- 1).
3. And of course, it's easy to perform reductions modulo p, as we can easily
enumerate the prime factors of n! using Legendre's theorem, then use
Basically what I'm looking for is something relating the congruence classes of
an integer and its inverse, so that I can figure out conditions n that will
have one of n! +/- n# +/- 1 divisible by a chosen prime. If such a result
could be found, then the sequence could actually be sieved in the usual sense
-- discarding the integers that are divisible by a given prime p with less
work than testing all of them.
I'm not placing much hope on the existence of such a method, but as it's been
repeatedly shown here, my knowledge is quite limited (:
[Non-text portions of this message have been removed]
- Next post in topic >>