Loading ...
Sorry, an error occurred while loading the content.

16043Sieving primo-factorials

Expand Messages
  • Décio Luiz Gazzoni Filho
    Feb 8, 2005
    • 0 Attachment
      As 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 (:

      Décio


      [Non-text portions of this message have been removed]
    • Show all 9 messages in this topic