Cunningham Chains

A Cunningham chain is a sequence (of length at least 2) of primes of the form p, 2p± 1, 4p± 1, etc. In particular, Cunningham chains of the first kind are sequences of the form p, 2p- 1, 4p- 1, etc. and of the second kind are sequences of the form p, 2p+1, 4p+1, etc. The first prime in a Cunningham chain of the first kind of length 2 is commonly known as a Sophie-Germain prime.

It is convenient to search for Cunningham chains amongst numbers of the form k.2^{n} ± 1, with k odd. All odd primes can be expressed in both of these forms, but there are very efficient tests for primality available when k < 2^{n}. Chains of the first kind appear naturally amongst those numbers of the form k.2^{n} - 1, and chains of the second amongst those numbers of the form k.2^{n} +1.

Immediately, we may restrict the values of k that need to be considered. Suppose k º 1 or 2 mod 3. Then, since 2^{1} º 2 mod 3 and 2^{2} º 1 mod 3, we have that k.2^{n} º 1 or 2 mod 3 depending on n. In either case, for any two consecutive n, either k.2^{n} + 1 or k.2^{n} - 1 is divisible by 3, and so it is impossible to have a Cunningham chain. Thus k must be divisible by 3. Since k is also odd by definition, we may suppose that k º 3 mod 6.

Suppose we are interested primarily in chains of length at least 3. We know that 2^{3} º 1 mod 7 and that powers of 2 modulo 7 form a cyclic group of order 3, namely {1, 2, 4}. If k is not divisible by 7 then the numbers k.2^{n}, k.2^{n+1} and k.2^{n+2} either map directly onto this set or its negative {3, 5, 6}. In the former case, this means that k.2^{r} - 1 is divisible by 7 for r equal to one of either n, n+1 or n+2, and in the latter case, k.2^{s} +1 is divisible by 7 for s either of n, n+1 or n+2. Thus a necessary condition for chains of length at least 3 is that either k is divisible by 7 or, for chains of the first kind, k º 3, 5 or 6 mod 7, or, for chains of the second kind, k º 1, 2, or 4 mod 7. If we combine this with the earlier condition k º 3 mod 6 then for chains of the first kind we require that k º 3, 21, 27 or 33 mod 42 and for chains of the second kind we require that k º 9, 15, 21 or 39 mod 42.

Suppose we are interested in chains of length at least 4. Since 2^{4} º 1 mod 5, for any k not divisible by 5, the numbers k.2^{n}, k.2^{n+1}, k.2^{n+2}, k.2^{n+3} simply rearrange the order of the cyclic group of order 4 made up of the powers of 2 modulo 7. In particular, k.2^{r} - 1 is divisible by 5 for r equal to one of either n, n+1, n+2 or n+3 and k.2^{s} +1 is divisible by 5 for s either n, n+1, n+2 or n+3. Thus in order to have chains of length at least 4, k must be divisible by 5. Combined with the condition k º 3 mod 6, this becomes k º 15 mod 30, and combined with the condition relating to divisibility by 7 outlined above, this means that for chains of the first kind of length at least 4, we require k º 45, 75, 105 or 195 mod 210 and for the second kind, we require k º 15, 105, 135 or 165 mod 210.

Similar arguments can be developed for larger primes. In particular, analogously to the prime 5 above, if p is a primitive root to the base 2 (i.e. the exponent of p to base 2 is p- 1) then in order to have a Cunningham chain of the first or second kind of length at least p- 1, k must be divisible by p. This includes p = 3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67 and 83 for p less than 100. Other primes, such as p = 7, 17, 23, 31, 41, 43, 47, 71, 73, 79, 89 and 97 for p less than 100, can reduce the values of k to be considered only by e/p where e is the exponent of p to the base 2.

Warut Roonguthai's website reports on Cunningham chains. The record is a chain of the second kind of length 16. The longest chain of the first kind has length 14. Both of these were found by Tony Forbes. However, these values, and all other examples of length 4 or greater have first exponent no larger than n = 5, with very large k values. In the following searches for long Cunningham chains, we shall attempt to minimise k and maximise n for which chains of a certain length exist. At this stage we introduce the notation 1C and 2C to refer to chains of the first and second kind respectively.

