mersenneforum.org  

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

Reply
 
Thread Tools
Old 2016-08-24, 14:27   #45
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×1,483 Posts
Default

Quote:
Originally Posted by Antonio View Post
What is the (Log p)^2 merit useful for?
The primary purpose would be showing that the strong form of Cramér's conjecture is false.
CRGreathouse is offline   Reply With Quote
Old 2016-08-24, 19:07   #46
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

599 Posts
Default

Quote:
Originally Posted by henryzz View Post
One question that has been bugging me for a bit is why do we usually divide by a small primorial? When you get to larger numbers the size of the large primorial isn't an issue. Does it affect the distribution of gaps? One thing I noticed with large primorials is that the largest gaps after sieving are a little away from the central point.
What is the best way to chose which primorial to divide by?
It all comes from the coprimes to a large primorial.
Take 997#/2 ± x for instance. In the range x=[0, 2*1000], only powers of 2 are coprime to 997# (i.e. x={2,4,8,16,32,64,128,256,512,1024}, for both sides of the center number, so 20 values in total). However, outside of said range, coprimes to 997# are abundant. For every x=2*p with p>997, 997#/2 ± x is a coprime to 997#. So it is quite easy to find a merit 4-gap there, but hard to find a larger gap. We have 20 coprimes to 997# in a range of 4000 numbers with x<=2000, but 270 coprimes in the range of the same size with 2000<x<=4000.
Dividing 997#/2 by the next small prime 3 leaves more numbers in the range with x<=2000 coprime to 997#, all of those x-values are 3-smooth. The great benefit is that half of the numbers x=2*p outside that merit 4-range get cancelled out, since before dividing by 3 they were equal to either 1 or 2 mod 3.
Dividing yet again by the next small prime 5 leaves 5-smooth values for x in the range x<=2000, but 1/4 of the numbers outside that range get cancelled out.

So basically, it's all a trade-off between the number of d-smooth numbers x in the expression p#/d# ± x and numbers outside the merit 4-range with x>=2*p that can be covered by odd small primes q<=d, since every such small prime q takes care of about 1/(q-1) of the remaining coprimes to p#.

My calculations for the "effective merit" (in some other thread, also with an appropriate PARI program) depend exactly on those coprimes.
mart_r is offline   Reply With Quote
Old 2016-08-25, 06:00   #47
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

599 Posts
Default

Quote:
Originally Posted by mart_r View Post
My calculations for the "effective merit" (in some other thread, also with an appropriate PARI program) depend exactly on those coprimes.
I've just noticed, it's on the very first page of this same thread.
mart_r is offline   Reply With Quote
Old 2016-08-25, 09:13   #48
Antonio
 
Antonio's Avatar
 
"Antonio Key"
Sep 2011
UK

32·59 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
The primary purpose would be showing that the strong form of Cramér's conjecture is false.
Ok so, if I've understood this correctly, we need to raise a flag if the merit we normally use ever exceeds log(p) [i.e. g/log(p) > log(p)].

As all the gaps below p=4e18 have been enumerated we only need to check the gap for Cramér's conjecture if our measure of merit > log(4e18), that is if we ever find a merit > 42.83

Is that right?
Antonio is offline   Reply With Quote
Old 2016-08-25, 16:59   #49
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

For the largest merits, Dr. Nicely already checks this value. If you have output in the "gap merit p1" format, this can be used to flag interesting values:

Code:
perl -nE 'next unless my($g,$m)=/^(\d+)\s+(\S+)/; my $l=$g/$m; my $c=$g/$l**2; print "$c $_" if $c > 0.2;'    file.txt
Even with the low threshold it's unlikely to show much (mine are all for gaps <= length 4404). Values above 0.5 are probably interesting. The only one above 2000 is Spielauer's gap of 2258 (merit 33.87) with a value of 0.508. Above 0.7 seems worthy of comment, but at that point the merit will be high enough to already cause attention.

Note the above script also works on the merits.txt file so you can examine the current values.
danaj is offline   Reply With Quote
Old 2016-08-25, 17:22   #50
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22·1,483 Posts
Default

Quote:
Originally Posted by Antonio View Post
Ok so, if I've understood this correctly, we need to raise a flag if the merit we normally use ever exceeds log(p) [i.e. g/log(p) > log(p)].

As all the gaps below p=4e18 have been enumerated we only need to check the gap for Cramér's conjecture if our measure of merit > log(4e18), that is if we ever find a merit > 42.83

Is that right?
Yes, precisely.

