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.

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

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 by-product 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 3-component 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.