20210106, 20:47  #122 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·41·71 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?

20210107, 01:39  #123  
"Seth"
Apr 2019
2^{2}·3^{2}·7 Posts 
Quote:
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 postfacto analysis over some run with nosideskip. for 2) I wrote a bit about this at https://github.com/sethtroisi/prime...nesidedtests 

20210107, 10:40  #124  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·41·71 Posts 
Quote:


20210108, 05:47  #125  
"Seth"
Apr 2019
2^{2}·3^{2}·7 Posts 
Quote:
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 515% 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). 

20210123, 23:54  #126 
May 2018
2^{4}·13 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.

20210127, 09:06  #127  
"Seth"
Apr 2019
2^{2}×3^{2}×7 Posts 
Quote:
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. 

20210202, 13:01  #128 
Jan 2018
41 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 20210202 at 13:08 
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 