Covering set

In mathematics, a covering set for a sequence of integers refers to a set of prime numbers such that every term in the sequence is divisible by at least one member of the set.[1] The term "covering set" is used only in conjunction with sequences possessing exponential growth.

Sierpinski and Riesel numbers

The use of the term "covering set" is related to Sierpinski and Riesel numbers. These are odd natural numbers k for which the formula k 2n + 1 (Sierpinski number) or k 2n − 1 (Riesel number) produces no prime numbers.[2] Since 1960 it has been known that there exists an infinite number of both Sierpinski and Riesel numbers (as solutions to families of congruences based upon the set {3, 5, 17, 257, 641, 65537, 6700417} [a][3]) but, because there are an infinitude of numbers of the form k 2n + 1 or k 2n − 1 for any k, one can only prove k to be a Sierpinski or Riesel number through showing that every term in the sequence k 2n + 1 or k 2n − 1 is divisible by one of the prime numbers of a covering set.

These covering sets form from prime numbers that in base 2 have short periods. To achieve a complete covering set, Wacław Sierpiński showed that a sequence can repeat no more frequently than every 24 numbers. A repeat every 24 numbers give the covering set {3, 5, 7, 13, 17, 241} , while a repeat every 36 terms can give several covering sets: {3, 5, 7, 13, 19, 37, 73}; {3, 5, 7, 13, 19, 37, 109}; {3, 5, 7, 13, 19, 73, 109} and {3, 5, 7, 13, 37, 73, 109}.[4]

Riesel numbers have the same covering sets as Sierpinski numbers.

Other covering sets

Covering sets (thus Sierpinski numbers and Riesel numbers) also exists for bases other than 2.[5][6]

b smallest k such that gcd(k+1,b−1) = 1 and k×bn+1 has covering set covering set for k×bn+1 smallest k such that gcd(k−1,b−1) = 1 and k×bn−1 has covering set covering set for k×bn−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}

Covering sets are also used to prove the existence of composite generalized Fibonacci sequences with first two terms coprime (primefree sequence).

The concept of a covering set can easily be generalised to other sequences which turn out to be much simpler.

In the following examples + is used as it is in regular expressions to mean 1 or more. For example, 91+3 means the set {913, 9113, 91113, 911113…}

An example are the following eight sequences:

  • (29·10n − 191) / 9 or 32+01
  • (37·10n + 359) / 9 or 41+51
  • (46·10n + 629) / 9 or 51+81
  • (59·10n − 293) / 9 or 65+23
  • (82·10n + 17) / 9 or 91+3
  • (85·10n + 41) / 9 or 94+9
  • (86·10n + 31) / 9 or 95+9
  • (89·10n + 593) / 9 or 98+23

In each case, every term is divisible by one of the primes {3, 7, 11, 13} .[7] These primes can be said to form a covering set exactly analogous to Sierpinski and Riesel numbers.[8] The covering set {3, 7, 11, 37} is found for several similar sequences,[8] including:

  • (38·10n − 137) / 9 or 42+07
  • (4·10n − 337) / 9 or 4+07
  • (73·10n + 359) / 9 or 81+51
  • 9175·10n + 1 or 91750+1
  • 10176·10n − 1 or 101759+
  • (334·10n − 1)/9 or 371+
  • (12211·10n − 1)/3 or 40703+
  • (8026·10n − 7)/9 or 8917+

Also for bases other than 10:

The covering set of them is {5, 13, 29}

An even simpler case can be found in the sequence:

  • (76·10n − 67) / 99 (n must be odd) or (76)+7 [Sequence: 7, 767, 76767, 7676767, 767676767 etc.]

Here, it can be shown that if:

  • w is of form 3 k (n = 6 k + 1): (76)+7 is divisible by 7
  • w is of form 3 k + 1 (n = 6 k + 3): (76)+7 is divisible by 13
  • w is of form 3 k + 2 (n = 6 k + 5): (76)+7 is divisible by 3

Thus we have a covering set with only three primes {3, 7, 13}.[9] This is only possible because the sequence gives integer terms only for odd n.

A covering set also occurs in the sequence:

  • (343·10n − 1) / 9 or 381+.

Here, it can be shown that:

  • If n = 3 k + 1, then (343·10n − 1) / 9 is divisible by 3.
  • If n = 3 k + 2, then (343·10n − 1) / 9 is divisible by 37.
  • If n = 3 k, then (343·10n − 1) / 9 is algebraic factored as ((7·10k − 1) / 3)·((49·102k + 7·10k + 1) / 3).

Since (7·10k − 1) / 3 can be written as 23+, for the sequence 381+, we have a covering set of {3, 37, 23+} – a covering set with infinitely many terms.[8]

The status for (343×10^n−1)/9 is like that for 3511808×63^n+1:

  • If n = 3 k + 1, then 3511808·63n + 1 is divisible by 37.
  • If n = 3 k + 2, then 3511808·63n + 1 is divisible by 109.
  • If n = 3 k, then 3511808·63n + 1 is algebraic factored as (152·63k + 1)·((23104·102k − 152·63k + 1)

Thus we have a covering of {37, 109, 152*63+1, 152*63^2+1, 152*63^3+1, ...} or {37, 109, 2Q0+1 in base 63} – a covering set with infinitely many terms.

A more simple case is 4×9^n−1, it is equal to (2×3^n−1) × (2×3^n+1), thus its covering sets are {5, 17, 53, 161, 485, ...} and {7, 19, 55, 163, 487, ...}, more generally, if k and b are both r-th powers for an odd r>1, then k×b^n+1 cannot be prime, and if k and b are both r-th powers for an r>1 then k×b^n−1 cannot be prime.

Another case is 1369×30^n−1, its covering is {7, 13, 19, 37×30^k−1 (k=1, 2, 3, ...)}

gollark: https://squiddev.cc/2018/01/26/ae-sat.html
gollark: * NP-hard
gollark: By reducing it to an NP-complete problem.
gollark: I think SquidDev also proved that autocrafting was really computationally hard somehow.
gollark: I might.

See also

Notes

a These are of course the only known Fermat primes and the two prime factors of F5.

References
  1. Guy, Richard; Unsolved Problems in Number Theory; pp. 119–121. ISBN 0387208607
  2. Wells, David; Prime Numbers: The Most Mysterious Figures in Math; pp. 212, 219. ISBN 1118045718
  3. Sierpiński, Wacław (1960); ‘Sur un problème concernant les nombres’; Elemente der Mathematik, 15(1960); pp. 73–96
  4. Covering Sets for Sierpiński Numbers
  5. Sierpinski conjectures and proofs
  6. Riesel conjectures and proofs
  7. Plateau and Depression Primes
  8. "Sequences by Prime Difficulty". Archived from the original on 2014-07-14. Retrieved 2014-06-17.
  9. Smoothly Undulating Palindromic Primes
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.