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) 25×5×37 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

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

134408 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

16F16 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 233 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

367 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 61 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
 2021-08-01, 13:40 #129 mart_r     Dec 2008 you know...around... 68010 Posts I'd like to ask if anybody could confirm or refute the following, or whether I'm just misunderstanding something: I do not believe that the upper bound of (1.12) in 1908.08613 (Banks-Ford-Tao: Large prime gaps and probabilistic models) is quite correct. Setting ap = 0 mod p for all primes p <= $$(\frac{y}{\log y})^{1/2}$$, the error bound on the right-hand side of the equation should be larger than $$O(\frac{y \log_2 y}{\log^2y})$$. We do not only have the primes in the interval (0, y) to account for (given indeed by $$\frac{y}{\log y}+O(\frac{y \log_2 y}{log^2y})$$), but also the semiprimes <= y with factors larger than $$(\frac{y}{\log y})^{1/2}$$. These semiprimes invalidate the error bound in the given form, in the sense that their number exceeds $$O(\frac{y}{\log^2y})$$ and is rather $$O(\frac{y}{\log y})$$, possibly $$O(\frac{y}{\log^{3/2}y})$$.
 2021-08-01, 15:12 #130 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 25·5·37 Posts Are you aware of the blog post for this paper? You could try asking a question there(the author might have notifications for new comments). https://terrytao.wordpress.com/2019/...listic-models/
2021-08-01, 15:39   #131
mart_r

Dec 2008
you know...around...

12508 Posts

Quote:
 Originally Posted by henryzz Are you aware of the blog post for this paper?
Not until now. It looks quite intriguing - thanks for pointing me to it.

2021-08-02, 13:27   #132
robert44444uk

Jun 2003
Oxford, UK

19·103 Posts

Quote:
 Originally Posted by SethTro 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).
Certainly testing the centre around the deficient primorial was the method of choice before Seth's code. Danaj developed a "surround_primes" function in Perl to enable the methodology.

Math::Prime::Util::GMP::surround_primes($x,$y,\$z);

See: https://github.com/danaj/Math-Prime-...ter/gmp_main.c

 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 11:35.

Sat Oct 23 11:35:35 UTC 2021 up 92 days, 6:04, 0 users, load averages: 0.91, 0.89, 0.96