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

 2021-01-06, 20:47 #122 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 10110110111012 Posts What is the logic behind searching one side before the other? Wouldn't it be better to test the denser central region first(assuming a primorial divisor) as it will probably be needed for a record?
2021-01-07, 01:39   #123
SethTro

"Seth"
Apr 2019

3·89 Posts

Quote:
 Originally Posted by henryzz What is the logic behind searching one side before the other? Wouldn't it be better to test the denser central region first(assuming a primorial divisor) as it will probably be needed for a record?
Not sure I quite understand the question. Is it
1) Why do I always search downwards before upwards?
2) Why do I give up after one search?

1) I don't think it matters which direction you search or if you search the denser / less dense side first.

It's possible there's some better out of order search scheme that alternates testing values on each side and from different points in the sieve but let's ignore that and focus on searching one side till we find the closest prime in that direction; Note this always takes the same expected number of PRP tests minus the small < 0.5% chance that we exceed the sieve length.

My mental justification was: If one side is twice as dense and we search that side first; the expected value is nearer but the sparseness on the other side makes it still likely to find a record. If we search the sparse side first then we get a larger value but the other side is denser so it's similar.

Let me know if this doesn't pass a smell test and we can try to validate by running a post-facto analysis over some run with --no-side-skip.

2021-01-07, 10:40   #124
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

16DD16 Posts

Quote:
 Originally Posted by SethTro Not sure I quite understand the question. Is it 1) Why do I always search downwards before upwards? 2) Why do I give up after one search? 1) I don't think it matters which direction you search or if you search the denser / less dense side first. It's possible there's some better out of order search scheme that alternates testing values on each side and from different points in the sieve but let's ignore that and focus on searching one side till we find the closest prime in that direction; Note this always takes the same expected number of PRP tests minus the small < 0.5% chance that we exceed the sieve length. My mental justification was: If one side is twice as dense and we search that side first; the expected value is nearer but the sparseness on the other side makes it still likely to find a record. If we search the sparse side first then we get a larger value but the other side is denser so it's similar. Let me know if this doesn't pass a smell test and we can try to validate by running a post-facto analysis over some run with --no-side-skip. for 2) I wrote a bit about this at https://github.com/sethtroisi/prime-...ne-sided-tests
To some extent I think it makes sense to try and find one of the end points as that allows for an early skip(as that is done 90% of the time now). I wonder whether skips could be done faster/more frequently/more accurately if a small portion of the other side is also tested early(before aiming for finding an end point). Record gaps very rarely have 90%(optimal figure to be determined based on the records list) on one side so 10% should be tested early on both sides.

2021-01-08, 05:47   #125
SethTro

"Seth"
Apr 2019

4138 Posts

Quote:
 Originally Posted by henryzz To some extent I think it makes sense to try and find one of the end points as that allows for an early skip(as that is done 90% of the time now). I wonder whether skips could be done faster/more frequently/more accurately if a small portion of the other side is also tested early(before aiming for finding an end point). Record gaps very rarely have 90%(optimal figure to be determined based on the records list) on one side so 10% should be tested early on both sides.
I've been pondering this for a while and you've changed my mind I should be testing the least dense portion of the interval.

I plotted some examples and it appears that if d the divisor has few divisors (1, 2, 3) the center is clearly less dense but as d has more divisors (6,30,210) it's not clear how much this helps.

I'm not sure how to measure the improvement but I'd guess this would give another 5-15% improvement but would take some reasonable amount of code. I've recorded it in the low priority TODOs but I'm unlikely to write this soon (happy to help anyone interested in coding it up).
Attached Thumbnails

 2021-01-23, 23:54 #126 Bobby Jacobs     May 2018 22·53 Posts When d=6, the coprimes are 1 and 5, so the center is not very dense. When d=30, the coprimes are 1, 7, 11, 13, 17, 19, 23, 29, so the center is dense. When d=210, the coprimes are 1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209, so the center is very dense.
2021-01-27, 09:06   #127
SethTro

"Seth"
Apr 2019

3·89 Posts

Quote:
 Originally Posted by Bobby Jacobs When d=6, the coprimes are 1 and 5, so the center is not very dense. When d=30, the coprimes are 1, 7, 11, 13, 17, 19, 23, 29, so the center is dense. When d=210, the coprimes are 1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209, so the center is very dense.

coprimes hides a lie with d=210 for any given m half of the coprimes will be divisible by 2, 1/3 by 3 and 1/5 by 5 so the center is still not very dense.

 2021-02-02, 13:01 #128 MJansen   Jan 2018 43 Posts Hi Seth and Bobby, when you plot the remaining candidates of a primorial value divided by 6, 30, 210, 2310 etc. you will find the remaining candidates with divider 6 are few close to the primorial center value but many a little distance from the center. The larger the divider, the more spread out the candidates are. So in a nutshell: The larger the divider, the fewer there are candidates around the center. But since the remaining candidates (say with divider 30030), are stronger candidates, chance is you will mostly find smaller gaps with the occasional find of a larger gap. There has been a post somewhere/somewhen that had a very nice graphic representation of that observation. You can easily check this yourself by writing a simple script that for instance prints the remaining candidates in an interval p(100)#/D +/- 10*P(100). after deleting all candidates that divide by the factors of the divider D. So D = 30030 has factors 2, 3, 5, 7, 11, 13 --> remove all candidates that can be divided by one (or more) of these factors So D = 30 had factors 2, 3, 5 --> remove all candidates that can be divided by one (or more) of these factors Compare the distribution of the candidates and you will see the pattern emerge, as I described above. Hope this is clear Michiel Last fiddled with by MJansen on 2021-02-02 at 13:08

 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 03:18.

Mon Apr 12 03:18:16 UTC 2021 up 3 days, 21:59, 1 user, load averages: 1.45, 1.75, 1.76