For completeness, the largest 1C of length 2 starts at 18458709.2^{32611} - 1 (Charles Kerchner) and the largest 2C of length 2 starts at 16769025.2^{34071} +1 (Henri Lifchitz). The largest 1C of length 3 starts at 115566729.2^{4319} - 1 (Warut Roonguthai) and the largest 2C of length 3 starts at 734257203.2^{5000} +1 (also Roonguthai).

Yves Gallot's program proth.exe has a setting that speeds up the search for chains of length at least 3 by trial dividing for 3 consective exponent values at a time. In this way, values of k with high Nash weights can be considered over large exponent ranges comparatively quickly. However, for small exponent values, there is a large quantity of data produced, much of it duplicated, and for this reason it is appropriate to use a tidier method. An Ultrabasic program was written to search for chains of arbitrary length. Initially we consider k < 10^{6}, and with a limit of 32 on the lowest value of exponent in a chain. This provides the following:

2-chains

1C: for n = 1 & 2: k = 3, 15, 21, 27, 45, 57, 87 (less than 100)

for n = 2 & 3: k = 1, 33, 63

for n = 3 & 4: k = 93

for n = 4 & 5: k = 15, 27, 57, 69, 99

larger values: k = 45, n = 8 & 9

k = 45, n = 14 & 15

k = 45, n = 28 & 29

k = 51, n = 9 & 10

k = 57, n = 25 & 26

2C: for n = 1 & 2: k = 1, 3, 9, 15, 39, 69, 99 (less than 100)

for n = 2 & 3: k = 57

for n = 3 & 4: k = 75

for n = 4 & 5: k = 21, 63, 81

larger values: k = 15, n = 9 & 10

k = 21, n = 16 & 17

k = 27, n = 19 & 20

k = 33, n = 21 & 22

3-chains

1C: for n = 1 to 3: k = 3, 21, 45, 255, 615, 705, 741, 945, 951 (less than 1000)

for n = 2 to 4: k = 363, 453, 483, 675, 873, 885

for n = 3 to 5: k = 129, 189, 489

larger values: k = 45, n = 14, 15, 16

k = 75, n = 18, 19, 20

2C: for n = 1 to 3: k = 9, 39, 165, 219, 249, 309, 639, 765 (less than 1000)

for n = 2 to 4: k = 207, 267, 777, 795

for n = 3 to 5: k = 261, 471, 855, 921, 945

larger values: k = 207, n = 14, 15, 16

k = 225, n = 12, 13, 14

k = 231, n = 11, 12, 13

2-chains are very common and the records for these have n well in excess of 30000. 3-chains are obviously much rarer, but for small n do occur in substantial quantities. For instance, for k less than 10^{6} there are 1044, 770 and 656 3-chains of the first kind and 1036, 780 and 662 3-chains of the second kind, respectively beginning at n = 1, 2 and 3.

4-chains

1C: for n = 1 to 4: k = 3, 45, 255, 615, 705, 3225, 5295, 5775, 5955, 9855, 9945

for n = 2 to 5: k = 675, 885

for n = 3 to 6: k = 1515, 2145, 3435, 6705, 8925

larger values: k = 735, n = 17 to 20

k = 855, n = 17 to 20

k = 3615, n = 4 to 7

k = 3645, n = 9 to 12

k = 4185, n = 12 to 15

k = 4725, n = 14 to 17

largest value in range : 811485, n = 32 to 35

2C: for n = 1 to 4: k = 765, 1065, 1155, 3105, 3705, 7695, 8325 (less than 10000)

for n = 3 to 6: k = 855, 2265, 6825

for n = 4 to 7: k = 645, 7875

larger values: k = 975, k = 14 to 17

k = 1155, k = 17 to 20

k = 15345, k = 2 to 5

largest value in range : k = 953985, n = 32 to 35

5-chains

1C: for n = 1 to 5: k = 45, 26925, 30705, 33375, 71805, 83865, 93075 (less than 100000)

