## Message 17461 from Yahoo.Groups.Primenumbers

Return-Path: <jens.k.a@...> X-Sender: jens.k.a@... X-Apparently-To: primenumbers@yahoogroups.com Received: (qmail 4708 invoked from network); 31 Dec 2005 17:02:20 -0000 Received: from unknown (66.218.66.172) by m1.grp.scd.yahoo.com with QMQP; 31 Dec 2005 17:02:20 -0000 Received: from unknown (HELO swip.net) (212.247.154.97) by mta4.grp.scd.yahoo.com with SMTP; 31 Dec 2005 17:02:19 -0000 X-T2-Posting-ID: zxQ0VDl87YJPv2Fvy7PJHg== X-Cloudmark-Score: 0.000000 [] Received: from [195.82.220.22] (HELO jensathlonxp) by mailfe04.swip.net (CommuniGate Pro SMTP 5.0.2) with SMTP id 68060264 for primenumbers@yahoogroups.com; Sat, 31 Dec 2005 17:55:42 +0100 Message-ID: <001b01c60e2b$16daabd0$16dc52c3@jensathlonxp> To: "Prime Numbers" <primenumbers@yahoogroups.com> References: <007d01c60dcd$0db3c5e0$05001aac@Ambroxius> Date: Sat, 31 Dec 2005 17:55:13 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 8bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2741.2600 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2742.200 X-Originating-IP: 212.247.154.97 X-eGroups-Msg-Info: 1:12:0:0 From: "Jens Kruse Andersen" <jens.k.a@...> Subject: Re: [PrimeNumbers] Prime GAP of 364,188 X-Yahoo-Group-Post: member; u=125539524; y=ZcQ8_LLwXA6K2kBQZvAhGSurWQ35VRQJNsRh6YmL19zzNA X-Yahoo-Profile: jkand71Jose 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 AndersenMessage 17459 Message 17462 Message 17480 Message 17488