Searching for large Sierpinski numbers
In this article's immediate predecessor, I described the results of a survey of Sierpinski numbers, which consisted mainly of enumerating these to a limit of 5*108 and highlighting any issues that were raised along the way. In the current article, rather than build up data gradually, I will take a more global view of the results and matters arising from a survey to the extended limit of 2*109.
The search method is as before, where each possible value of k, not divisible by 3, 5 or 7, is tested for each exponent n from 1 to 1000. If any prime is found for a particular k, that value of k is ignored. All values of k which survive this step are then passed to the program psieve3.exe, which builds up a list of Nash congruences. If at any time, the accumulation of Nash congruences combine to produce a complete covering, then we have a Sierpinski number, and the associated covering set can be extracted from the congruences (though not without the occasional difficulty). Covering sets are labelled, generally according to the order they were first identified.
The complete list of covering sets associated with at least one Sierpinski number under 2*109 is as follows (where P is the product of the primes in the set):
|
code |
modulus |
covering set |
2P |
|
A |
24 |
{3, 5, 7, 13, 17, 241} |
1.1e7 |
|
B |
36 |
{3, 5, 7, 13, 19, 37, 73} |
1.4e8 |
|
C |
48 |
{3, 5, 7, 13, 17, 97, 257} |
1.1e9 |
|
D |
36 |
{3, 5, 7, 13, 19, 73, 109} |
4.1e8 |
|
E |
36 |
{3, 5, 7, 13, 19, 37, 109} |
2.1e8 |
|
F |
36 |
{3, 5, 7, 13, 37, 73, 109} |
8.0e8 |
|
G |
72 |
{3, 5, 7, 13, 17, 19, 109, 433} |
4.2e10 |
|
H |
48 |
{3, 5, 7, 17, 97, 241, 257} |
2.2e10 |
|
I |
48 |
{3, 5, 7, 13, 17, 257, 673} |
8.0e9 |
|
K |
72 |
{3, 5, 7, 13, 17, 19, 37, 433} |
1.4e10 |
|
L |
48 |
{3, 5, 7, 13, 17, 97, 673} |
3.0e9 |
|
M |
48 |
{3, 5, 13, 17, 97, 241, 257} |
4.0e10 |
|
N |
72 |
{3, 5, 7, 17, 19, 37, 109, 241} |
6.6e10 |
|
P |
72 |
{3, 5, 7, 17, 19, 37, 73, 241} |
4.4e10 |
|
R |
72 |
{3, 5, 7, 13, 17, 37, 109, 433} |
8.1e10 |
|
S |
72 |
{3, 5, 7, 13, 17, 19, 73, 433} |
2.8e10 |
|
T |
60 |
{3, 5, 7, 11, 13, 41, 61, 151, 331} |
3.8e12 |
|
U |
60 |
{3, 5, 7, 11, 13, 31, 41, 61, 331} |
7.7e11 |
|
V |
72 |
{3, 5, 7, 17, 37, 109, 241, 433} |
1.5e12 |
|
W |
72 |
{3, 5, 7, 13, 19, 109, 241, 433} |
5.9e11 |
|
X |
60 |
{3, 5, 7, 11, 13, 31, 41, 61, 151} |
3.5e11 |
|
Y |
48 |
{3, 5, 7, 13, 97, 241, 673} |
4.3e10 |
|
Z |
72 |
{3, 5, 13, 17, 19, 37, 109, 241} |
1.2e11 |
|
AA |
48 |
{3, 5, 7, 17, 97, 257, 673} |
6.0e10 |
|
AB |
48 |
{3, 5, 13, 17, 97, 241, 673} |
1.0e11 |
|
AC |
72 |
{3, 5, 7, 13, 19, 37, 241, 433} |
2.0e11 |
|
AD |
72 |
{3, 5, 7, 13, 37, 73, 241, 433} |
7.7e11 |
|
AE |
144 |
{3, 5, 7, 13, 17, 19, 73, 97, 577} |
3.6e12 |
|
AF |
72 |
{3, 5, 7, 17, 19, 73, 109, 241} |
1.3e11 |
|
AG |
72 |
{3, 5, 7, 13, 17, 37, 73, 433} |
5.4e10 |
|
AH |
144 |
{3, 5, 7, 13, 17, 19, 73, 257, 577} |
9.5e12 |
|
AI |
72 |
{3, 5, 7, 13, 17, 73, 109, 433} |
1.6e11 |
|
AJ |
48 |
{3, 5, 7, 13, 97, 241, 257} |
1.6e10 |
|
AK |
72 |
{3, 5, 7, 17, 37, 73, 109, 241} |
2.5e11 |
|
AL |
72 |
{3, 5, 7, 13, 19, 73, 241, 433} |
4.0e11 |
|
AM |
72 |
{3, 5, 7, 17, 19, 37, 241, 433} |
2.6e11 |
|
AN |
60 |
{3, 5, 7, 11, 13, 31, 41, 61, 1321} |
3.1e12 |
|
AP |
48 |
{3, 5, 7, 17, 241, 257, 673} |
1.5e11 |
|
AR |
60 |
{3, 5, 7, 13, 31, 41, 61, 151, 331} |
1.1e13 |
|
AS |
72 |
{3, 5, 13, 17, 19, 73, 109, 241} |
2.4e11 |
|
AT |
180 |
{3, 5, 7, 11, 13, 19, 37, 61, 151, 181, 631} |
2.2e16 |
|
AU |
72 |
{3, 5, 13, 17, 19, 37, 73, 241} |
8.2e10 |
|
AV |
48 |
{3, 5, 7, 17, 97, 241, 673} |
5.6e10 |
|
AW |
60 |
{3, 5, 7, 11, 13, 31, 61, 151, 1321} |
1.1e13 |
|
AX |
72 |
{3, 5, 7, 17, 19, 73, 241, 433} |
5.2e11 |
|
AY |
144 |
{3, 5, 7, 17, 37, 73, 97, 109, 257} |
2.6e13 |
|
AZ |
72 |
{3, 5, 13, 17, 37, 73, 109, 241} |
4.7e11 |
|
BA |
48 |
{3, 5, 13, 17, 97, 257, 673} |
1.1e11 |
|
BB |
180 |
{3, 5, 7, 11, 13, 19, 31, 41, 73, 181, 631} |
6.0e15 |
|
BC |
60 |
{3, 5, 7, 11, 13, 31, 41, 151, 331} |
1.9e12 |
The letter J is missing from this list for historical reasons, as it was once used to explain the concept of overlaps (Sierpinski numbers belonging to more than one Keller cycle).
The above list includes 12 of the 15 available covering sets of modulus 48, but surprisingly only 7 of the 23 available covering sets of modulus 60. No Sierpinski numbers of modulus 96 occur within the current limit.
The Keller cycle produced by the Keller iteration k ® (2k+P) mod 2P (where P is the product of the primes in the covering set) is a closed loop of length equal to the modulus of the covering set.
For a given covering set, once the 2P limit is reached, there can be no more Keller cycles and so the number of these is finite. Additionally, the concept of the flip cycle has already been introduced. Amongst other things, this guarantees that for any covering set whose constituent primes have order modulo 2 that are not all even or not all odd, there must be an even number of Keller cycles. To the current search limit of 109, this has been verified to be true for covering sets A, B, C, D, E and F.
The current allocation of covering sets to Keller cycles is as follows:
|
set |
modulus |
# cycles |
status |
|
A |
24 |
2 |
(complete) |
|
B |
36 |
4 |
(complete) |
|
C |
48 |
2 |
(complete) |
|
D |
36 |
4 |
(complete) |
|
E |
36 |
4 |
(complete) |
|
F |
36 |
4 |
(complete) |
|
G |
72 |
4 |
|
|
H |
48 |
2 |
|
|
I |
48 |
2 |
|
|
K |
72 |
4 |
|
|
L |
48 |
2 |
|
|
M |
48 |
2 |
|
|
N |
72 |
3 |
|
|
P |
72 |
4 |
|
|
R |
72 |
3 |
|
|
S |
72 |
4 |
|
|
T |
60 |
2 |
|
|
U |
60 |
2 |
|
|
V |
72 |
1 |
|
|
W |
72 |
1 |
|
|
X |
60 |
12 |
|
|
Y |
48 |
2 |
|
|
Z |
72 |
2 |
|
|
AA |
48 |
2 |
|
|
AB |
48 |
1 |
|
|
AC |
72 |
2 |
|
|
AD |
72 |
1 |
|
|
AE |
144 |
1 |
|
|
AF |
72 |
3 |
|
|
AG |
72 |
4 |
|
|
AH |
144 |
1 |
|
|
AI |
72 |
1 |
|
|
AJ |
48 |
2 |
|
|
AK |
72 |
2 |
|
|
AL |
72 |
2 |
|
|
AM |
72 |
2 |
|
|
AN |
60 |
4 |
|
|
AP |
48 |
1 |
|
|
AR |
60 |
1 |
|
|
AS |
72 |
1 |
|
|
AT |
180 |
1 |
|
|
AU |
72 |
1 |
|
|
AV |
48 |
1 |
|
|
AW |
60 |
2 |
|
|
AX |
72 |
1 |
|
|
AY |
144 |
1 |
|
|
AZ |
72 |
1 |
|
|
BA |
48 |
1 |
|
|
BB |
180 |
1 |
|
|
BC |
60 |
1 |
|
|
|
|
114 |
|
I have no explanation as yet for the high incidence of cycles with covering set X.
There are 13394 distinct Sierpinski numbers in the range considered, including 141 overlaps.
This includes only four values, namely 308914459, 1319709979, 1554424697 and 1905955429 that are divisible by 7.
The smallest Sierpinski numbers for each of the moduli identified so far are:
|
modulus |
smallest Sierpinski number |
|
24 |
271129 |
|
36 |
78557 |
|
48 |
327739 |
|
60 |
169073869 |
|
72 |
1777613 |
|
144 |
516108143 |
|
180 |
1143502909 |
One value, namely 987152869, is the base value for two distinct Keller cycles, both of modulus 60. This is the only occurrence of such in the range considered.
My previous numbering of Keller cycles was based on the order in which they were found. However, the cases of the Sierpinski number divisible by 7, and the increasing number of overlaps, sometimes means that in order to retain a rising sequence, some re-ordering has to take place every now and then. To avoid this, I have simply listed the base values in increasing order.
The full list of Keller cycle base values, with associated covering sets, is as follows:
|
sequence |
base number |
modulus |
covering set |
factorisation |
|
1 |
78557 |
36 |
B |
17*4621 |
|
2 |
271129 |
24 |
A |
prime |
|
3 |
271577 |
24 |
A |
59*4603 |
|
4 |
322523 |
36 |
F |
prime |
|
5 |
327739 |
48 |
C |
prime |
|
6 |
934909 |
36 |
D |
prime |
|
7 |
1290677 |
36 |
E |
137*9421 |
|
8 |
1777613 |
72 |
G |
29*61297 |
|
9 |
2510177 |
36 |
B |
167*15031 |
|
10 |
5455789 |
48 |
C |
59*89*1039 |
|
11 |
5841947 |
36 |
E |
271*21557 |
|
12 |
6828631 |
36 |
D |
23*337*881 |
|
13 |
8184977 |
36 |
B |
prime |
|
14 |
8959163 |
36 |
E |
prime |
|
15 |
10306187 |
36 |
E |
prime |
|
16 |
11206501 |
48 |
H |
prime |
|
17 |
11822359 |
36 |
D |
prime |
|
18 |
12413281 |
36 |
F |
17*191*3823 |
|
19 |
12756019 |
36 |
B |
prime |
|
20 |
15273751 |
48 |
I |
prime |
|
21 |
17220887 |
36 |
D |
3709*4643 |
|
22 |
22024609 |
72 |
K |
1303*16903 |
|
23 |
24885199 |
48 |
L |
113*191*1153 |
|
24 |
27862127 |
36 |
F |
29*960763 |
|
25 |
36029731 |
72 |
G |
71*507461 |
|
26 |
37158601 |
48 |
M |
prime |
|
27 |
41134369 |
48 |
L |
prime |
|
28 |
51612259 |
72 |
N |
149*346391 |
|
29 |
51889823 |
72 |
P |
2347*22109 |
|
30 |
56191673 |
72 |
AU |
79*711287 |
|
31 |
57816799 |
36 |
F |
53*1090883 |
|
32 |
59198569 |
72 |
K |
prime |
|
33 |
105885947 |
72 |
R |
3181*33287 |
|
34 |
108628343 |
72 |
S |
151*719393 |
|
35 |
115281169 |
72 |
K |
311*370679 |
|
36 |
146053577 |
72 |
G |
4721*30937 |
|
37 |
155223473 |
72 |
S |
37*4195229 |
|
38 |
156701453 |
72 |
P |
3931*39863 |
|
39 |
169073869 |
60 |
T |
53*163*19571 |
|
40 |
174329011 |
60 |
U |
59*257*11497 |
|
41 |
210465533 |
72 |
P |
181*1162793 |
|
42 |
211062227 |
72 |
V |
prime |
|
43 |
212497043 |
72 |
W |
11*19317913 |
|
44 |
213578567 |
48 |
I |
127*1681721 |
|
45 |
240936503 |
72 |
K |
1129*213407 |
|
46 |
266142407 |
60 |
X |
23*347*33347 |
|
47 |
278770729 |
48 |
Y |
2551*109279 |
|
48 |
292099127 |
60 |
X |
37*2659*2969 |
|
49 |
297988073 |
60 |
X |
prime |
|
50 |
308914459 |
72 |
Z |
7*41*101*10657 |
|
51 |
332320309 |
60 |
X |
292*73*5413 |
|
52 |
341371831 |
48 |
AA |
2711*125921 |
|
53 |
359292259 |
48 |
AB |
131*2742689 |
|
54 |
365928503 |
72 |
AC |
347*1054549 |
|
55 |
369699767 |
72 |
R |
43*8597669 |
|
56 |
389737669 |
48 |
AP |
prime |
|
57 |
478078081 |
48 |
AA |
13*412*131*167 |
|
58 |
482420221 |
72 |
G |
71*6794651 |
|
59 |
488303521 |
60 |
X |
prime |
|
60 |
497369479 |
60 |
X |
19*683*38327 |
|
61 |
510877279 |
72 |
AD |
11*79*587891 |
|
62 |
516108143 |
144 |
AE |
prime |
|
63 |
563461069 |
72 |
AF |
97*1051*5527 |
|
64 |
577256123 |
72 |
AG |
43*13424561 |
|
65 |
597875869 |
48 |
H |
19*23*1031*1327 |
|
66 |
605248493 |
144 |
AH |
2351*257443 |
|
67 |
613997417 |
48 |
AJ |
11*673*82939 |
|
68 |
615884447 |
72 |
P |
1523*404389 |
|
69 |
620629981 |
72 |
AI |
3461*179321 |
|
70 |
627253343 |
72 |
N |
prime |
|
71 |
689546903 |
72 |
AK |
277*2489339 |
|
72 |
693557633 |
72 |
AL |
211*3287003 |
|
73 |
710530043 |
60 |
X |
7507*94649 |
|
74 |
757599167 |
72 |
N |
13*58276859 |
|
75 |
764612281 |
48 |
AJ |
17*557*80749 |
|
76 |
769883761 |
72 |
S |
23*5449*6143 |
|
77 |
832047023 |
72 |
R |
17047*48809 |
|
78 |
839316707 |
60 |
X |
17*1109*44519 |
|
79 |
844627607 |
72 |
AM |
1901*444307 |
|
80 |
879092101 |
48 |
Y |
1109*792689 |
|
81 |
914079949 |
60 |
AN |
19*3491*13781 |
|
82 |
974552641 |
60 |
AN |
151*379*17029 |
|
83 |
987152869 |
60 |
U |
337*2929397 |
|
84 |
987152869 |
60 |
AR |
337*2929397 |
|
85 |
1017439067 |
48 |
M |
41*24815587 |
|
86 |
1021957141 |
72 |
AS |
prime |
|
87 |
1038777953 |
72 |
S |
prime |
|
88 |
1051180381 |
72 |
AG |
prime |
|
89 |
1077331111 |
60 |
AN |
prime |
|
90 |
1077974903 |
60 |
AN |
6637*162419 |
|
91 |
1088472887 |
72 |
AZ |
59*199*92707 |
|
92 |
1143502909 |
180 |
AT |
17*239*431*653 |
|
93 |
1156418821 |
60 |
X |
59*19600319 |
|
94 |
1161643607 |
72 |
AG |
439*2646113 |
|
95 |
1181603461 |
72 |
AG |
107*929*11887 |
|
96 |
1269436171 |
48 |
AV |
23*55192877 |
|
97 |
1316626321 |
60 |
T |
73*18035977 |
|
98 |
1329539273 |
72 |
AM |
35461*37493 |
|
99 |
1366677863 |
72 |
Z |
20269*76427 |
|
100 |
1373855461 |
72 |
AC |
11*43*2904557 |
|
101 |
1452979757 |
60 |
AW |
prime |
|
102 |
1460644561 |
60 |
X |
prime |
|
103 |
1471655687 |
72 |
AL |
79*193*263*367 |
|
104 |
1502556901 |
72 |
AX |
101*14876801 |
|
105 |
1550990453 |
72 |
AF |
61*4967*5119 |
|
106 |
1591804639 |
60 |
X |
17*37*73*34667 |
|
107 |
1642059527 |
72 |
AK |
prime |
|
108 |
1644987931 |
72 |
AF |
499*3296569 |
|
109 |
1695587059 |
144 |
AY |
prime |
|
110 |
1828217513 |
60 |
X |
677*2700469 |
|
111 |
1840951877 |
48 |
BA |
2467*746231 |
|
112 |
1850694047 |
180 |
BB |
prime |
|
113 |
1945610987 |
60 |
BC |
prime |
|
114 |
1946251501 |
60 |
AW |
prime |
Sometimes because of an overlap, a non-base value is identifed before a base value for certain Keller cycles. This explains the occasional inconsistency in the labelling of covering sets (e.g. AJ before AI, the positioning of AP, etc.).
I have created a comprehensive list of every Sierpinski number to the limit of 109. In this list, individual Sierpinski numbers are labelled according to their position in the associated Keller cycle, with base (or smallest) values given an index of 0. Generated values, that is, Sierpinski numbers obtained by using the open iteration k ® (k+2P) are not individually labelled, but simply identified by the code of their covering set.