larger values: k = 735, n = 17 to 21

k = 855, n = 17 to 21

k = 3645, n = 9 to 13

k = 6705, n = 3 to 7

k = 12795, n = 10 to 14

largest value in range : k = 545445, n = 27 to 31

2C: for n = 1 to 5: k = 765, 7695, 8325, 22185, 28995, 41715, 52935, 75075 (to 100000)

larger values: k = 855, n = 3 to 7

k = 4935, n = 9 to 13

k = 4995, n = 6 to 10

k = 5565, n = 12 to 16

largest value in range : k = 781995, n = 32 to 36

6-chains

1C: k = 45, n = 1 to 6

k = 11835, n = 9 to 14

k = 15855, n = 2 to 7

k = 31785, n = 2 to 7

k = 66825, n = 4 to 9

k = 78435, n = 9 to 14

largest in range : k = 661365, n = 21 to 26

Note that k = 15855 also provides a 4-chain starting at n = 12 and so provides primes for 10 out of 15 primes for n £ 15.

2C: k = 4935, n = 9 to 14

k = 8325, n = 1 to 6

k = 29925, n = 4 to 9

k = 36135, n = 8 to 13

k = 41475, n = 2 to 7

k = 75195, n = 4 to 9

largest in range : k = 579825, n = 17 to 22

7-chains

1C: k = 280665, n = 2 to 8

k = 795255, n = 8 to 14

2C: k = 8325, n = 1 to 7

k = 41475, n = 2 to 8

k = 221055, n = 3 to 9

k = 267345, n = 6 to 12

k = 560235, n = 2 to 8

These are all the 7-chains in the range. There are no 8-chains in this range.

In fact, with a limit of 32 on the lowest exponent in the chain, there are 772 Cunningham chains of the first kind of length at least 4 for k < 10^{6} , including 11 values of k that provide more than one such chain, and there are 745 of the second kind, also including 11 values that appear more than once.

We are also interested in Bi-Chains, which are simultaneous chains of the first and second kinds with the same k values and n ranges. The smallest bi-chain is {5,7,11,13}, where k = 3 and n = 1 & 2. The largest bi-chain of length 2 (or Bi-Twin) has k = 633604755 and n = 1085 & 1086 (Roonguthai), the largest bi-chain of length 3 has k = 786756705 and n = 160 to 162 (Jack Brennen). The largest bi-chain of length 4 has k = 25378700094141989595 and n = 2 to 5, which is unsatisfactory in its values of k and n. The second largest is slightly better at k = 67427535 and n = 26 to 29. Check Henri Lifshitz website for more.

The next stage of our search pushes the lower exponent limit to 1000. The following results we obtained using Gallot's proth.exe.

1C

largest 3-chain : k = 499539, n = 819 to 821

largest 4-chain : k = 764235, n = 146 to 149

largest 5-chain : k = 888975, n = 67 to 71

largest 6-chain : k = 983685, n = 37 to 42

2C

largest 3-chain : k = 82233, n = 828 to 830

largest 4-chain : k = 828195, n = 126 to 129

largest 5-chain : k = 447615, n = 49 to 53

Pushing the exponent limit to 2000, we obtain the following larger 3-chains.

1C k = 712425, n = 1466 to 1468

2C k = 806295, n = 1032 to 1034

k = 172425, n = 1246 to 1248

For chains longer than 3 exponents, we are interested in the largest in terms of exponent n and lowest in terms of k. The following results were obtained primarily using Ultrabasic routines to filter for possible chains and output these in the form of lists of k & n. Then either Gallot's proth.exe or Nash's primeform.exe was used to test for primality using the File setting. The output was then collated using Unix scripts to isolate individual chains.

4-chains

k = 1154055, n = 373 to 376

k = 1091775, n = 513 to 516

k = 9423795, n = 637 to 640

limit : n £ 1000, k < 10^{7}

5-chains

k = 1562895, n = 80 to 84

k = 1892595, n = 81 to 85

k = 14996085, n = 99 to 103

k = 9495225, n = 145 to 149

