Covering Sets for Sierpinski Numbers
All odd numbers can be expressed in the form k.2^{n} +1 for some odd k. In particular, this is true of odd primes. However, there are some values of k for which there are no primes of this form for any positive integer n. Such k are called Sierpinski numbers. It is relatively easy to find candidates for Sierpinski numbers, but how do we prove mathematically that the property holds, since we obviously cannot check every possible n ?
If p is a prime such that p divides k.2^{r} +1, then p will also divide k.2^{n} +1 for all n º r mod e, where e is the exponent of p to the base 2. Therefore, in order to prove the Sierpinski property for k, it is sufficient to find a set of primes P = {p_{i}}, such that the set of congruences n º r_{i} mod e_{i} is enough to account for every n. If m = lcm{e_{i}}, then it is sufficient to prove that P covers all n from 1 to m (or 0 to m 1), since any other value of n can be covered reduced modulo m without changing its divisibility properties. If such a set P can be found for which this is the case, and for which no subset of P will do, then P is known as a covering set for k, and m is known as the Sierpinski modulus of both P and k. We shall refer to the values of n from 1 to m as positions. Any uncovered position is often referred to as a hole.
Since the set of primes dividing the number 2^{m}  1 is the set of all primes with exponent dividing m, covering sets with modulus m are necessarily subsets of this set. It is therefore possible to obtain covering sets without prior reference to a particular Sierpinski number by examining the sets of primes dividing 2^{m}  1 and looking for any subsets of this for which it is possible to find congruences of the type r mod e that will cover every position from 1 to m. For every covering set found in this way, it is possible to calculate a sample Sierpinski number with that covering set by solving a set of simultaneous congruences in the unknown k of the form k º  2 ^{r} mod p (since we assume that k.2^{r} + 1 º 0 mod p). This always has an odd solution less than 2P by the Chinese Remainder Theorem.
Let D(m) be the set of primes dividing 2^{m}  1 and let d(m) = D(m), that is, the number of primes dividing 2^{m}  1. The method used to obtain the results given here is to consider for each m, every realistic subset P Í D(m). By realistic, we mean that there are several obvious conditions that may be applied to P. For instance, let S(P) be the sum of the inverses of the exponents of primes p Î P. Since each prime p can cover at most 1/e possible values, for P to be a covering set, S(P) has to be at least 1. Since only the prime 3 has exponent 2 and all others have exponent greater than 2, we can see immediately that at least 3 primes are needed. With a little extra work, it is obvious that at least 4 are needed, since we can quickly discount the triples {3, 5, 7} and {3, 7, 31}, and all other triples have S(P) < 1. In fact, there are only 8 quadruples such that S(P) ³ 1, and each of these can be discounted easily, so that P has to have at least 5 members. Additionally, for each realistic subset P, the lowest common factor of the related exponents must equal m, otherwise the modulus is not m.
If m is a prime, then all primes p Î D(m) have exponent m and so can cover only one position. We therefore require d(m) ³ m, which is impossible since 3^{m} > 2^{m}. Thus we may consider nonprime m only in the following.
For each subset P Í D(m), we proceed by taking each prime p Î P in rising exponent order, and consider the e possible patterns of divisibility modulo e, running from r = 1 to r = e. For each pattern, we count the maximum number of values from 1 to m that can be covered by p and that have not already been covered by any of the previous primes in the set. If no value of r gives a count greater than zero then the prime is redundant and we can discard the set, otherwise we store the best value of r and consider the associated positions now covered. When all the primes in the set have been treated in this way, either all values are covered, in which case we may have a covering set, or not, in which case we can discard this set. Finally, each possible covering set should be checked to ensure that it does not have a subset that forms a covering set with modulus less than m.
For each m, we factorise 2^{m}  1 and then apply the above procedure to the entire divisor set D(m). Only if this set is sufficient to cover all possibilities do we then apply the procedure to realistic subsets. As an example, consider m = 30. This gives rise to the primes 3, 7, 31, 11, 151, 331 of exponent 2, 3, 5, 10, 15 and 30 respectively. There are no primes of exponent 6. The following grid shows one possibility for an optimum set of divisibility patterns.
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
3, 7, 31 
11 
3 
7 
3 
31 
3, 7 
151 
3 
7 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
3, 31 
11 
3, 7 
331 
3 
7, 31 
3 

