20160108, 08:57  #1 
Jun 2003
Oxford, UK
2·7·137 Posts 
Covering sets
I'm wondering if the following is known, and if not, how to compute this quickly:
The minimum number of primes that are needed in a covering set that provide factors for every member of a integer range of 2310. I would hypothesise that the primes in such a minimum member set are consecutive and, more, that the primes are of the sequence 2,3,5,7,....p I have, by brute force, calculated for an integer range of 30 that there are eight combinations of the 8 primes 2,3,5,7,11,13,17,19 that produce covering sets, with the following modular relationships demonstrated by the first of the integer range: 1mod2, 1mode3, 3mod5, 4mod7, 5mod11, 9mod13, 1mod17, 1mod19 0,2,4,5,6,10,2,2 1,0,0,6,7,11,3,3 0,2,3,4,5,9,16,3 0,2,4,5,6,10,0,4 0,1,1,0,8,12,4,4 1,0,0,6,7,11,1,5 0,1,1,0,8,12,2,6 I would imagine 8 is therefore the minimum, under the hypothesis. I have gone some way to looking for the smallest covering set for the integer range 210  for example, the primes 2...23 provide, at best, 24 "holes" in the cover (there are two such modular combinations), and hence trivially the next 24 primes after 23 will provide cover. This is highly unlikely to be the smallest number. But the time allocated for the search is already quite long, finding this result took me 130 minutes on one core to cover all 23# permutations. Clearly this would be difficult using my current methodology to solve this for 210, let along 2310 and hence this message to the Mersenneforum! 
20160108, 12:34  #2 
"Mark"
Apr 2003
Between here and the
2^{2}×23×67 Posts 
Sounds like a problem that could be solved more quickly on a GPU.

20160108, 16:38  #3  
Jun 2003
1001011101010_{2} Posts 
Quote:
These are the 8 solutions paired up 1,1,3,4,5,9 ,1,1 : 1,1,3,4,5,9,16,3 (you had it as 0,2,3,4,5,9,16,3. is that correct?) 0,2,4,5,6,10,2,2 : 0,2,4,5,6,10,0,4 1,0,0,6,7,11,3,3 : 1,0,0,6,7,11,1,5 0,1,1,0,8,12,4,4 : 0,1,1,0,8,12,2,61 All the lines differ from the next one by 1. i.e. They just represent shifting the starting point by 1. And within a pair, the first five modular classes are same  i.e these are primes that hit more than one point in the 30. 2,3, and 5 together eliminate 22 out of every 30 consecutive numbers (always). Of the remaining 8, the best we can do is to hit 2 each with 7,11, and 13. That leaves 2 points. Any prime > 15 can only hit at most 1 point. Therefore the last two requires two primes (any two primes > 15), which yields a family of solutions. 

20160109, 11:06  #4  
Jun 2003
Oxford, UK
2×7×137 Posts 
Quote:
Quote:
Also this disproves the hypothesis I put forward, as written. I wonder though, for a range where the total number of range members is > p#, then if 2,3,5...p have to be members of all minimum covering sets. Last fiddled with by robert44444uk on 20160109 at 11:07 

20160224, 14:50  #5  
Jun 2003
Oxford, UK
1918_{10} Posts 
Quote:
The primes to 739 produce a covering set over an integer range of 2310, as provided with the following range  (given as a pfgw file) Code:
ABC2 739#851000256349765889295008041950222651166966896546372185059613326227806525122640671296401722521283286251647678570118376450038403980595559317197227223782617485823807110377855506648118651780073056285228902161980363975551530425485856513116025177545445198982939525456348688416730243149519392436370957298448398900$a a: from 0 to 2309 Can anyone do better? 

