Prime Gap Theory - Page 2

science_man_88 · 2016-02-10, 21:39

Quote:

Originally Posted by mart_r

@ sm88: You surely are concerned about my program :)
I've changed a few things today and thereby made it quite a bit faster, especially "l=log(r)/4" outside the output loop helped a lot.

Also, fixed the main concern about odd inputs of d.

Apart from some cosmetics (maybe addhelp sometime later...), how's it now?

I keep on forgetting to save copies I make one of mine took at very least the second one ( maybe even the original) down from around 46 s to under 39 seconds for merit(2000000,5,2,3) for me. that I've been testing with log(r) still might be sped up with a variable declaration like

Code:

 g=log(r)

so that it only gets calculated once I was able to merge the forstep into one with a few variable declarations and merge a and b into one for the add in the final thing for c I realized prod may actually slow it in some cases. thinks like !m can be changed to to

Code:

if(m,,...)

and that may speed it up also only declaring the change to m right before using so we know it will be used. since factor has a limit possibility if that's backward compatible maybe only factor to p and check

Code:

p<e[#e[,1],1]

first then continue with the i check potentially with if statements to shorten the loop in some cases. I just want you to be able to get good performance out of it. you do two divisions c/w/log(r) this without parentheses is like

Code:

c/(w*log(r))

and multiplication will likely be faster.

Code:

t=(t+q*(t%2))/2;
                if(!t,t=q);

could be changed into

Code:

if(t,t=(t+q*(t%2))/2,t=q)

because if t is 0 the expression you do before the if will not change that so it is just over declared for what is needed especially if you are going to check it to begin with. oh and your declaration of l could be right after r and help define z potentially also the 1 being in the floor call is pointless because floor(x) = x-frac(x) and the 1 is not in the fractional part. oh and if you do stick with prod at least in later editions you can use

Code:

r=prod(r=1,primepi(p),prime(r),m/d);

oh and for people wondering I'm not an optimist so I can always find something bad in something ( unless it's my own creation at times), offtopic:part of why I haven't got a job I can never convince myself my skills are worth having. but back to the theory about primes and gaps for all primes >3 the gaps need to be even but the log of pn is not guaranteed to be even at last check so that may be what is getting confused.

danaj · 2016-02-17, 06:07

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
6-8% each in classes 1, 7, 11, 13, 17, 19, 23, 29
3-4% 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
4-6% 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 co-prime selection isn't a bad choice, but adding 5 and 25 wouldn't hurt. Either are more efficient than all-odds.

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 co-prime 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 co-prime 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 10-of-30 list is better for /30 and /6 and some other divisors.

Antonio · 2016-02-18, 07:29

Quote:

Originally Posted by danaj

None of the following is a surprise, but I ran some experiments and thought the results were interesting enough to post.

Interesting indeed.
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 co-prime multipliers is correct.

robert44444uk · 2016-02-23, 13:47

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 initial set of primes which would provide the same efficiency,
a range of p where the greedy algorithm provides greater efficiency,
a third range where the reference set becomes again more efficient,
and a fourth range where the algorthm provides accelerating efficiency.
A fifth range, is not shown, where the p is greater than the sqrt(60060), where the reference set is massively inefficient.

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.

mart_r · 2016-02-23, 21:53

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 (p-1)#, 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.

robert44444uk · 2016-02-24, 08:01

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.

robert44444uk · 2016-02-24, 14:53

I posted this on

http://www.mersenneforum.org/showthr...271#post427271

For the range of 2310. This was calcuated using the simple greedy algorithm.

mart_r · 2016-02-24, 16:25

Quote:

Originally Posted by robert44444uk

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.

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.

robert44444uk · 2016-02-25, 08:50

Quote:

Originally Posted by mart_r

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.

.

Wow, can't wait.

mart_r · 2016-02-26, 21:55

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

The statistics:

Code:

         remaining #s  effective merit
average:         4491  34.75
my first sieve:  3126  24.19
my new sieve:    2950  22.82  <---
1777#/210-30030: 2815  21.78

Which is better than I expected.

I've not yet run out of ideas, just need some more time. Maybe I can get even better results.

robert44444uk · 2016-02-27, 08:28

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.

2016-02-23, 13:47	#15
robert44444uk Jun 2003 Oxford, UK 2²×3×7×23 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 initial set of primes which would provide the same efficiency, a range of p where the greedy algorithm provides greater efficiency, a third range where the reference set becomes again more efficient, and a fourth range where the algorthm provides accelerating efficiency. A fifth range, is not shown, where the p is greater than the sqrt(60060), where the reference set is massively inefficient. 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. Attached Thumbnails Last fiddled with by robert44444uk on 2016-02-23 at 14:23

2016-02-23, 21:53	#16
mart_r Dec 2008 you know...around... 2×11×29 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 (p-1)#, 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 2016-02-23 at 22:02

2016-02-24, 08:01	#17
robert44444uk Jun 2003 Oxford, UK 78C₁₆ 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 2016-02-24 at 08:06

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	2016-10-14 19:38
Before you post your new theory about prime, remember	firejuggler	Math	0	2016-07-11 23:09
Mersene Prime and Number Theory	Ricie	Miscellaneous Math	24	2009-08-14 15:31
online tutoring in prime number theory	jasong	Math	3	2005-05-15 04:01
Prime Theory	clowns789	Miscellaneous Math	5	2004-01-08 17:09

2016-02-17, 06:07	#13
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 2²·227 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 kn#/6 or /30. Other divisors may have different results. I ran a simple experiment looking at kn#/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 6-8% each in classes 1, 7, 11, 13, 17, 19, 23, 29 3-4% 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, kn#/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 4-6% 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 kn#/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 co-prime selection isn't a bad choice, but adding 5 and 25 wouldn't hurt. Either are more efficient than all-odds. 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 co-prime 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 co-prime 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 10-of-30 list is better for /30 and /6 and some other divisors.

2016-02-24, 14:53	#18
robert44444uk Jun 2003 Oxford, UK 2²·3·7·23 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.

2016-02-27, 08:28	#22
robert44444uk Jun 2003 Oxford, UK 2²×3×7×23 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.