3, 7 

21 
22 
23 
24 
25 
26 
27 
28 
29 
30 
3, 31 
7, 11 
3 

3, 7 
31 
3 
7 
3, 151 

Hence D(30) covers at most 26 positions and so does not contain a covering set.
The lowest value for which a covering set exists is m = 24, for which the full divisor set of primes is {3, 5, 7, 13, 17, 241}. No subset of this is a covering set and so the full set is a covering set. The algorithm provides the rvalues 1, 2, 1, 8, 4, 24 respectively, which in turn provide the congruences k º 1 mod 3, 1 mod 5, 3 mod 7, 10 mod 13, 1 mod 17 and 240 mod 241. The solution of this is k = 3608251, which is part of the Keller cycle with smallest member 271129.
The next value that will provide a covering is m = 36, which has a divisor set of
{3, 5, 7, 13, 19, 37, 73, 109}. It turns out that there are 4 covering sets, consisting of the subsets obtained on removal of 19, 37, 73 and 109 from the full set. The generated Sierpinski number and the smallest number in the associated Keller cycle are as follows.
D(36){19} k = 129764281 (57816799)
D(36){37} k = 180351181 (11822359)
D(36){73} k = 140774371 (1290677)
D(36){109} k = 56330011 (12756019)
The next value worth considering is m = 48. D(48) = {3, 5, 7, 13, 17, 97, 241, 257, 673}. There are 15 covering sets with modulus 48. These are listed together with the Sierpinski number generated from the set of congruences and the smallest number in the Keller cycle.
{3, 5, 7, 13, 17, 97, 257} k = 579788401 (327739)
{3, 5, 7, 13, 17, 97, 673} k = 2722630921 (41134369)
{3, 5, 7, 13, 17, 257, 673} k = 6127129291 (425780911)
{3, 5, 7, 13, 97, 241, 257} k = 15816297871 (764612281)
{3, 5, 7, 13, 97, 241, 673} k = 31771100371 (879092101)
{3, 5, 7, 13, 241, 257, 673} k = 82620861151 (4046512609)
{3, 5, 7, 17, 97, 241, 257} k = 18563509891 (597875869)
{3, 5, 7, 17, 97, 241, 673} k = 13472700601 (1269436171)
{3, 5, 7, 17, 97, 257, 673} k = 36362815891 (478078081)
{3, 5, 7, 17, 241, 257, 673} k = 53672378581 (5112582467)
{3, 5, 13, 17, 97, 241, 257} k = 18563509891 (37158601)
{3, 5, 13, 17, 97, 241, 673} k = 53591139151 (359292259)
{3, 5, 13, 17, 97, 257, 673} k = 62031957901 (919128377)
{3, 5, 13, 17, 241, 257, 673} k = 96189651601 (12298364659)
{3, 5, 17, 97, 241, 257, 673} k = 789324314851 (39803042693)
The next useful value is m = 60, where D(m) = {3, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321}. There are 23 separate covering sets of modulus 60, two of which have length 10 and the rest length 9. These are listed with sample Sierpinski numbers.
{3, 5, 7, 11, 13, 31, 41, 61, 151} k = 73557542341 (7791902033)
{3, 5, 7, 11, 13, 31, 41, 61, 331} k = 164359523611 (23246795491)
{3, 5, 7, 11, 13, 31, 41, 61, 1321} k = 108481381291 (45299429363)
{3, 5, 7, 11, 13, 31, 41, 151, 331} k = 341230638031 (11801652413)
{3, 5, 7, 11, 13, 31, 41, 151, 1321} k = 3637888362391 (59150216933)
{3, 5, 7, 11, 13, 31, 41, 331, 1321} k = 11100063122431 (311005640147)
{3, 5, 7, 11, 13, 31, 61, 151, 331} k = 2667671254531 (7354973911)
{3, 5, 7, 11, 13, 31, 61, 151, 1321} k = 481098215881 (204575287201)
{3, 5, 7, 11, 13, 31, 61, 331, 1321} k = 8657762681851 (596688750227)
{3, 5, 7, 11, 13, 31, 151, 331, 1321} k = 28335128920381 (243698810449)
{3, 5, 7, 11, 13, 41, 61, 151, 331} k = 2187373836931 (36090391531)
{3, 5, 7, 11, 13, 41, 61, 151, 1321} k = 1427536248421 (368666816041)
{3, 5, 7, 11, 13, 41, 61, 331, 1321} k = 25635689938141 (983548147697)
{3, 5, 7, 11, 13, 41, 151, 331, 1321} k = 21320705274151 (1722422320457)
{3, 5, 7, 11, 13, 61, 151, 331, 1321} k = 49078894152571 (193636884083)
{3, 5, 7, 11, 31, 41, 61, 151, 331, 1321} k = 1382840931784441 (10019542331573)
{3, 5, 7, 13, 31, 41, 61, 151, 331} k = 1555209650641 (228919237553)
{3, 5, 7, 13, 31, 41, 61, 151, 1321} k = 14019845261341 (191976083123)
{3, 5, 7, 13, 31, 41, 61, 331, 1321} k = 1996943298451 (1996943298451)
{3, 5, 7, 13, 31, 41, 151, 331, 1321} k = 182899677484261 (3958265274739)
{3, 5, 7, 13, 31, 61, 151, 331, 1321} k = 134501188981351 (3281241306713)
{3, 5, 7, 13, 41, 61, 151, 331, 1321} k = 257806054679911 (3201918268463)
{3, 5, 11, 13, 31, 41, 61, 151, 331, 1321} k = 19964725987718971 (150870306352861)
We note that the algorithm used gives one set of congruences for each covering set. In reality, it is often possible to contruct alternative sets of congruences, which will give rise to different Sierpinski numbers. In particular, different sets of congruences may give rise to separate Keller cycles entirely.
If m = 2^{x}.z for some x £ 5 and any z, then 2^{m}  1 is divisible by the Fermat primes F_{0} to F_{x 1} , which have exponents 2^{1}, 2^{2}, …, 2^{x}. The divisibility patterns of these can be offset from each other in order to cover 1/2^{1} + 1/2^{2} +…+ 1/2^{x} positions, leaving 1/2^{x} positions free. Since each prime can be made to cover at least one position by sliding its divisibility pattern, if then D(m) must contain a covering set. The reverse is not true, as indicated by m = 60 above.
As an example, consider m = 24 and take x = 3. Then m/2^{x} + x = 24/8 + 3 = 6. Since we have d(m) = 6, it follows immediately that a covering set exists, as has already been verified above. Now consider m = 64 and take x = 5. Then m/2^{x} + x = 2 + 5 = 7. Since d(m) = 7 there must also be a covering set of modulus 64. In fact, D(64) is the only covering set of modulus 64. This is because 2^{32} +1 splits into two primes, 641 and 6700417, each of exponent 64, and which can be made to cover the two "holes" left by the 5 Fermat primes at positions 32 and 64. For completeness, the Sierpinski number obtained from placing the prime 641 at position 32 is 15511380746462593381 and the one obtained from placing 6700417 at position 32 is 2935363331541925531. These both belong to the same Keller cycle with smallest member 201446503145165177, which is therefore the only cycle with modulus 64. In particular, the cycle flips to itself with a base offset of 29.
For m = 72, we can take x = 3 so that 72/2^{3} + 3 = 12. Since d(72) = 12, we know that covering sets exist. In fact, there are at least 92 covering sets of modulus 72, of differing lengths from 8 to 10 primes. Modulus 72 provides the first occurrence of a particular effect, that is the possibility that a covering set strictly contains another covering set with a different divisibility pattern that is more efficient at covering the available positions. This greatly complicates any attempt to enumerate covering sets. In particular, it implies that considering primes in different orders will sometimes give different results.
The next value of interest is m = 80. With x = 4 we have m/2^{x} + x = 9. Since d(80) = 9, we have covering sets. In fact, D(80) is the only covering set since each of the 5 members of D(80) that is not a Fermat prime is a primitive root to base 2 and so can cover only one position.
For m = 84, we have D(84) = {3, 5, 7, 13, 29, 43, 113, 127, 337, 1429, 5419, 14449}. There are 8 covering sets, each obtained by removing one of the 8 largest members of D(84).
For m up to 200, the values m = 96 (with at least 71 covering sets), 108 (with 24), 120, 128 (with 2), 144, 160, 168, 180, 192 and 200 provide many covering sets. Of more interest are the values m = 112 and 140, for which, like m = 24, 64 and 80, the divisor set D(m) is the only covering set of order m.
The values of m included in the above are the only values up to 200 that have associated covering sets. For other values of m, such as 4, 8, 12, 16, 32, 40, 132, 156 and 176, the set D(m) covers all but one possibility. In such cases, if doubling m provides at least 2 additional primitive factors (that is, 2^{m} +1 has at least two factors), then a covering set is achieved, such as happens for m = 12, 32 and 40. This idea extends as follows.
Let c(m) be the maximum number of positions from 1 to m covered by D(m). If c(m) = y_{1} and 2^{m} +1 has y_{2} new and distinct prime factors then c(2m) ³ 2y_{1} + y_{2} (or 2m, whichever is smaller). This is because the divisibility patterns for m double up and any new factor of 2^{m} +1 can be used to cover at least one other position. For m odd, this formula is not particularly helpful because it does not take into account the fact that the prime 3 covers half of all positions. However, if m is even, we have that 3 Î D(m), and the inequality is often enough, as for m = 32 and 40 above, to prove that a covering set exists of modulus 2m. The simplest example is m = 12, where c(12) = 11. Since 2^{12} +1 = 17*241, we have y_{1} = 11, y_{2} = 2 and so c(24) ³ 24, and therefore D(24) contains a covering set.
It is obvious from the above inequality that for any m, repeated doubling will eventually produce a value 2^{x}.m that provides a covering set, although sometimes this will happen sooner than implied, since the Fermat primes have lower exponent than normal. For instance, if m = 3, then doubling 3 times is enough to obtain a covering set (for m = 24), but for m = 5 and 7, doubling has to be performed 4 times. This compares well with the inequality, which only guarantees a covering set for x considerably larger. Of course, if c(m) is known exactly for m even, then the inequality will take fewer doublings to reach this point.
In the doubling inequality, the value 2y_{1} + y_{2} may exceed 2m. Since c(2m), by definition, is at most 2m, the correct inequality is therefore that c(2m) ³ min(2y_{1} + y_{2}, m). In what follows, we shall consider any formula for c(m) to be considered similarly.
If p is an odd prime then c(p) = d(p). Doubling the length of the pattern, we have
c(2p) = p + c(p) + y_{1}. The first component arises since 3 always divides 2^{p} +1 for p odd. The second component is from the divisors of 2^{p}  1 since, on doubling, each of these divisors will cover one odd and one even position, only one of which will overlap with 3. The last component comprises the remaining y_{1} primitive divisors of 2^{p} +1, which all have exponent 2p since 2^{2p}  1 = (2^{p}  1).(2^{p} +1). In order for 2p to provide a covering set, we therefore require that c(p) + y_{1} ³ p. This means that either c(p) ³ p/2 or y_{1} ³ p/2. Given the definitions of c(p) and y_{1} this is unlikely.
Suppose m = p*q where p and q are distinct odd primes, and let c(p) = y_{1} and c(q) = y_{2}. Let y_{3} be the number of additional prime divisors of 2^{pq}  1 after removing those of 2^{p}  1 and 2^{q}  1. Then c(pq) = qy_{1} + py_{2} + y_{3}  y_{4} where y_{4} is the number of positions is the divisibility patterns which are covered by both p and q. With a little thought it is obvious that y_{4} = y_{1}*y_{2}.
For example, if p = 3 and q = 5, then y_{1} = y_{2} = y_{3} = 1 and so c(15) = 5 + 3 + 1  1 = 8. For
p = 11 and q = 23, we have y_{1} = y_{2} = 2 and y_{3} = 3 so c(253) = 46 + 22 + 3  4 = 67. Note that the rough estimation c(253) ³ 1 [(1 (1/11))*(1 (1/23))] = 33/253 based purely on exclusion by either 11 or 23 is poor by comparison. Taking q = 2 in the above equation, we have y_{2} = 1 and so c(2p) = 2y_{1} + p + y_{3}  y_{1} , which corresponds to the previous result.
Suppose m = p^{x} for some prime p. If p = 2 then the doubling inequality becomes an equality since each new primitive factor covers exactly one position. If p is odd, we can similarly align divisibility patterns so that they do not overlap. In either case, we obtain
c(p^{x}) = y_{1}.p^{x 1} + y_{2}.p^{x 2} + … + y_{x 1}.p + y_{x} , where y_{i} is the number of primitive factors of 1. For p = 2 and y < 6, y_{i} = 1, and so we are always one prime short. However, y_{6} = 2 since 2^{32} + 1 (the primitive part of 2^{64}  1) is 641*6700417, and so c(64) = 64. Obviously, this means that c(2^{x}) = 2^{x} for all x ³ 6.
Consider m = 2^{7} = 128. We know that it contains a covering set of modulus 64 but we require a covering set of modulus 128. Since F_{x} is composite at least for all 5 £ x £ 23, we can replace one prime of modulus 64 by two of modulus 128, and similarly for higher powers of 2 so that unique covering sets always exist. If p = 2, then, since S(p^{x}) ® 1 as x ® ¥ , it is only a matter of time until one of the y_{i} exceeds 1 and provides a covering set. However, if p is odd, then the sum to infinity is 1/(p 1) and so the values y_{i} would have to be consistently large to achieve parity, in particular y_{1}. Since the first value of p for which y_{1} > 1 is p = 11 and the first value for which y_{1} > 2 is p = 29, it is apparent that powers of odd primes do not provide covering sets.
Suppose m = p*q*r where p, q, and r are distinct odd primes.
Let y_{1} = number of divisors of 2^{p}  1.
Let y_{2} = number of divisors of 2^{q}  1.
Let y_{3} = number of divisors of 2^{r}  1.
Let y_{4} = number of primitive divisors of 2^{pq}  1.
Let y_{5} = number of primitive divisors of 2^{pr}  1.
Let y_{6} = number of primitive divisors of 2^{qr}  1.
Let y_{7} = number of primitive divisors of 2^{pqr}  1.
Then c(pqr) = (qry_{1} + pry_{2} + pqy_{3}) + (ry_{4} + qy_{5} + py_{6}) + y_{7}
 (ry_{1}y_{2} + qy_{1}y_{3} + py_{2}y_{3}  y_{1}y_{2}y_{3})  (y_{3}y_{4} + y_{2}y_{5} + y_{1}y_{6})
