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 1980-81 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 1st kind Cunningham Chain of length = 14, less than the Forbes one, or - better - the earliest one.

2.- Find a 1st 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 1980-81 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 2nd 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.

 Records   |  Conjectures  |  Problems  |  Puzzles