mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Prime Gap Searches

Reply
 
Thread Tools
Old 2021-01-06, 20:47   #122
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×2,909 Posts
Default

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?
henryzz is offline   Reply With Quote
Old 2021-01-07, 01:39   #123
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

3738 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.

for 2) I wrote a bit about this at https://github.com/sethtroisi/prime-...ne-sided-tests
SethTro is offline   Reply With Quote
Old 2021-01-07, 10:40   #124
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·2,909 Posts
Default

Quote:
Originally Posted by SethTro View Post
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.
henryzz is offline   Reply With Quote
Old 2021-01-08, 05:47   #125
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

25110 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
Click image for larger version

Name:	d=6.png
Views:	36
Size:	45.1 KB
ID:	24136   Click image for larger version

Name:	d=30.png
Views:	34
Size:	48.9 KB
ID:	24137  
SethTro is offline   Reply With Quote
Old 2021-01-23, 23:54   #126
Bobby Jacobs
 
Bobby Jacobs's Avatar
 
May 2018

32×23 Posts
Default

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.
Bobby Jacobs is offline   Reply With Quote
Old 2021-01-27, 09:06   #127
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

FB16 Posts
Default

Quote:
Originally Posted by Bobby Jacobs View Post
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.
SethTro is offline   Reply With Quote
Old 2021-02-02, 13:01   #128
MJansen
 
Jan 2018

1010012 Posts
Default

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
MJansen is offline   Reply With Quote
Reply

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 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

All times are UTC. The time now is 10:50.

Sun Feb 28 10:50:08 UTC 2021 up 87 days, 7:01, 0 users, load averages: 1.42, 1.04, 1.03

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.