20160224, 16:52  #6 
Dec 2008
you know...around...
2^{2}·5·31 Posts 
The Jacobsthal function applied to the product of the first n primes (see OEIS sequence A048670: http://oeis.org/search?q=A048670&sor...lish&go=Search) provides an answer for ranges up to 742. For example, to get a range of 210 covered it takes 23 primes (i.e. up to 83).
The assumption that a covering set consists only of the primes in consecutive order has also proven to be false. 
20160302, 17:52  #7 
Dec 2008
you know...around...
1154_{8} Posts 
I've run some samples at 577#, and after a few residue sets that left 16 numbers coprime to 577#, I was lucky to get one that left only 13 coprimes:
Code:
k=57038838199945595943092978020969218682105458339028727587781701358714381875907979834149194637905736734686560196824691232279743998298569591278748933757883925287649006675231123018149656337436046099711266218991008707108800654609166747134268 coprimes to 577# in range [k, k+2310] for k+x, x= 425 521 665 695 701 733 743 793 833 859 941 1393 1769 Thus, proceeding at this point, and taking into account the mirror image pattern, there are 12,454,041,600 possibilities in total to cover a whole 2310range at 653#. One of those possibilities is given by the offset number Code:
84014187931330891982928862151585423133277701808931254622654423525808390988632742949399274570817791940040095608793771771564891142528915498180659440098040141622958738285319473714869936965247261697018313728314093388024245806686921131025648923863267854404228281265796338542408 Last fiddled with by mart_r on 20160302 at 18:37 Reason: typo 
20160303, 10:30  #8 
Jun 2003
Oxford, UK
2·7·137 Posts 
Wow, thats a very large pick up from my simple algorithm!
The 13 remaining at 577 is a fabulous result all by itself. I reckon if you ran your algorithm a bit more, it might get a slightly superior result which might lead to a lower clearance number. 
20160303, 19:08  #9 
Dec 2008
you know...around...
1154_{8} Posts 
Well, looking at all the 16s and one 15  beside that record of 13  I got in those about two hours, I probably could find a 12 in two or three days of calculation time, which would be very little improvement compared to the effort. Looking at my limited resources, I'd rather leave that task for real experts.

20160404, 17:35  #10 
Jun 2003
Oxford, UK
2·7·137 Posts 
A slightly superior result using a different algorithm, found in 80 minutes on one core. The following [mod,prime] combination, when translated with the Chines Remainder Theorem leaves just one gap at 641#, which can be covered with 647, and hence is superior to mart_r's 653#
[0,2],[0,3],[0,5],[0,7],[2,11],[12,13],[8,67],[18,37],[3,23],[87,107],[22,43],[8,29],[15,31],[44,47],[49,61],[9,19],[15,17],[62,71],[170,181],[3,41],[41,53],[87,89],[48,83],[14,59],[57,227],[198,211],[35,109],[20,73],[26,103],[167,199],[57,101],[80,193],[52,97],[80,163],[67,157],[94,149],[27,79],[76,137],[71,127],[65,113],[170,349],[228,331],[18,317],[242,313],[114,311],[15,283],[95,281],[27,277],[170,271],[214,269],[47,263],[78,251],[54,241],[101,239],[10,233],[80,229],[20,223],[49,197],[95,191],[129,179],[123,173],[164,167],[12,151],[9,139],[93,131],[430,641],[356,619],[279,613],[98,607],[178,599],[513,593],[184,587],[267,577],[220,569],[135,563],[357,547],[200,523],[255,521],[238,509],[279,503],[189,499],[171,491],[165,479],[105,467],[3,463],[154,461],[184,457],[134,449],[296,443],[147,439],[105,433],[273,431],[136,409],[362,401],[195,389],[338,379],[322,373],[177,359],[276,337],[14,631],[33,617],[44,601],[21,571],[3,557],[13,541],[0,487],[69,421],[88,419],[99,397],[136,383],[140,367],[132,353],[122,347],[28,307],[256,293],[234,257] Last fiddled with by robert44444uk on 20160404 at 17:37 
20160404, 18:34  #11 
Jun 2003
Oxford, UK
77E_{16} Posts 
...and this produces 1 left with one fewer prime, so full cover at 641#. The cover is provided by the following CRT problem, and the prime 229. Actually there are many, many solutions given that the last 17 primes on this list only contribute to eliminating 1 integer in the sequence, each.
[0,2],[0,3],[0,5],[0,7],[4,11],[5,13],[10,23],[0,31],[49,61],[15,17],[4,83],[22,43],[21,29],[39,103],[14,59],[13,37],[5,41],[36,67],[3,19],[29,47],[29,71],[62,151],[9,53],[68,149],[99,139],[4,131],[32,127],[64,79],[42,113],[30,73],[8,109],[45,107],[3,101],[40,197],[170,193],[20,89],[83,181],[85,163],[81,157],[100,137],[332,373],[222,353],[130,311],[170,307],[30,97],[102,293],[198,281],[225,269],[146,251],[136,241],[171,233],[139,227],[93,223],[107,211],[90,199],[79,191],[43,179],[109,173],[142,167],[220,641],[32,631],[507,619],[250,617],[80,613],[135,607],[261,601],[238,599],[291,587],[483,571],[70,569],[460,563],[44,547],[122,541],[56,523],[16,509],[489,499],[214,491],[38,487],[165,479],[212,467],[142,463],[21,461],[218,457],[314,449],[222,443],[296,439],[322,433],[201,431],[170,421],[136,409],[217,401],[87,389],[206,383],[121,367],[219,349],[302,347],[2,277],[93,239],[22,593],[10,577],[150,557],[64,521],[83,503],[29,419],[4,397],[14,379],[19,359],[17,337],[116,331],[69,317],[142,313],[48,283],[34,271],[246,263],[246,257] Last fiddled with by robert44444uk on 20160404 at 18:41 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Covering sets for a^n1  carpetpool  Abstract Algebra & Algebraic Number Theory  1  20171228 12:48 
sets of 3 primes  MattcAnderson  Miscellaneous Math  3  20171018 00:24 
Polynomial Coefficients Integer Sets  carpetpool  carpetpool  1  20170222 08:37 
Does 2^nn2 have a covering set?  Stargate38  And now for something completely different  13  20170121 11:52 
Julia Sets  mfgoode  Miscellaneous Math  2  20060404 00:18 