Covering set
Encyclopedia
In mathematics
, a covering set for a sequence
of integer
s refers to a set of prime number
s 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
.
s. These are odd
natural number
s 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}.
Riesel numbers have the same covering sets as Sierpinski numbers.
).
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 three sequences:
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:
Here, it can be shown that if:
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:
Here, it can be shown that:
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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a covering set for a sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
of integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s refers to a set of prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s such that every term in the sequence is divisible
Division (mathematics)
right|thumb|200px|20 \div 4=5In mathematics, especially in elementary arithmetic, division is an arithmetic operation.Specifically, if c times b equals a, written:c \times b = a\,...
by at least one member of the set. The term "covering set" is used only in conjunction with sequences possessing exponential growth
Exponential growth
Exponential growth occurs when the growth rate of a mathematical function is proportional to the function's current value...
.
Sierpinski and Riesel numbers
The use of the term "covering set" is related to Sierpinski and Riesel numberRiesel number
In mathematics, a Riesel number is an odd natural number k for which the integers of the form k·2n − 1 are composite for all natural numbers n....
s. These are odd
Even and odd numbers
In mathematics, the parity of an object states whether it is even or odd.This concept begins with integers. An even number is an integer that is "evenly divisible" by 2, i.e., divisible by 2 without remainder; an odd number is an integer that is not evenly divisible by 2...
natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s 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
Congruence relation
In abstract algebra, a congruence relation is an equivalence relation on an algebraic structure that is compatible with the structure...
) 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
Radix
In mathematical numeral systems, the base or radix for the simplest case is the number of unique digits, including zero, that a positional numeral system uses to represent numbers. For example, for the decimal system the radix is ten, because it uses the ten digits from 0 through 9.In any numeral...
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}.
Riesel numbers have the same covering sets as Sierpinski numbers.
Other covering sets
Covering sets are also used to prove the existence of composite Fibonacci sequences (primefree sequencePrimefree sequence
In mathematics, a primefree sequence is a sequence of integers that does not contain any prime numbers. More specifically, it generally means a sequence defined by the same recurrence relation as the Fibonacci numbers, but with different initial conditions causing all members of the sequence to be...
).
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 three sequences:
- (82*10n+17)/9 or 91+3
- (85*10n+41)/9 or 94+9
- (86*10n+31)/9 or 95+9
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+7 [Sequence: 7, 767, 76767, 7676767, 767676767 etc]
Here, it can be shown that if:
- w is of form 3k (n = 6k+1): (76)+7 is divisible by 7
- w is of form 3k+1 (n = 6k+3): (76)+7 is divisible by 13
- w is of form 3k+2 (n = 6k+5): (76)+7 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 381+.
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 23+, for the sequence 381+, we have a covering set of {3, 37, 23+} - a covering set with infinitely many terms.