mersenneforum.org Covering sets
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2016-01-08, 08:57 #1 robert44444uk     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!
 2016-01-08, 12:34 #2 rogue     "Mark" Apr 2003 Between here and the 22·7·13·17 Posts Sounds like a problem that could be solved more quickly on a GPU.
2016-01-08, 16:38   #3
axn

Jun 2003

37×131 Posts

Quote:
 Originally Posted by robert44444uk 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
These 8 solutions are not unique. They represent one "family" of solution.

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.

2016-01-09, 11:06   #4
robert44444uk

Jun 2003
Oxford, UK

2·7·137 Posts

Quote:
 Originally Posted by axn 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?) .
You are right, I had transposed my results line incorrectly.

Quote:
 Originally Posted by axn 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
Nice observations! A great way to explain the outcome, and maybe this is food for thought in designing a slightly more sophisticated approach to finding the minimum for 2310. I have to think why 7 can only hit 2 gaps in the 30 range, i.e. smaller primes can always hit 2 out of the 4 in the range where 7 is a factor.

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 2016-01-09 at 11:07

2016-02-24, 14:50   #5
robert44444uk

Jun 2003
Oxford, UK

77E16 Posts

Quote:
 Originally Posted by robert44444uk 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 have been exploring this a bit.

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
This is almost certainly not the smallest range of 2310 where all integers are composite and all have factors of 739 or smaller.

Can anyone do better?

 2016-02-24, 16:52 #6 mart_r     Dec 2008 you know...around... 2·311 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.
 2016-03-02, 17:52 #7 mart_r     Dec 2008 you know...around... 2×311 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 On the downside, none of the differences between all these numbers divide a prime > 577, so it takes one more prime for every open residue to cover the whole set. 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 2310-range at 653#. One of those possibilities is given by the offset number Code: 84014187931330891982928862151585423133277701808931254622654423525808390988632742949399274570817791940040095608793771771564891142528915498180659440098040141622958738285319473714869936965247261697018313728314093388024245806686921131025648923863267854404228281265796338542408 Last fiddled with by mart_r on 2016-03-02 at 18:37 Reason: typo
 2016-03-03, 10:30 #8 robert44444uk     Jun 2003 Oxford, UK 77E16 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.
 2016-03-03, 19:08 #9 mart_r     Dec 2008 you know...around... 10011011102 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.
 2016-04-04, 17:35 #10 robert44444uk     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 2016-04-04 at 17:37
 2016-04-04, 18:34 #11 robert44444uk     Jun 2003 Oxford, UK 2×7×137 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 2016-04-04 at 18:41

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Abstract Algebra & Algebraic Number Theory 1 2017-12-28 12:48 MattcAnderson Miscellaneous Math 3 2017-10-18 00:24 carpetpool carpetpool 1 2017-02-22 08:37 Stargate38 And now for something completely different 13 2017-01-21 11:52 mfgoode Miscellaneous Math 2 2006-04-04 00:18

All times are UTC. The time now is 03:28.

Tue Jan 26 03:28:03 UTC 2021 up 53 days, 23:39, 0 users, load averages: 1.40, 1.64, 1.64