The first three terms comprise the number of appearances in the divisibility pattern of any of the primes involved in D(pqr). The subtracted terms comprise all possible overlaps between two or more primes. The negative value in the first subtracted term must be included in order to ensure that any positions covered by 3 different primes are not counted twice. For instance, if p = 3, q = 5 and r = 7, then y_{1} = y_{2} = y_{3} = y_{4} = y_{5} = 1, y_{6} = 2 and y_{7} = 3 and so we have
c(105) = (35+21+15)+(7+5+6)+3 (7+5+3 1) (1+1+2) = 71+18+3 14 4 = 74, which is verified to be the correct answer.
If, however, p = 2 in the above, then the formula must be adjusted downwards by an additional term y_{4}y_{5} since in order to use primitive factors of 2^{pq}  1 and 2^{pr}  1 we must offset both divisibility patterns from that of 3 = 2^{2}  1. This effectively doubles the length of the cycle pattern for such factors from pqr to 2pqr and hence guarantees overlaps. If y_{4} or y_{5} is zero (e.g. if q = 3), then this coincides with the original formula.
From now on, we let y(m) denote the number of primitive divisors of 2^{m}  1. We then have d(m) = .
Suppose m = 2p^{z}. Then c(2p^{z}) ³ p^{z} + c(p^{z}) + y(m). This is an immediate extension of the result for m = 2p since the overlap between exponents 2 and p^{z} is always half of the total, and we can always throw in the primitive factors of 2^{m}  1. In fact, there are almost always additional components, as we shall incorporate shortly.
Suppose m = 2z where z is odd. Then we have c(2z) ³ z + c(z) + y(m) by extension of the above result, since exactly half of the positions from 1 to 2z covered by m = z are of opposing polarity to those covered by the prime 3. This is an improvement over the doubling inequality. Similar but more complicated effects are produced for higher powers of 2, since further Fermat primes have a significant effect.
Suppose m = 2^{x}.p for some odd prime p. Then c(2^{x}.p) = p.c(2^{x}) + . The first term is obvious by extending the length of the divisibility pattern of 2^{x}. Since the holes in this divisibility pattern are at 2^{x}, 2.2^{x}, 3.2^{x}, …, p.2^{x}, each primitive divisor with modulus 2^{i}.p can cover only one of these holes.
Suppose m = 2^{x}.p^{z} for some odd prime p. Then c(2^{x}.p^{z}) = p^{z}.c(2^{x}) + . This is a logical extension of the previous result. Taking x = 1 in this equation gives the exact result which improves on the estimate given above. This formula also holds for x = 0, as long as we consider c(1) = y(1) = 0.
Suppose m = p^{x}.q for some odd primes p and q. In this case, we now have to consider overlaps. We have c(m) = q.c(p^{x}) +  c(p^{x}).y(q) as long as d(p^{x}) + y(q) £ p. The extra condition is explained as follows. Consider the m positions laid out as a grid with pq columns and p^{x 1} rows. Then d(p^{x}) of the first p positions are taken by members of D(p^{x}) and so the number of available positions that do not overlap with these is p d(p^{x}). Since each prime of exponent pq covers an entire column, the condition guarantees that there are enough free columns. If the condition does not hold, then we may still use this formula as an upper bound. For example, if m = 3^{3}.5 or 3^{3}.7 then, since d(3^{3}) = 3, there is an additional overlap and so the additional term y(3q) must be subtracted from the equation for c(m). As x increases, the complexity of overlaps increases and the formula becomes less accurate.
Suppose m = a.b where a > 1 and b > 1. Then c(m) ³ a.c(b) + y(m) since we can simply multiply the divisibility pattern for b by a and then fill as many holes as we have new primes of exponent m. For instance, if m = 60, we have y(6) = 2 and we may take a = 2 and b = 30 to get c(60) ³ 54. However, if we take a = 3 and b = 20, we get c(60) ³ 56, and if we take a = 5 and b = 12 we get c(60) ³ 57. Although in this case, the actual value is c(60) = 60, this indicates that if a divisor b of m can be found such that c(b) is as close to b as possible, then we may be able to close the gap to get c(m) = m. This is an improvement over the doubling inequality as more flexibility is allowed.
The above formulae for c(m) may be coupled with the doubling inequality to obtain estimates for much larger values of m. Note that whenever a formula gives the exact result c(m) = m, this means that the whole of D(m) is the only covering set of modulus m, and if a formula gives a result greater than m, this implies that there are more than one covering sets. In this case, we wonder whether it is possible to obtain formulae for the number of covering sets.
It is obvious that if m provides a covering set then so does any multiple zm of m, since all the primes that constituted the covering set remain. However, the possibility exists that no new covering sets exist and that all covering sets provided by zm have modulus less than zm. In order to overcome this, we need to be able to construct at least one covering set of modulus zm. When z = 2 this is straightforward, since as long as m is not a power of 2 then 2^{m} +1 has at least 2 factors, and we have previously dealt with the case where m is a power of 2. However, for z > 2 there is no guarantee that there will be enough additional factors to replace a prime of exponent m.
Note that factorisations of 2^{n}  1, and hence the values of y_{i} , may be obtained from the published Cunningham tables, available in book form or via the Internet.
It is obvious that given a modulus m and divisor d of m, every primitive factor of 2^{d}  1 can cover at least one position. This can be expressed as follows.
c(m) =
Since y(1) = 0, we can ignore d = 1. What can we say about a(d) ? Since overlaps will occur for a typical modulus, a(d) will depend on the order in which the divisors are considered. For consistency, each prime and all its powers dividing m will be considered in numerical sequence first, and then all other divisors, again in numerical order.
Obviously, a(d) £ m/d since there are m/d occurrences of d between 1 and m. If m = p^{x} for some x, then a(p^{i}) = p^{x i}. If d = 2^{x} for some x, then a(d) = m/d since powers of 2 are considered first and can always be completely offset from each other. Otherwise, let 2^{x} be the maximum power of 2 dividing m and 2^{z} be the maximum power of 2 dividing d. Then for each d that is not a power of 2, we can at least say that a(d) £ m/(2^{x z}d). This gives an upper bound for c(m). For example, if m = 30, the set of divisors of m is {2, 3, 5, 6, 10, 15, 30}. Thus we have c(30) £ 30/2y(2) + 30/2*3y(3) + 30/2*5y(5) + 30/6y(6) + 30/10y(10) + 30/2*15y(15) + 30/30y(30). Now y(2) = y(3) = y(5) = y(10) = y(15) = y(30) = 1 and y(6) = 0. This gives c(30) £ 28 and so no covering sets exist. In fact, c(30) = 26.
A slightly larger example is m = 126 = 2.3^{2}.7. The set of divisors is {2, 3, 9, 7, 6, 14, 18, 21, 42, 63, 126). All values of y are 1 except y(6) = 0 and y(126) = 2. Thus c(126) £ 125 and so has no covering sets. In fact, c(126) = 113. Similarly, the estimate gives c(198) £ 195, ensuring that no covering sets exist with modulus 198. In fact, c(198) = 177.
For m = 2^{x}.p^{z} (including x = 0), the estimated upper bound is exact, since there is no danger of unaccounted overlaps.
Unfortunately, if the calculated upper bound exceeds m, then we cannot tell immediately whether or not m has any covering sets. If, however, we could produce a formula for the number of overlaps, then we would know the nature of m for all m. Enumeration of all covering sets of order m when c(m) > m remains a separate problem.
For completeness, the values of c(m) for m £ 200 are given in the following table. Modulii that provide covering sets are marked with an asterisk. Values of c(m) in excess of m indicate the existence of more than one covering set, but since considering primes in D(m) in different sequences provides different results, no great significance can be applied.
m 
c(m) 
m 
c(m) 
m 
c(m) 
m 
c(m) 
m 
c(m) 
1 
0 
41 
2 
81 
42 
121 
24 
161 
39 
2 
1 
42 
34 
82 
45 
122 
63 
162 
138 
3 
1 
43 
3 
83 
2 
123 
47 
163 
5 
4 
3 
44 
38 
84 
* 85 
124 
99 
164 
131 
5 
1 
45 
30 
85 
22 
125 
37 
165 
113 
6 
4 
46 
26 
86 
47 
126 
113 
166 
90 
7 
1 
47 
3 
87 
37 
127 
1 
167 
2 
8 
7 
48 
* 50 
88 
84 
128 
* 130 
168 
* 176 
9 
4 
49 
8 
89 
1 
129 
50 
169 
16 
10 
7 
50 
39 
90 
87 
130 
101 
170 
127 
11 
2 
51 
22 
91 
22 
131 
2 
171 
89 
12 
11 
52 
44 
92 
76 
132 
131 
172 
137 
13 
1 
53 
3 
93 
34 
133 
26 
173 
4 
14 
9 
54 
44 
94 
52 
134 
71 
174 
129 
15 
8 
55 
22 
95 
26 
135 
96 
175 
80 
16 
15 
56 
54 
96 
* 100 
136 
126 
176 
175 
17 
1 
57 
23 
97 
2 
137 
2 
177 
66 
18 
14 
58 
34 
98 
65 
138 
101 
178 
93 
19 
1 
59 
2 
99 
60 
139 
2 
179 
3 
20 
18 
60 
* 62 
100 
97 
140 
* 140 
180 
* 190 
21 
10 
61 
1 
101 
2 
141 
55 
181 
4 
22 
14 
62 
33 
102 
78 
142 
76 
182 
135 
23 
2 
63 
38 
103 
2 
143 
38 
183 
66 
24 
* 24 
64 
* 64 
104 
98 
144 
* 158 
184 
169 
25 
7 
65 
18 
105 
74 
145 
42 
185 
47 
26 
15 
66 
53 
106 
58 
146 
78 
186 
130 
27 
13 
67 
2 
107 
2 
147 
73 
187 
45 
28 
25 
68 
56 
108 
* 115 
148 
119 
188 
149 
29 
3 
69 
28 
109 
2 
149 
2 
189 
121 
30 
26 
70 
59 
110 
91 
150 
141 
190 
144 
31 
1 
71 
3 
111 
44 
151 
5 
191 
5 
32 
31 
72 
* 78 
112 
* 112 
152 
141 
192 
* 200 
33 
16 
73 
3 
113 
5 
153 
84 
193 
3 
34 
19 
74 
41 
114 
84 
154 
118 
194 
83 
35 
14 
75 
46 
115 
34 
155 
40 
195 
122 
36 
* 37 
76 
62 
116 
94 
156 
155 
196 
180 
37 
2 
77 
24 
117 
66 
157 
2 
197 
2 
38 
21 
78 
59 
118 
64 
158 
83 
198 
177 
39 
17 
79 
3 
119 
27 
159 
63 
199 
2 
40 
39 
80 
* 80 
120 
* 126 
160 
* 162 
200 
* 206 