Generalisation of the Cunningham Chain
A Cunningham chain of the first kind is a sequence of primes generated by the transformation p ® 2p +1, and a Cunningham chain of the second kind is the related sequence generated by p ® 2p - 1.
Cunningham chains occur naturally among primes of the form k*2n ± 1 for a particular k, where those of the first kind are of the form k*2n - 1 and those of the second kind are of the form k*2n +1. When primes are denoted in these forms they are known as Robinson primes or Proth primes.
I had been looking for a natural generalisation of the concept of Cunningham chains. From the definitions given above, the most obvious step is to consider transformations of the form p ® ap ± 1 for some a > 2. It is obvious that a must be even. A self-imposed restriction, in order to take advantage of various theoretical and practical properties, is that any generalisation should still be allowed to occur naturally amongst Proth primes, which leads us to consider a = 2m for m > 1.
Now, suppose p = k*2n +1. Then ap = 2m(k*2n +1) = k*2m+n + 2m. The only way to ensure that this remains a Proth prime based on k is to subtract (2m - 1) rather than just 1. Similarly, if p = k*2n - 1, ap = k*2m+n - 2m and we must add (2m - 1) to keep to the desired form. Therefore we consider the transformation p ® 2m*p ± (2m - 1) as our generalisation, where we have generalised Cunningham chains of the first or second kind depending on the sign. Restricting the transformation to m = 1 returns us to the standard case.
Although these new transformations seem unwieldy, in fact they can be easily depicted. For instance, a standard Cunningham chain of the second kind is of the form k*2n +1, k*2n+1 +1, k*2n+2 +1, etc. A generalised Cunningham chain of the second kind is simply of the form k*2n +1, k*2n+m +1, k*2n+2m +1, etc. In other words, the exponents form an arithmetic progression with difference m.
In the case of generalised chains of the second kind, I have readily available lists of all Proth primes for k < 105 and n £ 4000 in which to search.
Initially, let us consider k < 1000. Within this range, the first standard Cunningham chain of length 4 starts at 645*24 +1 and the first of length 5 starts at 765*21 +1. In fact, there are only 6 chains with k < 1000 of length 4 and 2 of length 5. On the other hand, there are 164 generalised chains of length 4 in this small range, the first one being 11*21 +1, 11*23 +1, 11*25 +1, 11*27 +1, with m = 2 of course. For k < 1000, there are 23 generalised chains of length 5, the smallest of which is the rather startling sequence starting at 67*2214 +1 and with m = 128 (most of these chains have n < 20). There are also 3 generalised chains of length 6, the smallest starting at 231*25 +1 and with m = 2.
Most occurrences of generalised chains of length 3 or more have even m, which is the most obvious way to avoid divisibility by 3. However, another way to avoid divisibility by 3 is for k to divide 3, and this allows chains of length at least 3 with odd m to exist. The first generalised chain of the second kind of length 4 with odd m starts at 75*21 +1 and has m = 3. The first of length 5 and odd m, excluding the m = 1 case, starts at 765*25 +1 and has m = 5.
From now one, for convenience I will represent a generalised Cunningham chain (of the second kind) starting at k*2n +1, with difference m and length s by the combination (k,n,m,s). For example, (k,n,1,2) signifies a Cunningham pair and (k,n,1,s) represents a Cunningham chain of length s.
Of particular interest is the case n = m, if for no other reason than symmetry. The first occurrence of a chain of length 4 of this type occurs for k = 37 and n = m = 4, i.e. the sequence 37*24 +1, 37*28 +1, 37*212 +1, 37*216 +1. The first chain of length 5 of this type is (663,6,6,5).
Let us now consider extending the range to all k < 100000. It's not long before we discover the first generalised chain of length 7, namely (1467,2,2,7), and there are 14 such chains in the range. The earliest chains of length 6 and 7 with m odd are (2025,1,3,6) and (5775,1,3,7). The symmetric chain (8325,1,1,7) covers the first such occurrence for lengths 6 and 7. For completeness, there are 6990 chains of length 4, 798 of length 5 and 117 of length 6, there being no chains of length 8 discovered.
More generally, and as an extension of the record searches for m = 1, for each m, it is of interest to find the largest known (with respect to the exponent n) generalised chain for each length s > 2. For example, we have
(73305,88,1,4)
(59565,170,2,4)
(9705,75,3,4)
(60137,603,4,4)
(11715,232,5,4)
etc.
Also of interest is to find, for each length, the largest in terms of n regardless of m. At present, for lengths 4 up to 7, we have (89233,1184,468,4), the aforementioned (67,214,128,5), (41457,80,30,6) and (7545,13,6,7).
The largest symmetric chains of length 4 and 5 are (36465,58,58,4), (50925,15,15,5) respectively, while the chain (51315,6,6,7) contains the largest chain of length 6 as well as that of length 7.
I have concentrated on chains of length at least 4 above, since chains of length 3 occur excessively, and most often as a result of sheer statistical likelihood. In fact, there are 1814 with k < 1000 and a total of 112853 for k < 100000. For the record, the largest is (55155,3759,99,3). However, there are a few additional effects worth noting:
1) There is a large occurrence of pairs of chains of the form (k,n,m,3) and (k,n,2m,3). In fact, there are notable occurrences of triples of chains of the form (k,n,m,3); (k,n,2m,3) and (k,n,am,3) where a = 3 or 4. For example, we have
a = 3: at least 93 occurrences starting with
(233,1,4,3); (233,1,8,3) and (233,1,12,3)
(1467,2,2,3); (1467,2,4,3) and (1467,2,6,3)
and largest
(51416,56,2,3); (51416,56,4,3) and (51416,56,6,3)
a = 4: at least 539 occurrences starting with
(99,2,20,3); (99,2,40,3) and (99,2,80,3)
(135,2,2,3); (135,2,4,3) and (135,2,8,3)
and largest, an amazing
(77115,932,33,3), (77115,932,66,3) and (77115,932,132,3)
with plenty more of this type for higher values of a, some largest values being
a = 5: (52969,138,4,3), (52969,138,8,3) and (52969,138,20,3)
a = 6: (32235,52,2,3), (32235,52,4,3) and (32235,52,12,3)
a = 7: (48393,142,2,3), (48393,142,4,3) and (48393,142,14,3)
Interestingly there is only one occurrence for a = 8 at
(71225,9,2,3); (71225,9,4,3) and (71225,9,16,3).
Other notable groups include:
(165,1,1,3); (165,1,2,3); (165,1,4,3); (165,1,8,3); (165,1,16,3) and (165,1,32,3)
2) There are many occurrences such as of the form (k,n,m,3) and (k,n,m+1,3) such as
(21,1,3,3) and (21,1,4,3)
(39,1,1,3) and (39,1,2,3)
(81,5,10,3) and (81,5,11,3)
(97335,162,19,3) and (97335,162,20,3)
or even
(261,1,2,3), (261,1,3,3) and (261,1,4,3)
(3063,2,2,3), (3063,2,3,3) and (3063,2,4,3)
(4935,10,1,3), (4935,10,2,3) and (4935,10,3,3)
(51051,55,40,3), (51051,55,41,3) and (51051,55,42,3)
3) There are many occurrences such as of the form (k,n,m,3) and (k,m,n,3) such as
(561,1,7,3) and (561,7,1,3)
(687,2,4,3) and (687,4,2,3)
(1765,70,100,3) and (1765,100,70,3)
4) In the n = m case for s = 3, how large a value of n can we get ? In the range under consideration, the largest is (80655,843,843,3)
Comments on where to go from here would be greatly appreciated.