mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, a covering set for a sequence of integers refers to a

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...

s such that ''every'' term in the

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...

divisible In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a '' multiple'' of m. An integer n is divisible or evenly divisibl ...

by ''at least one'' member of the set. The term "covering set" is used only in conjunction with sequences possessing

exponential growth Exponential growth occurs when a quantity grows as an exponential function of time. The quantity grows at a rate directly proportional to its present size. For example, when it is 3 times as big as it is now, it will be growing 3 times as fast ...

Sierpinski and Riesel numbers

The use of the term "covering set" is related to Sierpinski and Riesel numbers. These are odd

natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...

s for which the formula (Sierpinski number) or (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 In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group (mathematics), group, ring (mathematics), ring, or vector space) that is compatible with the structure in the ...

based upon the set but, because there are an infinitude of numbers of the form or for any , one can only prove to be a Sierpinski or Riesel number through showing that ''every'' term in the sequence or 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 Wacław Franciszek Sierpiński (; 14 March 1882 – 21 October 1969) was a Polish mathematician. He was known for contributions to set theory (research on the axiom of choice and the continuum hypothesis), number theory, theory of functions ...

showed that a sequence can repeat no more frequently than every 24 numbers. A repeat every 24 numbers give the covering set , while a repeat every 36 terms can give several covering sets: ; ; and . 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. Covering sets are also used to prove the existence of composite generalized Fibonacci sequences with first two terms

coprime In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...

(

primefree sequence In mathematics, a primefree sequence is a sequence of integers that does not contain any prime numbers. More specifically, it usually means a sequence defined by the same recurrence relation as the Fibonacci numbers, but with different initial con ...

), such as the sequence starting with 20615674205555510 and 3794765361567513. 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 expression A regular expression (shortened as regex or regexp), sometimes referred to as rational expression, is a sequence of characters that specifies a match pattern in text. Usually such patterns are used by string-searching algorithms for "find" ...

s to mean 1 or more. For example, 91⁺3 means the set . An example are the following eight sequences: * (29·10^''n'' − 191) / 9 or 32⁺01 * (37·10^''n'' + 359) / 9 or 41⁺51 * (46·10^''n'' + 629) / 9 or 51⁺81 * (59·10^''n'' − 293) / 9 or 65⁺23 * (82·10^''n'' + 17) / 9 or 91⁺3 * (85·10^''n'' + 41) / 9 or 94⁺9 * (86·10^''n'' + 31) / 9 or 95⁺9 * (89·10^''n'' + 593) / 9 or 98⁺23 In each case, every term is divisible by one of the primes from the set . These primes can be said to form a covering set exactly analogous to Sierpinski and Riesel numbers.List of near-repdigit-related (probable) prime numbers, sorted by difficulty
/ref> The covering set is found for several similar sequences, including: * (38·10^''n'' − 137) / 9 or 42⁺07 * (4·10^''n'' − 337) / 9 or 4⁺07 * (73·10^''n'' + 359) / 9 or 81⁺51 * 9175·10^''n'' + 1 or 91750⁺1 * 10176·10^''n'' − 1 or 101759⁺ * (334·10^''n'' − 1)/9 or 371⁺ * (12211·10^''n'' − 1)/3 or 40703⁺ * (8026·10^''n'' − 7)/9 or 8917⁺ Also for bases other than 10: * 521·12^''n'' + 1 or 3750⁺1 in

duodecimal The duodecimal system, also known as base twelve or dozenal, is a positional numeral system using twelve as its base. In duodecimal, the number twelve is denoted "10", meaning 1 twelve and 0 units; in the decimal system, this number is i ...

* (1288·12^''n'' − 1)/11 or 991⁺ in duodecimal * (4517·12^''n'' − 7)/11 or 2X27⁺ in duodecimal * 376·12^''n'' − 1 or 273E⁺ in duodecimal The covering set of them is An even simpler case can be found in the sequence: * (76·10^''n'' − 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 (): (76)⁺7 is divisible by 7 * w is of form (): (76)⁺7 is divisible by 13 * w is of form (): (76)⁺7 is divisible by 3 Thus we have a covering set with only three primes .Smoothly Undulating Palindromic Primes
/ref> This is only possible because the sequence gives integer terms ''only for odd n''. A covering set also occurs in the sequence: * (343·10^''n'' − 1) / 9 or 381⁺. Here, it can be shown that: * If , then is divisible by 3. * If , then is divisible by 37. * If , then algebraically factors as . Since can be written as 23⁺, for the sequence 381⁺, we have a covering set of – a covering set with ''infinitely many'' terms. The status for (343×10^''n'' − 1)/9 is like that for 3511808×63^''n'' + 1: * If , then is divisible by 37. * If , then is divisible by 109. * If , then algebraically factors as Thus we have a covering of or – a covering set with ''infinitely many'' terms. A more simple example is 4×9^''n'' − 1, it is equal to (2×3^''n'' − 1) × (2×3^''n'' + 1), thus its covering sets are and , 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 example is 1369×30^''n'' − 1, its covering is

Sierpinski and Riesel numbers

Other covering sets

See also

Notes

References

External links