Thread: Covering sets
View Single Post
Old 2016-01-08, 08:57   #1
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

2·7·137 Posts
Default 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!
robert44444uk is offline   Reply With Quote