k = 11309835, n = 179 to 183

k = 18424845, n = 196 to 200

limit : n £ 500, k < 10^{7}

n £ 200, k < 2*10^{7}

6-chains

k = 1783575, n = 41 to 46

k = 36557115, n = 42 to 47

k = 36504075, n = 43 to 48

k = 23001975, n = 44 to 49

k = 55462575, n = 45 to 50

k = 58070085, n = 47 to 52

k = 89277705, n = 54 to 59

k = 12669765, n = 88 to 93

limit : n £ 200, k < 10^{7}

n £ 100, k < 10^{8}

7-chains

k = 4758705, n = 13 to 19

k = 660075045, n = 23 to 29

k = 322831575, k = 28 to 34

k = 1783575, n = 40 to 46

limit : n £ 100, k < 10^{8}

8-chains

k = 26277285, n = 1 to 8 (first occurrence with n starting at 1)

k = 1960335, n = 3 to 10

k = 1193745, n = 4 to 11

k = 21440835, n = 6 to 13

k = 82921845, n = 22 to 29

k = 649691955, n = 24 to 31

k = 887539785, n = 25 to 32

limit : n £ 30, k < 10^{9}

n £ 100, k < 10^{8}

9-chains

k = 42932385, n = 1 to 9

k = 49619895, n = 2 to 10

k = 76298145, n = 2 to 10

limit : n £ 30, k < 10^{8}

2C

4-chains

k = 1122615, n = 181 to 184

k = 2683095, n = 397 to 400

k = 2130975, n = 420 to 423

k = 4865835, n = 493 to 496

limit : n £ 700, k < 2*10^{6}

5-chains

k = 1267785, n = 76 to 80

k = 3922485, n = 81 to 85

k = 6769365, n = 83 to 87

k = 3723645, n = 187 to 191

limit : n £ 200, k < 10^{7}

6-chains

k = 1893585, n = 27 to 32

k = 3499965, n = 32 to 37

k = 19433835, n = 48 to 53

k = 2354055, n = 54 to 59

k = 64848645, n = 56 to 61

k = 80655135, n = 68 to 73

k = 22825875, n = 70 to 75

limit : n £ 200, k < 10^{7}

limit : n £ 100, k < 10^{8}

7-chains

k = 2098845, n = 18 to 24

k = 21471765, n = 19 to 25

k = 39648375, n = 25 to 31

k = 63812385, n = 43 to 49

limit : n £ 100, k < 10^{8}

8-chains

k = 3878717, n = 2 to 9

k = 52350375, n = 4 to 11

k = 33203115, n = 24 to 31

limit : n £ 30, k < 10^{8}

The following results were obtained using Ultabasic routines only.

Bi-Chains

2-chain s

k = 855, n = 10 & 11

k = 735, n = 20 & 21

k = 5385, n = 39 & 40

k = 205005, n = 41 & 42

k = 62265, n = 47 & 48

k = 505365, n = 48 & 49

k = 905145, n = 53 & 54

k = 417615, n = 54 & 55

k = 9285, n = 77 & 78

k = 150945, n = 80 & 81

k = 326445, n = 97 & 98

k = 150945, n = 100 & 101

k = 130455, n = 182 & 183

k = 730425, n = 245 & 246

k = 460485, n = 380 & 381

limit : n £ 1000, k < 10^{6}

n = 201-500, k < 1.8*10^{6}

3-chains

k = 3885, n = 6 to 8

k = 762405, n = 8 to 10

k = 765765, n = 10 to 12

k = 791175, n = 11 to 13

k = 4601835, n = 19 to 21

k = 2705115, n = 22 to 24

k = 17319645, n = 30 to 32

k = 24399375, n = 33 to 35

k = 55692945, n = 35 to 37

k = 57768165, n = 49 to 51

limit : n £ 200, k < 10^{8}

4-chains

k = 569415, n = 1 to 4

k = 15855, n = 4 to 7

k = 765765, n = 9 to 12

k = 67427535, n = 26 to 29

limit : n £ 200, k < 10^{8}

n = 30-50, k < 10^{9}