Saturday 9 March 2024

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*2n+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. This is because for a number of the form 2n-1 where n is any integer, b2-1 has no “primitive divisor” — that is, no prime divisor that does not divide a smaller number of the form bn-1. This is because:

  1. b2-1 = (b+1)(b-1)
  2. b+1 is a power of 2
  3. both b+1 and b-1 divide by 2
  4. so, b2-1  lacks a prime divisor for these bases
  5. Bang’s Theorem states that the only other such case is 26-1, which I will not discuss further
The absence of a factor with period 2 means that for bases of the form 2n-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 whcih an 8-cover provides the smallest Sierpiński number is 168, and I know of no base where a 9-cover, 10-cover or 15-cover provide the smallest Sierpiński or Riesel number, but 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