mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2016-01-08, 08:57   #1
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

2·953 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
Old 2016-01-08, 12:34   #2
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

136038 Posts
Default

Sounds like a problem that could be solved more quickly on a GPU.
rogue is online now   Reply With Quote
Old 2016-01-08, 16:38   #3
axn
 
axn's Avatar
 
Jun 2003

478110 Posts
Default

Quote:
Originally Posted by robert44444uk View Post
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.
axn is offline   Reply With Quote
Old 2016-01-09, 11:06   #4
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

77216 Posts
Default

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

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
robert44444uk is offline   Reply With Quote
Old 2016-02-24, 14:50   #5
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

190610 Posts
Default

Quote:
Originally Posted by robert44444uk View Post
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?
robert44444uk is offline   Reply With Quote
Old 2016-02-24, 16:52   #6
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

10011000002 Posts
Default

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.
mart_r is offline   Reply With Quote
Old 2016-03-02, 17:52   #7
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

25·19 Posts
Default

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
mart_r is offline   Reply With Quote
Old 2016-03-03, 10:30   #8
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

35628 Posts
Default

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.
robert44444uk is offline   Reply With Quote
Old 2016-03-03, 19:08   #9
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

25·19 Posts
Default

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.
mart_r is offline   Reply With Quote
Old 2016-04-04, 17:35   #10
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

111011100102 Posts
Default

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
robert44444uk is offline   Reply With Quote
Old 2016-04-04, 18:34   #11
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

2·953 Posts
Default

...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
robert44444uk is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Covering sets for a^n-1 carpetpool Abstract Algebra & Algebraic Number Theory 1 2017-12-28 12:48
sets of 3 primes MattcAnderson Miscellaneous Math 3 2017-10-18 00:24
Polynomial Coefficients Integer Sets carpetpool carpetpool 1 2017-02-22 08:37
Does 2^n-n-2 have a covering set? Stargate38 And now for something completely different 13 2017-01-21 11:52
Julia Sets mfgoode Miscellaneous Math 2 2006-04-04 00:18

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

Mon Nov 30 18:10:46 UTC 2020 up 81 days, 15:21, 3 users, load averages: 2.38, 2.94, 2.60

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.