Covering set

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 2ⁿ + 1 (Sierpinski number) or k 2ⁿ − 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 2ⁿ + 1 or k 2ⁿ − 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 2ⁿ + 1 or k 2ⁿ − 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.

Covering sets are also used to prove the existence of composite Fibonacci sequences (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·10ⁿ − 191) / 9 or 32⁺01
• (37·10ⁿ + 359) / 9 or 41⁺51
• (46·10ⁿ + 629) / 9 or 51⁺81
• (59·10ⁿ − 293) / 9 or 65⁺23
• (82·10ⁿ + 17) / 9 or 91⁺3
• (85·10ⁿ + 41) / 9 or 94⁺9
• (86·10ⁿ + 31) / 9 or 95⁺9
• (89·10ⁿ + 593) / 9 or 98⁺23

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

• (38·10ⁿ − 137) / 9 or 42⁺07
• (4·10ⁿ − 337) / 9 or 4⁺07
• (73·10ⁿ + 359) / 9 or 81⁺51

An even simpler case can be found in the sequence:

• (76·10ⁿ − 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}.[7] This is only possible because the sequence gives integer terms only for odd n.

A covering set also occurs in the sequence:

• (343·10ⁿ − 1) / 9 or 381⁺.

Here, it can be shown that:

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

Since (7·10^k − 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.[6]

• Covering system

^a These are of course the only known Fermat primes and the two prime factors of F₅.

• Sierpinski-like numbers