Covering set

From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article is about meaning in the number theory. For other uses, see Covering.

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[edit]

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[edit]

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·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} .[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·10n − 137) / 9 or 42+07
  • (4·10n − 337) / 9 or 4+07
  • (73·10n + 359) / 9 or 81+51

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}.[7] 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.[6]

See also[edit]

Notes[edit]

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

References[edit]

  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. ^ Plateau and Depression Primes
  6. ^ a b c Sequences by Prime Difficulty
  7. ^ Smoothly Undulating Palindromic Primes

External links[edit]