mersenneforum.org Prime Gap Theory
 Register FAQ Search Today's Posts Mark Forums Read

2016-02-27, 09:22   #23
robert44444uk

Jun 2003
Oxford, UK

1,933 Posts

Quote:
 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.

 2016-02-28, 17:01 #24 robert44444uk     Jun 2003 Oxford, UK 1,933 Posts 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. Last fiddled with by robert44444uk on 2016-02-28 at 17:02
2016-03-02, 18:24   #25
mart_r

Dec 2008
you know...around...

12128 Posts

Quote:
 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#.

Last fiddled with by mart_r on 2016-03-02 at 18:31

 2016-03-04, 07:33 #26 robert44444uk     Jun 2003 Oxford, UK 1,933 Posts 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. Last fiddled with by robert44444uk on 2016-03-04 at 12:28
 2016-03-09, 11:06 #27 Antonio     "Antonio Key" Sep 2011 UK 32·59 Posts 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 : Code: # 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"}; . . . Attached Thumbnails  2016-03-09, 16:57 #28 danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 90810 Posts 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: Code: 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.
2016-03-09, 22:52   #29
Antonio

"Antonio Key"
Sep 2011
UK

32×59 Posts

Quote:
 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: Code: 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.

2016-03-13, 18:10   #30
Antonio

"Antonio Key"
Sep 2011
UK

32×59 Posts

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.
Attached Files
 GCD.pdf (12.2 KB, 185 views)

 2016-03-13, 20:09 #31 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 22·227 Posts 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: Code: 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: Code: 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. Last fiddled with by danaj on 2016-03-13 at 20:11
2016-04-02, 10:06   #32
robert44444uk

Jun 2003
Oxford, UK

1,933 Posts

Quote:
 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": Code:  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.

2016-04-03, 12:45   #33
Antonio

"Antonio Key"
Sep 2011
UK

21316 Posts

Quote:
 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: Code: 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.

Last fiddled with by Antonio on 2016-04-03 at 12:46

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 6 2016-10-14 19:38 firejuggler Math 0 2016-07-11 23:09 Ricie Miscellaneous Math 24 2009-08-14 15:31 jasong Math 3 2005-05-15 04:01 clowns789 Miscellaneous Math 5 2004-01-08 17:09

All times are UTC. The time now is 17:41.

Tue May 11 17:41:12 UTC 2021 up 33 days, 12:22, 1 user, load averages: 2.96, 2.93, 3.22