Of course gathering statistics on smaller gaps is also useful!
CRGreathouse is offline   Reply With Quote
Old 2016-08-25, 19:34   #51
Antonio
 
Antonio's Avatar
 
"Antonio Key"
Sep 2011
UK

32·59 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Yes, precisely.

Of course gathering statistics on smaller gaps is also useful!
As a little exercise I plotted all the results credited to myself, and all the results with merit , g/log p, greater than 30 converted to merit g/(log p)^2 the results look quite interesting.
Attached Thumbnails
Click image for larger version

Name:	cramer.png
Views:	107
Size:	44.3 KB
ID:	14815   Click image for larger version

Name:	cramer30plus.png
Views:	98
Size:	21.6 KB
ID:	14816  
Antonio is offline   Reply With Quote
Old 2016-08-25, 20:51   #52
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

2·13·73 Posts
Default

It is interesting. The first graph is more interesting I think. Something to do with size of the smallest prime in a gap and computing capability to find gaps, rather than new maths to replace CSG.

the second graph is just a function of computing power and level of effort. The 30 requirement explains the straight line.

But I am not the maths bod.
robert44444uk is offline   Reply With Quote
Old 2016-08-26, 09:23   #53
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

32×72×13 Posts
Default

Quote:
Originally Posted by mart_r View Post
It all comes from the coprimes to a large primorial.
Take 997#/2 ± x for instance. In the range x=[0, 2*1000], only powers of 2 are coprime to 997# (i.e. x={2,4,8,16,32,64,128,256,512,1024}, for both sides of the center number, so 20 values in total). However, outside of said range, coprimes to 997# are abundant. For every x=2*p with p>997, 997#/2 ± x is a coprime to 997#. So it is quite easy to find a merit 4-gap there, but hard to find a larger gap. We have 20 coprimes to 997# in a range of 4000 numbers with x<=2000, but 270 coprimes in the range of the same size with 2000<x<=4000.
Dividing 997#/2 by the next small prime 3 leaves more numbers in the range with x<=2000 coprime to 997#, all of those x-values are 3-smooth. The great benefit is that half of the numbers x=2*p outside that merit 4-range get cancelled out, since before dividing by 3 they were equal to either 1 or 2 mod 3.
Dividing yet again by the next small prime 5 leaves 5-smooth values for x in the range x<=2000, but 1/4 of the numbers outside that range get cancelled out.

So basically, it's all a trade-off between the number of d-smooth numbers x in the expression p#/d# ± x and numbers outside the merit 4-range with x>=2*p that can be covered by odd small primes q<=d, since every such small prime q takes care of about 1/(q-1) of the remaining coprimes to p#.

My calculations for the "effective merit" (in some other thread, also with an appropriate PARI program) depend exactly on those coprimes.
So increasing d makes reaching 4 merit harder but makes extending beyond that easier.
I understand that it makes less numbers to test past x=2000, however, I don't quite understand why as surely 1/3 of numbers are divisible by 3 anyway.
I assume it is a case of k*997#/6+-x has less numbers to test for x>2000 if gcd(k,3)=1. Need to think some more.
henryzz is offline   Reply With Quote
Old 2016-08-27, 11:51   #54
Antonio
 
Antonio's Avatar
 
"Antonio Key"
Sep 2011
UK

32×59 Posts
Default

Quote:
Originally Posted by Antonio View Post
As a little exercise I plotted all the results credited to myself, and all the results with merit , g/log p, greater than 30 converted to merit g/(log p)^2 the results look quite interesting.
Here is a plot for the Cramér-Shanks-Granville ratio for all gaps in Nicely's current merit.txt file.

Interesting discontinuity at the point where the linear search (up to 4e18 and gaps less than approximately 1346) ends and all other results continue.
Attached Thumbnails
Click image for larger version

Name:	cramer all results.png
Views:	110
Size:	42.4 KB
ID:	14829  

Last fiddled with by Antonio on 2016-08-27 at 12:38
Antonio is offline   Reply With Quote
Old 2016-08-27, 16:51   #55
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22·1,483 Posts
Default

Quote:
Originally Posted by Antonio View Post
Interesting discontinuity at the point where the linear search (up to 4e18 and gaps less than approximately 1346) ends and all other results continue.
Great plot! That suggests that we have a lot more record gaps to find, the best ones are still hidden.
CRGreathouse 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 11:44.

Wed Oct 28 11:44:27 UTC 2020 up 48 days, 8:55, 2 users, load averages: 1.51, 1.78, 1.76

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.