Täckningsset
I matematik hänvisar en täckande uppsättning för en sekvens av heltal till en uppsättning primtal så att varje term i sekvensen är delbar med minst en medlem av mängden . Termen "täckande uppsättning" används endast i samband med sekvenser som har exponentiell tillväxt .
Sierpinski och Riesel nummer
Användningen av termen "täckningsset" är relaterad till Sierpinski- och Riesel-nummer . Dessa är udda naturliga tal k för vilka formeln k 2 n + 1 (Sierpinski-tal) eller k 2 n − 1 (Rieseltal) inte ger några primtal. Sedan 1960 har det varit känt att det finns ett oändligt antal både Sierpinski- och Riesel-tal (som lösningar på familjer av kongruenser baserade på mängden { 3, 5, 17, 257, 641, 65537, 6700417 } men eftersom det finns en oändlighet av tal av formen k 2 n + 1 eller k 2 n − 1 för vilken k som helst kan man bara bevisa att k är ett Sierpinski- eller Rieseltal genom att visa att varje term i sekvensen k 2 n + 1 eller k 2 n − 1 är delbart med ett av primtalen i en täckande uppsättning.
Dessa täckande mängder bildas från primtal som i bas 2 har korta perioder. För att uppnå en komplett täckande uppsättning Wacław Sierpiński att en sekvens inte kan upprepas oftare än vart 24:e nummer. En upprepning var 24:e siffra ger täckningssetet {3, 5, 7, 13, 17, 241 }, medan en upprepning var 36:e term kan ge flera täckningsset: {3, 5, 7, 13, 19, 37, 73 } ; {3, 5, 7, 13, 19, 37, 109} ; {3, 5, 7, 13, 19, 73, 109 } och {3, 5, 7, 13, 37, 73, 109 }.
Rieselnummer har samma täckande set som Sierpinski-nummer.
Andra täckningsset
Täckande set (alltså Sierpinski-tal och Riesel-nummer) finns även för andra baser än 2.
| b | minsta k så att gcd( k +1, b −1) = 1 och k × b n +1 har täckningsmängd | täcksats för k × b n +1 | minsta k så att gcd( k −1, b −1) = 1 och k × b n −1 har täckningsmängd | täcksats för k × b n −1 |
|---|---|---|---|---|
| 2 | 78557 | {3, 5, 7, 13, 19, 37, 73} | 509203 | {3, 5, 7, 13, 17, 241} |
| 3 | 125050976086 | {5, 7, 13, 17, 19, 37, 41, 193, 757} | 63064644938 | {5, 7, 13, 17, 19, 37, 41, 193, 757} |
| 4 | 66741 | {5, 7, 13, 17, 241} | 39939 | {5, 7, 13, 19, 73, 109} |
| 5 | 159986 | {3, 7, 13, 31, 601} | 346802 | {3, 7, 13, 31, 601} |
| 6 | 174308 | {7, 13, 31, 37, 97} | 84687 | {7, 13, 31, 37, 97} |
| 7 | 1112646039348 | {5, 13, 19, 43, 73, 181, 193, 1201} | 408034255082 | {5, 13, 19, 43, 73, 181, 193, 1201} |
| 8 | 47 | {3, 5, 13} | 14 | {3, 5, 13} |
| 9 | 2344 | {5, 7, 13, 73} | 74 | {5, 7, 13, 73} |
| 10 | 9175 | {7, 11, 13, 37} | 10176 | {7, 11, 13, 37} |
| 11 | 1490 | {3, 7, 19, 37} | 862 | {3, 7, 19, 37} |
| 12 | 521 | {5, 13, 29} | 376 | {5, 13, 29} |
| 13 | 132 | {5, 7, 17} | 302 | {5, 7, 17} |
| 14 | 4 | {3, 5} | 4 | {3, 5} |
| 15 | 91218919470156 | {13, 17, 113, 211, 241, 1489, 3877} | 36370321851498 | {13, 17, 113, 211, 241, 1489, 3877} |
| 16 | 66741 | {7, 13, 17, 241} | 33965 | {7, 13, 17, 241} |
| 17 | 278 | {3, 5, 29} | 86 | {3, 5, 29} |
| 18 | 398 | {5, 13, 19} | 246 | {5, 13, 19} |
| 19 | 765174 | {5, 7, 13, 127, 769} | 1119866 | {5, 7, 13, 127, 181} |
| 20 | 8 | {3, 7} | 8 | {3, 7} |
Täckande uppsättningar används också för att bevisa förekomsten av sammansatta generaliserade Fibonacci-sekvenser med de två första termerna coprime ( primefri sekvens ), såsom sekvensen som börjar med 20615674205555510 och 3794765361567513.
Konceptet med en täckande uppsättning kan lätt generaliseras till andra sekvenser som visar sig vara mycket enklare.
I följande exempel används + som det är i reguljära uttryck för att betyda 1 eller fler. Till exempel betyder 91 + 3 mängden {913, 9113, 91113, 911113, … }.
Ett exempel är följande åtta sekvenser:
- (29·10 n − 191) / 9 eller 32 + 01
- (37·10 n + 359) / 9 eller 41 + 51
- (46·10 n + 629) / 9 eller 51 + 81
- (59·10 n − 293) / 9 eller 65 + 23
- (82·10 n + 17) / 9 eller 91 + 3
- (85·10 n + 41) / 9 eller 94 + 9
- (86·10 n + 31) / 9 eller 95 + 9
- (89·10 n + 593) / 9 eller 98 + 23
I varje fall är varje term delbar med ett av primtal från mängden { 3, 7, 11, 13 } . Dessa primtal kan sägas bilda en täckande uppsättning exakt analog med Sierpinski- och Riesel-tal. Täckningssetet {3, 7, 11, 37 } finns för flera liknande sekvenser, inklusive:
- (38·10 n − 137) / 9 eller 42 + 07
- (4·10 n − 337) / 9 eller 4 + 07
- (73·10 n + 359) / 9 eller 81 + 51
- 9175·10 n + 1 eller 91750 + 1
- 10176·10 n − 1 eller 101759 +
- (334·10 n − 1)/9 eller 371 +
- (12211·10 n − 1)/3 eller 40703 +
- (8026·10 n − 7)/9 eller 8917 +
Även för andra baser än 10:
- 521·12 n + 1 eller 3750 + 1 i duodecimal
- (1288·12 n − 1)/11 eller 991 + i duodecimal
- (4517·12 n − 7)/11 eller 2X27 + i duodecimal
- 376·12 n − 1 eller 273E + i duodecimal
Den täckande uppsättningen av dem är {5, 13, 29 }
Ett ännu enklare fall kan hittas i sekvensen:
- (76·10 n − 67) / 99 ( n måste vara udda ) eller (76) + 7 (sekvens: 7, 767, 76767, 7676767, 767676767 etc.)
Här kan det visas att om:
- w har formen 3 k ( n = 6 k + 1 ): (76) + 7 är delbart med 7
- w har formen 3 k + 1 ( n = 6 k + 3 ): (76) + 7 är delbart med 13
- w har formen 3 k + 2 ( n = 6 k + 5 ): (76) + 7 är delbart med 3
Vi har alltså en täckande uppsättning med endast tre primtal {3, 7, 13 }. Detta är endast möjligt eftersom sekvensen ger heltalstermer endast för udda n .
En täckande uppsättning förekommer också i sekvensen:
- (343·10 n − 1) / 9 eller 381 + .
Här kan det visas att:
- Om n = 3 k + 1 är (343·10 n − 1) / 9 delbart med 3.
- Om n = 3 k + 2 är (343·10 n − 1) / 9 delbart med 37.
- Om n = 3 k , då (343·10 n − 1) / 9 algebraiskt faktorer som ((7·10 k − 1) / 3)·((49·10 2 k + 7·10 k + 1) / 3 ) .
Eftersom (7·10 k − 1) / 3 kan skrivas som 23 + , för sekvensen 381 + , har vi en täckande mängd av {3, 37, 23 + } – en täckande mängd med oändligt många termer.
Statusen för (343×10 n − 1)/9 är som för 3511808×63 n + 1:
- Om n = 3 k + 1 är 3511808·63 n + 1 delbart med 37.
- Om n = 3 k + 2 är 3511808·63 n + 1 delbart med 109.
- Om n = 3 k , då 3511808·63 n + 1 algebraiskt faktorer som (152·63 k + 1)·(23104·63 2 k − 152·63 k + 1)
Vi har alltså en täckning på {37, 109, 152×63 + 1, 152×63 2 + 1, 152×63 3 + 1, ...} eller {37, 109, 2Q0 + 1 i bas 63} – en täckande set med oändligt många termer.
Ett enklare exempel är 4×9 n − 1, det är lika med (2×3 n − 1) × (2×3 n + 1), så dess täckande uppsättningar är {5, 17, 53, 161, 485, ... } och {7, 19, 55, 163, 487, ... }, mer allmänt, om k och b båda är r -:te potenser för en udda r > 1, kan k × b n + 1 inte vara primtal, och om k och b båda är r -te potenser för en r > 1 så kan inte k × b n − 1 vara primtal.
Ett annat exempel är 1369×30 n − 1, dess täckning är {7, 13, 19, 37×30 k − 1 ( k = 1, 2, 3, ...)}