Prime Gap Theory

[robert44444uk]

Originally Posted by robert44444uk

If I get less than 5 records then I will let you know.

.

Hah, not 15 minutes in to the run and a record already !!!!

658 as the multiplier and 105.. the offset, around the midpoint 30030. Not a giant, but still the best at 43170.

[robert44444uk]

I decided to extend the 1777# offset using the greedy algorithm and will test at a variety of higher primorials up to 3001#. At 3001# I have 2173 integers in a range of 60060 that are co-prime to 3001#. (3.6%)

Results are quite promising, 4 records in a 8 hour period, on 3.2 cores compared to 2 I have found after 24 hours on 0.8 cores working with the two 1777# offsets.

Starting from the midpoint of the 60060 range, just one of the 3001# tests out of 17,000 has cleared the entire range of 2173, but ran into primes just beyond the minus and plus boundaries. It still managed to improve the 61788 gap record. None of the other higher primorials has such a gap, or cleared both boundaries.

[mart_r]

Originally Posted by robert44444uk

Hah, not 15 minutes in to the run and a record already !!!!

658 as the multiplier and 105.. the offset, around the midpoint 30030. Not a giant, but still the best at 43170.

Wow. I should consider searching for new gaps with this method myself.

My "method" is that I take a set of numbers coprime to 13# (or other small p#) with a randomly chosen offset, analysing the whole gamut of residues and then cancelling out the residue for which the difference between the max and the min value of appearances is largest.
For instance, there would be a maximum number of 340 cancelled out for p=17 in a range of 30030, but the corresponding minimum is 336, which is not much smaller. On the other hand, e.g. for p=131, up to 48 numbers can be cancelled out, compared to a minimum of 38 which is much less, so I'd prefer to first cancel those 48 numbers.
Sieving is done in VisualBasic in an MS Excel environment, and is pretty fast IMHO - well at least compared to Pari (ballpark figure: 7 seconds for one sample at 907#).
The program is flexible in several ways, in that I let it randomly choose not only different residues if there is a tie between two or more, but it also sometimes takes residues which don't necessarily cancel a maximum number of numbers.
It seems like a good strategy for small values, say < 1000#. For the case with the 2310-range (see "covering sets"), I didn't find such a good example with the popular version m*577#/q#.

[robert44444uk]

I was thinking about mart_r's approach this morning. Would this be an improvement?

• choose the range of integers L
• reduce L to L' using small primes up to p[n] where p[n]# is the largest primorial smaller than L. The set L' comprises those integers in L which are coprime to p[n]#
• choose a target prime p[q], which would give prime gaps of approximately 20 merit over L, if p[q]# is used
• run the primes p[n+1]...p[q] individually over L' for each of the mods and rank them in order of the difference between the best performing and worst performing mod - your approach described above
• collect, say, the top fifteen p and collect for each, the mods which are within say 3 of the best for that p
• carry out a 15-nested loop to determine which group of mods, one for each of the 15 primes, provides the most efficient reduction to L'
• Go with this mod solution for those 15 primes, and reduce L' to take out those which are not coprime to each of these primes. The new set is L"
• Repeat the prescription with another 15 primes, excluding those up to p[n] and the 15 already tested, which show the greatest variation of performing mods applied to L"
• Repeat until all primes up to p[q] are treated

If 15 was too many, given the permutations possible, a smaller collection would suffice.

I won't have time to do more than think now for the next three weeks as I am in deepest rural Uganda from tomorrow. No computer, no internet. Bliss.

[Antonio]

In a similar vein to Dana's post http://mersenneforum.org/showpost.ph...4&postcount=13 I have run a test for my 24090 divisor.

The results of this are in the attached spreadsheet.

The data was gathered from a run with the following parameters:
For C = i * p#/d
i from 1e5 to 5e5
d = 24090 (= 2 * 3 * 5 * 11 * 73)
C from 60 to 180 digits
This set of parameters gives p# in the range 151# to 439#

For each composite (C) tested I recorded the GCD = gcd( i, d) and when a merit >= 15 was achieved for that GCD, a total of over 19.6 million tests and 1955 merits (>= 15) were logged.

The spreadsheet is ordered according to the yield (merit count / number of trials) of each GCD recorded. (The gcds with zero yield are reported lower left for completeness).

I have subsequently used this to determine which GCDs to include in my search. The following rules were used:
1. GCD 1 must be included (otherwise we are effectively using a different divisor).
2. Include the GCDs in order of yield while doing so does not decrease the overall yield.

As can be seen the final result was to use GCDs of 1, 55, 803, 11 and 5.
I then took the decision to exclude 803 as a value for two reasons:
1. The resulting effective divisor is 30, which is well covered by other searchers
2. Doing so allowed me to use the same script with my other main divisors which are also of the form 2*3*5*11*P.
Fortunately, the values associated with 803 are so small it's remove has little effect on the overall result.

The resulting code change to accommodate this :

# define the GCD's to use
my %gcd;
$gcd{"1"} = 1;
$gcd{"5"} = 1;
$gcd{"11"} = 1;
$gcd{"55"} = 1;
.
.
.
# Completed preparations, now search the requested range
while ($endi > $i++) {
 my $g = gcd($i, $divisor); # Also used later to simplify the expression for a gaps starting prime
 next unless defined $gcd{"$g"};
.
.
.

[danaj]

Great post, Antonio. I really enjoyed reading it. It's an interesting way of handling multiple divisors at the same time, and unlike the 2*3*5*k or square-free-k searches the number of divisors doesn't blow up as k increases.

Wrong thread for this portion but since I'm already making a post ... While it doesn't matter for large searches because the time is in prev_prime, for small values this is faster:

my @gcd;
$gcd[$_] = 1 for (1, 5, 11, 55);
# ...
  next unless $gcd[$g];
# ...

Since $g is a small native int, that saves doing a string conversion and hash lookup. I benchmarked a loop with just the gcd and condition, and this came out 1.5x faster. A very small improvement, but I've lately been doing searches in the sub-2k range where the overhead is important because prev_prime is fast. With divisors in the millions this change may not be as attractive.

[Antonio]

Originally Posted by danaj

Great post, Antonio. I really enjoyed reading it. It's an interesting way of handling multiple divisors at the same time, and unlike the 2*3*5*k or square-free-k searches the number of divisors doesn't blow up as k increases.

Wrong thread for this portion but since I'm already making a post ... While it doesn't matter for large searches because the time is in prev_prime, for small values this is faster:

my @gcd;
$gcd[$_] = 1 for (1, 5, 11, 55);
# ...
  next unless $gcd[$g];
# ...

Since $g is a small native int, that saves doing a string conversion and hash lookup. I benchmarked a loop with just the gcd and condition, and this came out 1.5x faster. A very small improvement, but I've lately been doing searches in the sub-2k range where the overhead is important because prev_prime is fast. With divisors in the millions this change may not be as attractive.

Thanks, as to your suggested code change - I realised the 'stringification' (?!) wasn't required when I re-read the post (to late to edit though), that's what you get for doing a copy, paste & modify with your brain turned off.

[Antonio]

As a follow-on from my previous test, and with Dana's MOD 30 analysis in mind I ran a similar test to his but only counting multipliers which gave a GCD of 1, 5 11 or 55 with divisor 24090.

There was a minor change between the two trials, in that the first trial used a 'delta' value of 6 merits whereas this trial used a 'delta' value of 3 merits, explaining the increase in the number of trials where the merit was >= 15.

The results are presented in the attached PDF, and as can be seen have a good correlation with Dana's results, especially with the predominance of results which are 5 or 25 MOD 30.

[danaj]

I started an experiment to look at divisors, but did not finish and don't plan on running it in the near future, but thought I'd share the idea and a hypothesis from the partial data. Send me a PM if you want the program I used or want me to post a link.

The question was 'what are the best divisors when searching for k * n# / d' ? One crude measure is to see what divisors show up the most in current results. That shows:

Freq   divisor
22284  30
 4584  7410   (Jacobsen)
 3699  2310   (Jansen, MJPCJKA use this a lot)
 3544  46410  (Rob)
 2737  15630  (Antonio)
 1910  210
 1238  24090  (Antonio)
 1100  9570   (Antonio)
  816  7590   (Antonio)
  550  30030  (MJPCJKA, Jansen)
  485  6
  384  93030  (Jacobsen)
  307  330    (Jansen, Jacobsen)
  216  510510
  213  4818   (Jacobsen, Antonio)
  ...

While 7410 is the second most common divisor, that's because I picked it last October as what looked like a good example of 2*3*5*p*q, and dedicated a computer to searches with it. It was almost randomly chosen. That it has been very successful is more a factor of resources dedicated to it and the search spending a lot of time in the 60k-100k range. I don't think looking at the current record holders is a good measure of quality.

I've done a lot of searches that covered '2*3*p' and '2*3*5*p' and '2*3*5*7*p'. I also started a 'every square-free d up to 510510' at one point. Analyzing these results might be interesting but nothing obvious sprung out at me.



So using something similar to Antonio's parameters I started gathering the number of found merits >= 15 with C = i * p# / d with i from 1e5 to 5e5, p from 36 to 46, and d running through the square free numbers to 510510. The script I used restricted to those numbers with factors under 100 which is a mistake for this experiment. It also takes a huge amount of time which is one reason I stopped after a while. I think more 'p' values should be used.

I printed the number of trials and number of successes for each combination of p and d. I summed both over each p to get a trials and successes for each d. Using the partial data I got (about 1 million tests for each divisor under 1000), sorted by success rate and also showing the factorization:

Percent   divisor [factors]
.03688      6 [2 3]
.03096    537 [2 3 89]
.03064    498 [2 3 83]
.02948    474 [2 3 79]
.02913    402 [2 3 67]
.02851    438 [2 3 73]
.02845    582 [2 3 97]
...
.02019     30 [2 3 5]
.01977    102 [2 3 17]
.01964     42 [2 3 7]
.01732     66 [2 3 11]
...
.01672  4818 [2 3 11 73]
...
.00795   210 [2 3 5 7]
...
.00731   330 [2 3 5 11]

Which suggests the best divisors are 6 and 2*3*p. 10x more likely to have merit 15+ than things like 2*3*5*7*p. I'm not entirely convinced this hypothesis is true, and would like to see some other evidence. In the mean time I moved some of my divisor = 30 searches to 2*3*p searches as it can't hurt.

[robert44444uk]

Originally Posted by mart_r

There are just too many possible choices for the different residues, it's practically impossible to get the best solution.

But here are some comparisons for the 30030 @ 907# case, with my "effective merit":

         remaining #s  eff.merit  exp(eff.m.)
average:         2464  34.8500    1.365 E+15
my first sieve:  1789  25.2955    9.676 E+10
your solution:   1767  24.9844    7.089 E+10
my new sieve:    1725  24.3906    3.915 E+10
907#/210-15015:  1633  23.0898    1.066 E+10

The value in the last column shows the average number of tries to find a whole 30030-range devoid of primes, which would result in a gap of at least merit 34.85.
As you can see, there's still a lot of room between my latest solution and the popular one.

My overnight calculation was cut short because I saved my file in the old xls format (instead of xlsx), so after about half an hour it was full with 255 results, the best of which is the above with 1725 remaining numbers. I'm doing another calculation today with a range of 60060 and primes up to 1777, and if everything works out right, I'll be posting some results for you to check for gaps.

The program runs on the computer at my workplace and I don't yet have a copy at home, which I need to run the results - the list of remainders - through Pari to get the actual offset numbers (currently I don't have the time to write my own code to do this). But maybe tomorrow I'll see what I can do about the 2310-range and how many p's it takes until it is completely covered.

I have developed a new algorithm which got me to 1763 remaining for the 30030 range after only 1 hour of processing on one core.

Given this, I think it will be able to calculate larger ranges relatively quickly so I will have another go at 60060.

[Antonio]

Originally Posted by danaj

So using something similar to Antonio's parameters I started gathering the number of found merits >= 15 with C = i * p# / d with i from 1e5 to 5e5, p from 36 to 46, and d running through the square free numbers to 510510. The script I used restricted to those numbers with factors under 100 which is a mistake for this experiment. It also takes a huge amount of time which is one reason I stopped after a while. I think more 'p' values should be used.

I printed the number of trials and number of successes for each combination of p and d. I summed both over each p to get a trials and successes for each d. Using the partial data I got (about 1 million tests for each divisor under 1000), sorted by success rate and also showing the factorization:

Percent   divisor [factors]
.03688      6 [2 3]
.03096    537 [2 3 89]
.03064    498 [2 3 83]
.02948    474 [2 3 79]
.02913    402 [2 3 67]
.02851    438 [2 3 73]
.02845    582 [2 3 97]
...
.02019     30 [2 3 5]
.01977    102 [2 3 17]
.01964     42 [2 3 7]
.01732     66 [2 3 11]
...
.01672  4818 [2 3 11 73]
...
.00795   210 [2 3 5 7]
...
.00731   330 [2 3 5 11]

Which suggests the best divisors are 6 and 2*3*p. 10x more likely to have merit 15+ than things like 2*3*5*7*p. I'm not entirely convinced this hypothesis is true, and would like to see some other evidence. In the mean time I moved some of my divisor = 30 searches to 2*3*p searches as it can't hurt.

Compare with my earlier results with GCD = 55 (equivalent to divisor of 2*3*73), for the range of p# I used the success rate was almost double that for the range of p# you used (0.0504% compared to 0.02851%).
I suppose this could be caused by the way the range of i values are restricted by the gcd requirement, but that would require further investigation.