mersenneforum.org  

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

Reply
 
Thread Tools
Old 2015-10-16, 07:33   #34
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

35768 Posts
Default

Quote:
Originally Posted by Antonio View Post
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
robert44444uk is offline   Reply With Quote
Old 2015-10-20, 11:50   #35
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

579510 Posts
Default

Does getting high merits get harder when you get to larger gaps?
henryzz is offline   Reply With Quote
Old 2015-10-20, 16:06   #36
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

90610 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
danaj is offline   Reply With Quote
Old 2015-10-20, 17:50   #37
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

2×7×137 Posts
Default

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.

Last fiddled with by robert44444uk on 2015-10-20 at 17:51
robert44444uk is offline   Reply With Quote
Old 2015-10-20, 21:07   #38
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

5×19×61 Posts
Default

So basically the merit isn't a good measure of how hard it is to find them. Maybe we should correct the formula.
henryzz is offline   Reply With Quote
Old 2015-10-20, 21:52   #39
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

11568 Posts
Default

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

Code:
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)
mart_r is offline   Reply With Quote
Old 2015-10-20, 22:39   #40
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2015-10-21, 07:02   #41
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

191810 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
robert44444uk is offline   Reply With Quote
Old 2015-10-21, 07:58   #42
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24·3·191 Posts
Default

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

Last fiddled with by LaurV on 2015-10-21 at 08:02
LaurV is online now   Reply With Quote
Old 2015-10-21, 16:01   #43
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

16128 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
danaj is offline   Reply With Quote
Old 2015-10-22, 02:29   #44
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24×3×191 Posts
Default

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?

Last fiddled with by LaurV on 2015-10-22 at 02:42
LaurV is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
News gd_barnes Conjectures 'R Us 298 2021-01-07 09:06
News gd_barnes No Prime Left Behind 250 2020-06-29 13:23
P!=NP in the news willmore Computer Science & Computational Number Theory 48 2010-09-19 08:30
The news giveth, the news taketh away... NBtarheel_33 Hardware 17 2009-05-04 15:52
Some news about Home Prime ? MoZ Factoring 6 2006-02-28 12:02

All times are UTC. The time now is 11:13.

Wed Jan 27 11:13:19 UTC 2021 up 55 days, 7:24, 0 users, load averages: 4.91, 5.02, 5.15

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.