2507re: [PrimeNumbers] GAP of 93918 between two PRPs

Expand Messages
• Sep 3, 2001
I suggest the following formula for assigning a weight to a prime
gap discovery:

exp(g / ln(N)) . g . (ln N)^2 . ln(ln N) ..................... (1)

g is the length of the gap, N is one of the endpoints. Or maybe the
midpoint. It doesn't matter too much. The higher the weight, the
more remarkable the discovery.

The formula attempts to take into account both the rarity of the gap
amongst primes of size N, [ exp(g/ln(N)) ] and also the
approximate difficulty (CPU cycles) required to find it/check it.

It may be used to compare PRP gaps with PRP gaps. It may also
be used, if desired, to compare Prime gaps with Prime gaps.
However, for large N, the chief difficulty in proving a prime gap
would be in proving the numbers prime and not just PRP.

The justification for the fomula: Let n = ln(N)

To check the gap itself requires testing o(g) numbers for probable
primality. Each test takes o(n) FFT multiplications. Each FFT
multiplication takes o(n.ln(n)) basic operations. Checking the gap
therefore takes o( g n^2 ln(n) ) CPU cycles.

The rarity of a gap of length g of numbers of this size is of order
exp(-g/n). To actually FIND (not just check) the gap of length g
requires, therefore,
o( g n^2 ln(n) ) / exp(-g/n) = o( exp(g/n) g n^2 ln(n) ) CPU cycles,
for a naive search. Therefore I present the formula (1) above as a
reasonable formula for judging a prime gap or a PRP gap. If people
use nifty brainy tricks to save themselves a few CPU cycles, they
should not be penalised for that. That's why I assume a naive
search to derive the formula.

Note that it CAN NOT be used to compare a prime gap with a PRP
gap. Apples to Oranges, as someone else said.

Yours, Mike H...

Michael Hartley : Michael.Hartley@...