Problems & Puzzles:
Problems
Problem 26. The earliest Cunningham Chains.
Stimulated by the excellent page of Warut
Roonguthai about the Cunningham Chains(*)
I propose the following questions:
1. First Kind, the
earliest chain for each length.
Length 
Digits 
N
(initial prime) 
Author 
Year 
1 
1 
7 


2 
1 
3 


3 
2 
11 


4 
1 
5 


5 
1 
1 


6 
2 
89 


7 
7 
1122659 
D.
H. Lehmer 
? 
8 
8 
19099919 
Nelson
& Meeus 
198081 
9 
8 
85864769 
Gunther
Löh 
1989 
10 
11 
26089808579 
Gunther
Löh 
1989 
11 
12 
665043081119 
Gunther
Löh 
1989 
12 
12 
554688278429 
Gunther
Löh 
1989 
13 
16 
4090932431513069 
Jack
Brennen 
1998 
14 
17 
95405042230542329 
Paul Jobling 
Oct. 28, 1999 
15 
22
21

4678714760875524493409
2213336799116965210259 the earliest? Not because of the next one
by Carmody113220800675069784839 
Tony Forbes
Carmody 2001 
Set. 2003
Oct. 2003 
16 
21 
810433818265726529159 
Carmody & Jobling 
Oct. 2003 
Questions:
1. Find a 1^{st}
kind Cunningham Chain of length = 14, less than the
Forbes one, or  better  the earliest one.
2. Find a 1^{st}
Cunningham Chain of length => 15
2. Second Kind, the earliest for each
length
Length 
Digits 
N
(Initial prime) 
Author 
Year 
1 
1 
5 


2 
1 
2 


3 
2 
19 


4 
4 
2131 


5 
4 
1531 


6 
5 
33301 


7 
5 
16651 
D.
H. Lehmer 
? 
8 
8 
15514861 
Lalout
& Meeus 
198081 
9 
9 
857095381 
Gunther
Löh 
1989 
10 
12 
205528443121 
Gunther
Löh 
1989 
11 
13 
1389122693971 
Gunther
Löh 
1989 
12 
15 
216857744866621 
Gunther
Löh 
1989 
13 
15 
758083947856951 
Gunther
Löh 
1989 
14 
18 
107588900851484911 
Paul Jobling 
Oct. 28, 1999 
15 
17 
69257563144280941 
Paul Jobling 
Oct. 28, 1999 
16 
19 
3203000719597029781
earliest? 
Tony
Forbes 
1997 
Questions:
3. Find
a 2nd kind Cunningham Chain of length 14, 15 & 16
less than the Forbes respective records, or 
better  the earliest ones.
4. Find
a 2nd kind Cunningham Chain of length =>17.
Other questions:
5. Can
you argue if exist a Cunningham Chain for any desired
length?
6.
Regarding the digits D of the initial prime of the
earliest chain of length L, what can you conjecture about
D/L as L > infinite? Do you think that D/L remains
close to 1?
Last question:
Warut provides a tip to get
Carmichael numbers related to Cunningham chains of 2^{nd}
kind and Length 2
"
Since k must be divisible by 3, you can use step = 6 and
start with k that is an odd multiple of 3…, When you
find a chain of length 2 of the second kind {k.2^n+1,
k.2^(n+1)+1} (e.g. as a byproduct of your search for a
chain of length 3 of the second kind), try checking the
primality of 3k.2^n+1. if it is prime, then the product
(k.2^n+1)(k.2^(n+1)+1)(3k.2^n+1) will be a 3component Carmichael number of the form (6m+1)(12m+1)(18m+1)…"
Small examples are (k, n) = (3, 1); (9, 2); (15, 9);
(21, 4), ..., (4933320, 501) etcetera.
7. Would
you like to find larger examples?
Solution:
Paul
Jobling sent (28/10/99) the
earliest CC1stK of L=14 and also the
earliest CC2ndK for L= 14 and L=15. Please see them in
the Tables above. Here is part of his email
communication:
"...
The code is written in C with some optimised assembler to
perform the
sieving. CCs of lengths 13 to 16 must have a first term
of the form
k*2*3*5*11*13+1, so the software only examined values of
that form.
The search for CCs of the first kind was performed on a
233 MHz Pentium II.
The search was performed at a rate of 55 million k's a
second, with a search
time of 14 days.
The search for CCs of the second kind was performed on a
500 MHz Pentium
III. The search was performed at a rate of 120 million
k's a second, with a
search time of 6 days. This was supposed to search for 14
days as well
(while I was on holiday), but it was running on a Windows
98 machine which
decided to fall over after 6 days ..."
"...let
N be the first number in the chain. Here I will just
talk about chains of the first kind, though the logical
for chains of the
second kind is exactly the same.
If 3 does not divide N+1, then 3 will divide either N, or
2N+1. So for a
chain of length 2 or more, 3 must divide N+1.
Similarly if 5 does not divide N+1, then 5 will divide
either N, 2N+1, 4N+3,
or 8N+7. So for a chain of length 4 or more, 5 must
divide N+1.
You might think that 7 would have to divide N+1, but it
turns out that if 11
and 13 divide N+1, 7 kinda sorts itself out and never
about half of the
possible chains.
So in short, for a CC of length X, you need a first term
of the form
k*(X+1)#/Y +1, where Y is made up of those numbers like
7 that sort
themselves out (17 is the next one when you get onto much
longer chains)."
_______
Notes:
(*) These sequences of primes used to
be called "Chain of nearly doubled primes"
by Lalout & Meeus, an excellent descriptive
denomination.
