Covering set

Last updated

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.

Contents

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. [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} [lower-alpha 1] 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

Covering sets (thus Sierpinski numbers and Riesel numbers) also exists for bases other than 2. [5] [6] [7]

bsmallest k such that gcd(k+1, b−1) = 1 and k×bn+1 has covering setcovering set for k×bn+1smallest k such that gcd(k−1, b−1) = 1 and k×bn−1 has covering setcovering set for k×bn−1
278557{3, 5, 7, 13, 19, 37, 73}509203{3, 5, 7, 13, 17, 241}
3125050976086{5, 7, 13, 17, 19, 37, 41, 193, 757}63064644938{5, 7, 13, 17, 19, 37, 41, 193, 757}
466741{5, 7, 13, 17, 241}39939{5, 7, 13, 19, 73, 109}
5159986{3, 7, 13, 31, 601}346802{3, 7, 13, 31, 601}
6174308{7, 13, 31, 37, 97}84687{7, 13, 31, 37, 97}
71112646039348{5, 13, 19, 43, 73, 181, 193, 1201}408034255082{5, 13, 19, 43, 73, 181, 193, 1201}
847{3, 5, 13}14{3, 5, 13}
92344{5, 7, 13, 73}74{5, 7, 13, 73}
109175{7, 11, 13, 37}10176{7, 11, 13, 37}
111490{3, 7, 19, 37}862{3, 7, 19, 37}
12521{5, 13, 29}376{5, 13, 29}
13132{5, 7, 17}302{5, 7, 17}
144{3, 5}4{3, 5}
1591218919470156{13, 17, 113, 211, 241, 1489, 3877}36370321851498{13, 17, 113, 211, 241, 1489, 3877}
1666741{7, 13, 17, 241}33965{7, 13, 17, 241}
17278{3, 5, 29}86{3, 5, 29}
18398{5, 13, 19}246{5, 13, 19}
19765174{5, 7, 13, 127, 769}1119866{5, 7, 13, 127, 181}
208{3, 7}8{3, 7}

Covering sets are also used to prove the existence of composite generalized Fibonacci sequences with first two terms coprime (primefree sequence), 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 expressions to mean 1 or more. For example, 91+3 means the set {913, 9113, 91113, 911113, …}.

An example are the following eight sequences:

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

Also for bases other than 10:

The covering set of them is {5, 13, 29}

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

The status for (343×10n − 1)/9 is like that for 3511808×63n + 1:

Thus we have a covering of {37, 109, 152×63 + 1, 152×632 + 1, 152×633 + 1, ...} or {37, 109, 2Q0+1 in base 63} – a covering set with infinitely many terms.

A more simple example is 4×9n − 1, it is equal to (2×3n − 1) × (2×3n + 1), thus its covering sets are {5, 17, 53, 161, 485, ...} and {7, 19, 55, 163, 487, ...}, more generally, if k and b are both r-th powers for an odd r > 1, then k×bn + 1 cannot be prime, and if k and b are both r-th powers for an r > 1 then k×bn − 1 cannot be prime.

Another example is 1369×30n − 1, its covering is {7, 13, 19, 37×30k − 1 (k = 1, 2, 3, ...)}

See also

Notes

  1. ↑ These are of course the only known Fermat primes and the two prime factors of F5. [3]

Related Research Articles

The duodecimal system is a positional notation numeral system using twelve as its base. The number twelve is instead written as "10" in duodecimal, whereas the digit string "12" means "1 dozen and 2 units". Similarly, in duodecimal, "100" means "1 gross", "1000" means "1 great gross", and "0.1" means "1 twelfth".

In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.

In number theory, a Sierpiński number is an odd natural number k such that is composite for all natural numbers n. In 1960, Wacław Sierpiński proved that there are infinitely many odd integers k which have this property.

Seventeen or Bust was a volunteer computing project started in March 2002 to solve the last seventeen cases in the Sierpinski problem. The project solved eleven cases before a server loss in April 2016 forced it to cease operations. Work on the Sierpinski problem moved to PrimeGrid, which solved a twelfth case in October 2016. Five cases remain unsolved as of December 2021.

In recreational mathematics, a repunit is a number like 11, 111, or 1111 that contains only the digit 1 — a more specific type of repdigit. The term stands for repeated unit and was coined in 1966 by Albert H. Beiler in his book Recreations in the Theory of Numbers.

The tables contain the prime factorization of the natural numbers from 1 to 1000.

<span class="mw-page-title-main">Semiperfect number</span>

In number theory, a semiperfect number or pseudoperfect number is a natural number n that is equal to the sum of all or some of its proper divisors. A semiperfect number that is equal to the sum of all its proper divisors is a perfect number.

In mathematics, a Riesel number is an odd natural number k for which is composite for all natural numbers n. In other words, when k is a Riesel number, all members of the following set are composite:

73 (seventy-three) is the natural number following 72 and preceding 74. In English, it is the smallest natural number with twelve letters in its spelled out name.

300 is the natural number following 299 and preceding 301.

<span class="mw-page-title-main">Constructible polygon</span> Regular polygon that can be constructed with compass and straightedge

In mathematics, a constructible polygon is a regular polygon that can be constructed with compass and straightedge. For example, a regular pentagon is constructible with compass and straightedge while a regular heptagon is not. There are infinitely many constructible polygons, but only 31 with an odd number of sides are known.

In mathematics, a harshad number in a given number base is an integer that is divisible by the sum of its digits when written in that base. Harshad numbers in base n are also known as n-harshad numbers. Harshad numbers were defined by D. R. Kaprekar, a mathematician from India. The word "harshad" comes from the Sanskrit harṣa (joy) + da (give), meaning joy-giver. The term "Niven number" arose from a paper delivered by Ivan M. Niven at a conference on number theory in 1977.

In number theory, a Wagstaff prime is a prime number of the form

In number theory, a nontotient is a positive integer n which is not a totient number: it is not in the range of Euler's totient function φ, that is, the equation φ(x) = n has no solution x. In other words, n is a nontotient if there is no integer x that has exactly n coprimes below it. All odd numbers are nontotients, except 1, since it has the solutions x = 1 and x = 2. The first few even nontotients are

In mathematics, a noncototient is a positive integer n that cannot be expressed as the difference between a positive integer m and the number of coprime integers below it. That is, m − φ(m) = n, where φ stands for Euler's totient function, has no solution for m. The cototient of n is defined as n − φ(n), so a noncototient is a number that is never a cototient.

A divisibility rule is a shorthand and useful way of determining whether a given integer is divisible by a fixed divisor without performing the division, usually by examining its digits. Although there are divisibility tests for numbers in any radix, or base, and they are all different, this article presents rules and examples only for decimal, or base 10, numbers. Martin Gardner explained and popularized these rules in his September 1962 "Mathematical Games" column in Scientific American.

100,000 (one hundred thousand) is the natural number following 99,999 and preceding 100,001. In scientific notation, it is written as 105.

In mathematics, a covering system is a collection

In number theory, Proth's theorem is a primality test for Proth numbers.

20,000 is the natural number that comes after 19,999 and before 20,001.

References

  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. ↑ Sierpinski conjectures and proofs
  6. ↑ Riesel conjectures and proofs
  7. ↑ Generalized Sierpinski number base b
  8. ↑ Plateau and Depression Primes
  9. 1 2 3 List of near-repdigit-related (probable) prime numbers, sorted by difficulty
  10. ↑ Smoothly Undulating Palindromic Primes
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.