Prime Gap News

[robert44444uk]

Originally Posted by Antonio

A casual inspection of my results indicate that this is almost certainly true. When I started I was more interested in filling in the missing gaps rather than finding record merits. I may well move a core over to record merit searching in a week or two, just to see what happens

After you get 5000 new records, then I think your thirst may be satiated. Then it is a question of how many of those would survive for a while. This is why I won't post smaller than 10 merit, and have set myself up to maximise >20s. These will survive for a long time.

Another one this morning:

>338,000 gap, merit 21.7

[henryzz]

Does getting high merits get harder when you get to larger gaps?

[danaj]

Originally Posted by henryzz

Does getting high merits get harder when you get to larger gaps?

Primalilty tests take longer, so the whole search process takes longer. My searches with 11k digit numbers are very slow.

Empirically in the 100-8000 digit range, the BPSW test is about O(log^2.5(n)). 2x larger size is 5-6x longer time. The larger size also means a longer range for a large merit, which means more tests. Presumably log(n) growth. There is a complicating factor of the partial sieve that has a dynamic log^2(n) depth.

Usually I see the tradeoff as small sizes run faster but are better covered hence need high merits to get a record. Large sizes (200k+) are slow but are so sparse that almost anything you find is a record. The sweet spot this year seems to be in the 70-90k range for efficiency of generating records. There are lots of gaps with merit under 10.

My stats page (http://ntheory.org/gaps/stats.pl) has a section that shows the gaps with merit < 20, < 15, < 10, and no gap. The strike-through values are ones my unsubmitted gap set has found. I usually submit every 3 weeks or so.

[robert44444uk]

I barely have a positive score for this week, looking at the number of my records that Danaj has clawed back
The good news is that the new ones are a better quality - almost everything I am looking for is 150k plus so should last a while.

[henryzz]

So basically the merit isn't a good measure of how hard it is to find them. Maybe we should correct the formula.

[mart_r]

Originally Posted by henryzz

So basically the merit isn't a good measure of how hard it is to find them. Maybe we should correct the formula.

Before I jumped on the bandwagon with the (m*p#)/(d*q#)±x kind of sequences, I wrote a small code that tells me how many candidates there are left to check after a trial division up to p.
This gives sort of an "effective" merit, as displayed in this example:

center number = 2000003# / 13#
           numbers without
          factor <= 2000003  effective merit
           - side  + side    - side  + side
merit ± 1    2550    2527      0.03    0.03
merit ± 2    3218    3199      0.04    0.04
merit ± 3   21172   21119      0.27    0.27
merit ± 4   38603   38594      0.50    0.50
merit ± 5   64610   64486      0.84    0.83
merit ± 6   90082   90090      1.16    1.16
merit ± 7  127014  127067      1.64    1.64
merit ± 8  163654  163684      2.12    2.12
merit ± 9  204374  204397      2.64    2.64
merit ±10  244814  244884      3.17    3.17

Depending on the parameters, you can choose which merit you want to find, then take exp(effective merit) to have a rough estimate of the number of different tests you might need until an example is found.
If e.g. you aim for a merit >10 in this region (± 5), after four attempts there is a >50% chance that an example is found. (I loosely calculate this 50%-chance by using the factor log(2), so exp(0.84+0.83)*log(2) ~ 3.7 attempts)

[danaj]

A little experiment looking at the time and number of merits >= 5.0 found using k*p#/30-b where k=1..10000 without multiples of 2,3,5.

p=20: 1.7s 102 found = 60/s (28-30 digits)

p=40: 4.1s 236 found = 58/s (69-71 digits)

p=80: 19.6s 515 found = 26/s (166-169 digits)

p=160 235s 985 found = 4/s (392-395 digits)

Interestingly with this form the number we find with merit >= 5 goes up as we get larger. But the time taken goes up quite a bit faster. Which would explain why we see the shape of the graph of current records (high at the beginning, dropping off as gap size increases).

As discussed on the other prime gap thread, it's certainly possible that a different method of selecting the search points would be more efficient, and it's also possible to improve the speed of this or other methods vs. doing prev/next prime with my GMP code. For example with numbers larger than ~3000 digits using gwnum would be faster than GMP. gapcoin uses a different method, but it's not obvious to me how to get exact efficiency comparisons.


From Mathworld: "The merit of a prime gap compares the size of a gap to the local average gap [...]" which doesn't take into account computational complexity nor the state of current records.

[robert44444uk]

Originally Posted by henryzz

So basically the merit isn't a good measure of how hard it is to find them. Maybe we should correct the formula.

There are as many gaps as there are primes...so gaps are not hard to find!

Gaps can be arbitrarily long, so a proportionately large gap size is what makes a gap rare and there is a limit to gap size for a given set of two consecutive primes.

Setting higher limits to reporting them, such as a merit of >10 does at least provide some discrimination.

At any size of prime, beyond the 6,30, 210, 2310 rule, in general the larger the gap the rarer it is and the form of number we are searching - near the primorials - does lend itself to larger gaps - however, we are way off getting to a gap merit of 37. I live in hope.

[LaurV]

Originally Posted by robert44444uk

There are as many gaps as there are primes, minus one

Fixed it for you.

Joking apart (or not), the last discussion made me think to analogy with the "difficulty" concept at bitcoin pool-mining, where there is a "bound" for reporting. For example, if you do mining in a pool, the pool will pay you according with your efforts, and the only way it can check how much effort you did is if you report your results which are "better than the bound". So, the pool counts how many results like that are sent by any participant, and they constitute "shares" earned by the participant. The pool gets rewarded (paid) by the bitcoin community when one participant is enough lucky to find a result which is better than the (higher bound) "difficulty" set by the bitcoin community, and in that case the benefit (money) is shared with all participants in the pool according with their "shares".

Next step here is to make a "gapcoin".
The there will be a lot of participants....

[danaj]

Originally Posted by LaurV

Next step here is to make a "gapcoin".

(apologies if I missed the sarcasm/humor tag)

There is such a thing, and it's called gapcoin. Forum / Site. They even have a GPU miner. Over the last year (today is their 1 year anniversary) it has found 1517 record gaps. Antonio has found more than that using a single computer over 3 months. We don't know what resources are being used for Gapcoin. However, Gapcoin is searching for smaller gaps, and has 2 top-20-overall records. The participants also get a coin, where we don't.

You could make an argument that they're looking for higher quality gaps. For people with >100 gaps, average merit:

27.3 Nyman
26.8 Gapcoin
26.2 Spielaur
25.4 Gapcoin unsubmitted
18.7 Jacobsen
18.7 MJPC&JKA
17.9 Jacobsen unsubmitted
17.4 Brent
16.4 TonyKey
15.7 Jansen
15.4 RobSmith
14.9 Rosnthal
14.1 Cami
13.8 Andersen
13.1 TorAlmJA

[LaurV]

It wasn't sarcasm. I use different icons for that
Now I am thinking it was a bit silly for me not to google it before posting, but robert44's talk about "setting higher limits to reporting them" was crying in my brain to a similarity with pool mining, from which it was a very small step to where the name struck. Now, it seems just normal that someone else was thinking to it before me... Tragedy of my life...

OTOH, I like their page (the one you linked). Good and elementary explanations for both the coining system and prime gaps' math, for everybody to understand. As an "old salt" bitcoin folk, I will give their GPU miner a try during this long weekend we will have here (23rd is national holiday). To see how fast it is. I have no real feeling (beside of this thread) what the numbers you posted really mean, in term of effort. Seeing you on the list, it may be not easy to get some coins ...

Edit2: "there is no pool mining at present". Time to make one?