Covering set
From Wikipedia, the free encyclopedia
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. The term "covering set" is used only in conjunction with sequences possessing exponential growth.
[edit] 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. Since 1960 it has been known that there exists an infinite number of both Sierpinski and Riesel numbers (as solutions to families of congruences) 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 the covering set.
These covering sets form from prime numbers that in base 2 have short periods. To achieve a complete covering set, it can be shown that the 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}, whilst 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}. See Covering Sets For Sierpinski numbers for details of other covering sets. Riesel numbers have the same covering sets as Sierpinski numbers.
[edit] Other covering sets
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.
An example are the following three sequences:
- 82*10n+17/9 or 91w3
- 85*10n+41/9 or 94w9
- 86*10n+31/9 or 95w9
In each case, every term is divisible by one of the primes {3, 7, 11, 13}. These primes can be said to form a covering set exactly analogous to Sierpinski and Riesel numbers.
An even simpler case can be found in the sequence:
- 76*10n-67/99 (n must be odd) or (76)w7 [Sequence: 7, 767, 76767, 7676767, 767676767 etc]
Here, it can be shown that if:
- w is of form 3k (n = 6k+1): (76)w7 is divisible by 7
- w is of form 3k+1 (n = 6k+3): (76)w7 is divisible by 13
- w is of form 3k+2 (n = 6k+5): (76)w7 is divisible by 3
Thus we have a covering set with only three primes {3, 7, 13}. 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 381w.
Here, it can be shown that:
- If n = 3k+1, then 343*10n-1/9 is divisible by 3.
- If n = 3k+2, then 343*10n-1/9 is divisible by 37.
- If n = 3k, 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 23w, for the sequence 381w, we have a covering set of {3, 37, 23w} - a covering set with infinitely many terms.
