Jose Ramón Brox wrote:
> > There are better methods to choose which numbers have small factors.
> > Such methods were used for the 2 known Megagaps:
> >
http://hjem.get2net.dk/jka/math/primegaps/megagap.htm
>
> Indeed a very intelligent approach: I was wondering how all that records
> could be arrived at, and now I know. Are there any other approaches,
> or yours is the main used one?
AFAIK, all efficient searches for large gaps between large primes/prp's (e.g.
above 50 digits) have included some variant of these points:
1) Choose a size of prp's, and an interval size to hopefully be part of a
large prime gap.
2) For each small prime, choose which numbers in the interval that prime
should divide, trying to minimize the "overlap" with other primes.
3) Solve a set of modular equations from 2) to find an interval with the
chosen divisibility properties.
4) Do prp testing to find out how large the gap actually is.
2) and 3) are also used in many CPAP searches, obviously with the addition
that the targeted primes should _not_ have any of the small prime factors. It
was used for all known CPAP's of length at least 7 (where at least 1254
composites are needed).
The paper about the first known CPAP-7 [1] says:
"by extending a method of Nelson for assuring that a given set of numbers
would be composite, such a search became practical [2]."
For large numbers, it is far too hard to find the optimal solution in 2).
Different algorithms for searching good solutions have been used.
The simplest algorithms are "greedy". For each prime in increasing order, they
maximize the amount of new numbers divided by that prime.
More complicated algorithms use back tracking when choices for smaller primes
later turn out to be unfortunate. I don't know whether others have used back
tracking before me but I would be surprised to be first. Jim Fougeron appears
to have a better back tracker than me.
A possibly new idea by me (used in the second Megagap but not the first) was
to not always pick the smallest primes, but search larger primes which could
divide more hitherto unfactored numbers. I haven't seen others do this.
The product of the picked primes must be below the chosen prp size to give a
solution below that size in 3).
3) is computationally easy using modular inverse and a library for large
numbers. I use GMP.
Pierre Cami has found some large gaps with simple primorial formulas but he
must have used far more cpu time than 2) and 3) would have.
Sieving can and should be done before 4).
A possibly new idea by me was to sieve a large number of intervals and only do
step 4) for the intervals where sieving factored the most additional numbers.
This is not so significant for the Megagaps but it is for lots of gaps
Torbjörn Alm and I found between smaller prp's.
> Do you know if the smallest gaps with biggest merit are being collected
> somewhere? I don't refer to the biggest known, but to the real ones,
> starting with the first prime gap (between 3 and 5) and finishing in the
> frontier of too-hard-to-compute prime gaps.
First known occurrence prime gaps are at
http://www.trnicely.net/gaps/gaplist.html
For every gap size, it lists the smallest known primes or prp's with exactly
that gap.
[1] Harvey Dubner and Harry Nelson, Seven consecutive primes in arithmetic
progression. Mathematics of Computation, Volume 66, Number 220, October 1997.
[2] Harry L. Nelson, There is a better sequence. J. Recreational Math. 8 (1)
(1975).
--
Jens Kruse Andersen