Cover structures by base

In recent weeks I have been rereading the 2000s file ‘Generalizing Sierpiński Numbers to Base b’, written by a team from the University of Tennessee at Martin.

Although Sierpiński numbers to base 2 are well-known in studies of prime numbers because Proth primes — those of the form k*2ⁿ+1 — occur frequently as possible factors of binomial numbers like Mersenne and Fermat numbers, similar numbers for other bases were not studied until the 1990s. Moreover, although a major project exists to verify the smallest Sierpiński number for all bases up to 1030, bases as small as 71 have not been started yet.

What was really interesting to me re-reading ‘Generalizing Sierpiński Numbers to Base b’ (my off-line .pdf copy is under a slightly different title but has the same text) this summer was the discussion of various covering set periods. The UT Martin team noted that different bases have vastly different minimal periods for a covering set of primes to repeat. For bases that are 2 or one fewer than a power of 2, this period is relatively long, since for any b of the form 2ⁿ-1, b²-1 has no “primitive divisor” — that is, no prime divisor that does not divide a smaller number of the form bⁿ-1. This is because:

1. b²-1 = (b+1)(b-1)
2. b+1 is a power of 2
3. both b+1 and b-1 divide by 2
4. thus, b²-1  lacks a prime divisor for these bases
5. Bang’s Theorem states that the only other such case is 2⁶-1, which I will not discuss further

The absence of a factor with period 2 means that for bases of the form 2ⁿ-1 covering sets must be built from prime numbers with longer periods. For other numbers, there will always be a cover with period 12 or shorter, but for base 3, there can be no cover repeating more frequently than every 48 terms, as was established by Yannick Saouter in 1995.

In the following table, I will indicate the presence or absence for bases from 2 to 175 of covers with the following periods:

• 2
• 3
• 4
• 6
• 8
• 9
• 10
• 12
• 15

Covers with periods 5, 7, 11 and 13, as was noted by the UT Martin team, do not occur for any base so small as 175. 14-covers have not been investigated, although such a cover would be expected to involve eight primes, one with period 2 and seven with periods 7 or 14.

8-, 9-, 10- and 15-covers were not discussed in the UT Martin study, although I have long known of the 8-cover {11, 73, 101, 137} in base 10. The smallest base for which an 8-cover provides the smallest Sierpiński number is 168, while I know of no base where a 9-cover, 10-cover or 15-cover provide the smallest Sierpiński or Riesel number. Nevertheless,  my re-read made me feel these were worthy of study.

For all bases:

• red means the base lacks a cover with that period
• light green means a non-primitive cover
• dark green means a primitive cover that cannot be reduced

Presence or absence of N-cover for Bases from 2 to 175
N-cover	2	3	4	6	8	9	10	12	15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175