mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Computer Science & Computational Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=116)

 robert44444uk 2016-01-08 08:57

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!

 rogue 2016-01-08 12:34

Sounds like a problem that could be solved more quickly on a GPU.

 axn 2016-01-08 16:38

[QUOTE=robert44444uk;421543]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
[/QUOTE]

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.

 robert44444uk 2016-01-09 11:06

[QUOTE=axn;421566]
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?)
.[/QUOTE]

You are right, I had transposed my results line incorrectly.

[QUOTE=axn;421566]

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

[/QUOTE]

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.

 robert44444uk 2016-02-24 14:50

[QUOTE=robert44444uk;421543]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.

[/QUOTE]

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[/code]

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?

 mart_r 2016-02-24 16:52

The Jacobsthal function applied to the product of the first n primes (see OEIS sequence A048670: [URL]http://oeis.org/search?q=A048670&sort=&language=english&go=Search[/URL]) 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.

 mart_r 2016-03-02 17:52

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
[/CODE]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
[/CODE]

 robert44444uk 2016-03-03 10:30

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.

 mart_r 2016-03-03 19:08

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.:smile:

 robert44444uk 2016-04-04 17:35

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]

 robert44444uk 2016-04-04 18:34

...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]

All times are UTC. The time now is 16:10.