20160227, 09:22  #23 
Jun 2003
Oxford, UK
2×7×137 Posts 

20160228, 17:01  #24 
Jun 2003
Oxford, UK
2·7·137 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 coprime 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 20160228 at 17:02 
20160302, 18:24  #25  
Dec 2008
you know...around...
2^{2}×5×31 Posts 
Quote:
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 2310range (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 20160302 at 18:31 

20160304, 07:33  #26 
Jun 2003
Oxford, UK
2·7·137 Posts 
I was thinking about mart_r's approach this morning. Would this be an improvement?
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 20160304 at 12:28 
20160309, 11:06  #27 
"Antonio Key"
Sep 2011
UK
3^{2}×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"}; . . . 
20160309, 16:57  #28 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2×3×151 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 squarefreek 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]; # ... 
20160309, 22:52  #29  
"Antonio Key"
Sep 2011
UK
1023_{8} Posts 
Quote:


20160313, 18:10  #30 
"Antonio Key"
Sep 2011
UK
3^{2}·59 Posts 
As a followon 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. 
20160313, 20:09  #31 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
906_{10} 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) ... 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 squarefree 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] Last fiddled with by danaj on 20160313 at 20:11 
20160402, 10:06  #32  
Jun 2003
Oxford, UK
2·7·137 Posts 
Quote:
Given this, I think it will be able to calculate larger ranges relatively quickly so I will have another go at 60060. 

20160403, 12:45  #33  
"Antonio Key"
Sep 2011
UK
3^{2}·59 Posts 
Quote:
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 20160403 at 12:46 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Basic Number Theory 4: a first look at prime numbers  Nick  Number Theory Discussion Group  6  20161014 19:38 
Before you post your new theory about prime, remember  firejuggler  Math  0  20160711 23:09 
Mersene Prime and Number Theory  Ricie  Miscellaneous Math  24  20090814 15:31 
online tutoring in prime number theory  jasong  Math  3  20050515 04:01 
Prime Theory  clowns789  Miscellaneous Math  5  20040108 17:09 