20160210, 21:39  #12  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:
Code:
g=log(r) Code:
if(m,,...) Code:
p<e[#e[,1],1] Code:
c/(w*log(r)) Code:
t=(t+q*(t%2))/2; if(!t,t=q); Code:
if(t,t=(t+q*(t%2))/2,t=q) Code:
r=prod(r=1,primepi(p),prime(r),m/d); Last fiddled with by science_man_88 on 20160210 at 22:06 

20160217, 06:07  #13 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2×3×151 Posts 
None of the following is a surprise, but I ran some experiments and thought the results were interesting enough to post.
tl;dr: Use k values that are {1,5,7,11,13,17,19,23,25,29} mod 30 for best results with k*n#/6 or /30. Other divisors may have different results. I ran a simple experiment looking at k*n#/30 with:  all k values from 1 to 1,000,000 including evens  n from 173 to 337  print every result with merit 15+. then looked at the resulting k values mod 30. 13% each of all results were in class 5 and 25 68% each in classes 1, 7, 11, 13, 17, 19, 23, 29 34% in classes 3, 9, 21, 27 .9% in class 15 .5% or less in all evens, and 0,6,12,18 had no results at all Based on the results for 5/25 and 15, k*n#/6 seems more productive, /2 or /10 less so. With /30, primes plus 1 plus multiples of 5 seem to work best. A downside of using multiples of 5 is that it overlaps with people that have done searches with the 6 divisor. The same thing ran with divisor 210 yields: 12% each for 5, 25 46% each for 1, 3, 7. 9, 11, 13, 17, 19, 21, 23, 27, 29 3% for 15 1+% for 2, 4, 8, 14, 16, 22, 26, 28 < 1% for 0, 6, 10, 12, 18, 20, 24 Similar to /30 but multiples of 3 are even more common. With divisor 6, k mod 30 shows: ~9.5% for 1, 5, 7, 11, 13, 17, 19, 23, 25, 29 ~0.7% for 3, 9, 15, 21, 27 0.1% or less for evens Using the 8 values 1,7,11,13,17,19,23 would find 89.6% of the results and run 88% faster. Adding in 5 and 25 gets 97.6% of the results and runs 50% faster (skipping 3, 9, 15, 21, 27). The speedup would likely be mitigated by prev_prime running quickly due to a small gap and then skipping further processing. To test the mitigation, I timed k=1..2M, n=281#313#, d=30, 10 threads: best10 2049 results 799s 2.56 res/sec +36% odds 2365 results 1258s 1.88 res/sec  all 2432 results 2314s 1.05 res/sec 56% A look at the results from my recent k*n#/30 searches that have run all odds shows results that are similar but not quite the same (5 and 25 are less common instead of more common). Those searches are only showing results that have beat current merits so this may be influenced by previous searches using /6. They show 1,7,11,13,17,19,23,29 to be the best values by far. class 5 and 25 occur half as often, classes 3, 9, 21, and 27 occur 1/20th as often as the top values, and 15 only found one result of 2500. So the coprime selection isn't a bad choice, but adding 5 and 25 wouldn't hurt. Either are more efficient than allodds. I looked at my month or so of results using k*n#/7410 and see similar classes. Doing the same experiment with that divisor shows it isn't as productive as (in order) /6, /30, /210, or /4818. /24090 is somewhat better as well. The classes mod 30 look very similar to the ones I gave for /210. I tried looking at the results Antonio has done with /24090 but it's clear his script is using the set 1,7,11,13,17,19,23,29 so this doesn't tell us anything (probably looking at numbers coprime to the divisor, the theory being that e.g. we would test /4818 separately hence we don't want multiples of 5). Running the experiment above with /24090 shows 5 and 25 to be 2x more common than the others  so /4818 would be a good divisor for someone to test (indeed, I found a merit 31.6 gap during this experiment). 3 and 9 appear as often as the coprime values, and the drop off on other classes isn't very sharp (15 isn't much worse than 23, and 2, 4, 8, 14, 22, and 28 are each over 1%). Using /4818 I get the familiar 1,5,7,11,13,17,19,23,25,29 list at the top, with multiples of 3 also getting ~2% each. Just for info, I tried /12045 since that was brought up on the theory thread. It results in 10x fewer results than /6 or /30 or /25090 for the same number of trials so looks like a bad idea in general. The mod results say to avoid all multiples of 3 and 5 for that example, but keep the evens (leaving 16 of 30 classes). Based on these, I think running all odds makes sense for /210, but changing to the 10of30 list is better for /30 and /6 and some other divisors. 
20160218, 07:29  #14  
"Antonio Key"
Sep 2011
UK
3^{2}×59 Posts 
Quote:
I already have a script to look at just the class 5 and 25 cases for the divisors I use most, and will run it, as soon as I have a core free, over some of the space I have previously covered with them. (Should be starting in the next 24 hours) Oh, and your assumption about my using coprime multipliers is correct. Last fiddled with by Antonio on 20160218 at 07:31 

20160223, 13:47  #15 
Jun 2003
Oxford, UK
2^{4}·7·17 Posts 
Confirmation of something odd
I had observed this before, but now i have seen it again, I have no idea of how to explain the graph below.
I took the greedy algorithm to determine the most efficient modular value x, where R[0]=xmodp over a range if integers R, with R[0] the first member, for increasing p primes, taking one p at a time. Efficiency comprises the largest number of additional integers that can be eliminated, given those already eliminated through smaller primes. If more than one x provides the same level of efficiency, then the smallest x is chosen. I then compared the count of the remaining members of R at each prime to the count of the reference group where the first member is 0modp for all p  i.e. the primorials, which are used extensively by the prime gap searchers. The graph shows a limited range of p covering an Integer range of 60060, and has four areas:
The y axis represents the difference between the cumulative counts of integers in R with no prime factors p or primes smaller than p for the greedy set, less the same for the reference set, at each p. One obvious aspect coming out of this is that a combination of the reference set and the greedy algorithm is more efficient than either on its own. Doing this with this example, going up to p=3001, gave 2,298 integers with no prime factor smaller than 3001 using the combined appoach, compared to 2,345 for the algorithm alone and 5,632 for the primorial alone. This pickup of 2% is well worth having in the world of prime gaps. Last fiddled with by robert44444uk on 20160223 at 14:23 
20160223, 21:53  #16 
Dec 2008
you know...around...
2^{5}×19 Posts 
That might well be correct. Given that you considered a fixed range of 60060, the reference set is sometimes less efficient for some small values of p.
I also experimented with those kind of killing sieves before, where I identified the residues x mod p which appeared a maximum number of times among all x coprime to (p1)#, with several different approaches. The results were sometimes good, but the easier choice of p#/q# was always a bit better and obviously out of reach for my sieve, so I abandoned this idea again. Just today I had another idea and gave it one more try by first eliminating the residues mod p for which the difference between the minimum and the maximum number is largest. I let the computer at my workplace run overnight to see if I can get a good set of residues that eliminates a lot of small factors, the best I could get within a few minutes during my lunch break was 1642 in a range of 30030 numbers without a small factor <= 997. I'll see if I can get something closer to 1562 (for 997#/210+[15015;15015]). That also bears the question, what is actually the minimum number of numbers coprime to 997# in a range of 30030 integers? It cannot be far away from 1550, can it? 30030, 15015, 10010, 8008, 6864, 6240, 5760, 5417, 5125, 4893, 4718, ...??? Edit: The maximum number should be around 3347, according to Thomas Engelsma's site. Last fiddled with by mart_r on 20160223 at 22:02 
20160224, 08:01  #17 
Jun 2003
Oxford, UK
2^{4}×7×17 Posts 
I got to 1767 for 907, which suggests a 1713 at 997,over a 30030 range, and therefore it looks as of you might be miles ahead of me with your x#/y#. I can't for the life of me understand why this is the case.
After 5 days of running, my 139,720 offsets to 907# have only produced 5 records in the 20k to 23k range, with a maximum of 26.6 merit. I asked the coprime question in Maths here at Mersenneforum but it was probably badly worded  I put it in the form of a covering set. I think it is an important question, equivalent to the Sierpinski for power series. Last fiddled with by robert44444uk on 20160224 at 08:06 
20160224, 14:53  #18 
Jun 2003
Oxford, UK
3560_{8} Posts 
I posted this on
http://www.mersenneforum.org/showthr...271#post427271 For the range of 2310. This was calcuated using the simple greedy algorithm. 
20160224, 16:25  #19  
Dec 2008
you know...around...
2^{5}·19 Posts 
Quote:
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#/21015015: 1633 23.0898 1.066 E+10 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 2310range and how many p's it takes until it is completely covered. Last fiddled with by mart_r on 20160224 at 16:34 

20160225, 08:50  #20  
Jun 2003
Oxford, UK
3560_{8} Posts 
Quote:


20160226, 21:55  #21 
Dec 2008
you know...around...
2^{5}×19 Posts 
So here's my best solution after 15 hours on 2 cores:
In a range of [n+0; n+60060] there are 2950 numbers coprime to 1777# for n = Code:
1052296176192451647640479075818694673973812730782514838164741763396374346247479908199754832748502736878253268795905797391379801098917959492677730392033156236494730947042781257198118911053407713954417462677276362048707908535895581380765501067122423987806099069521624776253926618586731849986166076187434086904557001695374339199302773684810969216081838148601209469521079095434323760607220254421498383751489842729855537354845893978888372239550031057051954375088504445545182095418165748263601357319146343467835177976185357849041815393264268176355311648783296334751352961297671017656073778597512943854077701649537056517253702556975949286485154200878256048348514682569715520230175214080419680023488816332295394334654892183515745401918536548830019766970878038 and the mirror image pattern... 4070121366290251717191621971586066179444141007247400216660786553016277357349008178627949497590407745254506793345640272361847123104586854029959369321573183467296073062541942711674196218091799205518087579921752653198166409050332910356485075503337334281527993896010114059094295969562178246326073464918526615258916092665058918792468480006201551082867373401380514284255403344056415198187172952906418704641668972829172634069110961446429490952062905258495702564943855026298294505404340857822854852445677692633548697667791321504952953268475148475383601371236941470802818616141492395010621200617322448433943976077724477592535007723913498229877945426721732933423844649733234939978187702031444592335739827380359420541346890185271901608316926670315552181143686072 Code:
remaining #s effective merit average: 4491 34.75 my first sieve: 3126 24.19 my new sieve: 2950 22.82 < 1777#/21030030: 2815 21.78 I've not yet run out of ideas, just need some more time. Maybe I can get even better results. 
20160227, 08:28  #22 
Jun 2003
Oxford, UK
2^{4}×7×17 Posts 
Thanks mart_r. I'll take these two and see what I can make of them. I'll run them for a week, each over 1 core. If I get less than 5 records then I will let you know.
I would be interested in your methodology and why it produces better results than my efforts. I'm trying to understand the paper on killer sieves, but it is a bit of a wade, as I get confused with symbols  I never was a mathematician. 
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 