Counting Cunningham chains

Question

Prime numbers have always fascinated people. 2300 years ago Euclid wrote in his "Elements"

A prime number is that which is measured by a unit alone.

which means that a prime is only divisible by 1 (or by itself).

People have always looked for relations between prime numbers, and have come up with some pretty weird (as in "interesting") stuff.

For example a Sophie Germain prime is a prime p for which 2*p+1 is also prime.

A safe prime is a prime p for which (p-1)/2 is also prime, which is exactly the backwards condition of a Sophie Germain prime.

These are related to what we are looking for in this challenge.

A Cunningham chain of type I is a series of primes, where every element except the last one is a Sophie Germain prime, and every element except the first one is a safe prime. The number of elements in this chain is called it's length.

This means that we start with a prime p and calculate q=2*p+1. If q is prime too, we have a Cunnigham chain of type I of length 2. Then we test 2*q+1 and so on, until the next generated number is composite.

Cunningham chains of type II are constructed following almost the same principle, the only difference being that we check 2*p-1 at each stage.

Cunningham chains can have a length of 1, which means that neither 2*p+1 nor 2*p-1 are prime. We're not interested in these.

Some examples of Cunningham chains

2 starts a chain of type I of length 5.

2, 5, 11, 23, 47

The next constructed number would be 95 which isn't prime.
This also tells us, that 5, 11, 23 and 47 don't start any chain of type I, because it would have preceeding elements.

2 also starts a chain of type II of length 3.

2, 3, 5

Next would be 9, which isn't prime.

Let's try 11 for type II (we excluded it from type I earlier).
Well, 21 would be next, which isn't prime, so we would have length 1 for that "chain", which we don't count in this challenge.

Challenge

Write a program or function that, given a number n as input, writes/returns the starting number of the nth Cunningham chain of type I or II of at least length 2, followed by a space, followed by the type of chain it starts (I or II), followed by a colon, followed by the length of that type of chain. In case a prime starts both types of chains (type I and type II) the chain of type I is counted first.

Example: 2 I:5

Bear in mind, that n might be part of a previously started chain of any type, in which case it shouldn't be considered a starting number of a chain of that type.

Let's look into how this begins

We start with 2. Since it is the first prime at all we can be sure that there is no chain starting with a lower prime that contains 2.
The next number in a chain of type I would be 2*2+1 == 5. 5 is prime, so we have a chain of at least length 2 already.
We count that as the first chain. What about type II? Next number would be 2*2-1 == 3. 3 is prime, so a chain of at least length 2 for type II too.
We count that as the second chain. And we're done for 2.

Next prime is 3. Here we should check if it is in a chain that a lower prime started.
Check for type I: (3-1)/2 == 1. 1 isn't prime, so 3 could be a starting point for a chain of type I.
Let's check that. Next would be 3*2+1 == 7. 7 is prime, so we have a chain of type I of at least length 2. We count that as the third chain.
Now we check if 3 appears in a type II chain that a lower prime started. (3+1)/2 == 2. 2 is prime, so 3 can't be considered as a starting number for a chain of type II. So this is not counted, even if the next number after 3 in this chain, which would be 5, is prime. (Of course we already knew that, and you can and should of course think about your own method how to do these checks.)

And so we check on for 5, 7, 11 and so on, counting until we find the nth Cunningham chain of at least length 2.

Then (or maybe some time earlier ;) ) we need to determine the complete length of the chain we found and print the result in the previously mentioned format.

By the way: in my tests I haven't found any prime besides 2 that started both types of chains with a length greater than 1.

Input/Output examples

Input

1

Output

2 I:5

Input

10

Output

79 II:3

Input

99

Output

2129 I:2

The outputs for the inputs 1..20

2 I:5
2 II:3
3 I:2
7 II:2
19 II:3
29 I:2
31 II:2
41 I:3
53 I:2
79 II:3
89 I:6
97 II:2
113 I:2
131 I:2
139 II:2
173 I:2
191 I:2
199 II:2
211 II:2
229 II:2

A list of the first 5000 outputs can be found here.

This is code golf. Arbitrary whitespace is allowed in the output, but the type and numbers should be seperated by a single space and a colon as seen in the examples. Using any loopholes is not allowed, especially getting the results from the web is not allowed.

Good luck :)

Answer 1

Javascript, 236 208 bytes

Saved 28 bytes:

p=(n,i=n)=>n%--i?p(n,i):i==1;f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:`+eval(`for(j=1;p(k=2*k+l);j++);j`))}

Saved 9 bytes on p function with: p=(n,i=n)=>n%--i?p(n,i):i==1
The t function was replaced by the eval(...) statement directly in the f function.

---

Previous solution:

p=n=>{for(i=n;n%--i&&i;);return 1==i};t=(n,m)=>{for(j=1;p(n=2*n+m);j++);return j};f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:${t(k,l)}`)}

Example: f(6)

Output: 29 I:2

Explanation
I'm using 3 functions

1 p: to know if n is prime : p=n=>{for(i=n;n%--i&&i;);return 1==i}

2 t: to know the length of the Cunningham chain starting with n of type I or II depending on the m parameter which will be 1 or -1 : t=(n,m)=>{for(j=1;p(n=2*n+m);j++);return j}

3 f: counts the chains (for loop) then display the result

f=n=>{for(k=2,c=0;c<n;k++){p(k)&&!p((k-1)/2)&&p(2*k+1)&&(c++,l=1,r='');p(k)&&c-n&&!p((k+1)/2)&&p(2*k-1)&&(c++,l=-1,r='I');};alert(--k+` I${r}:${t(k,l)}`)}

for loop: for each number the Cunningham chain (I then II if needed) is valid if

• the number is prime
• the predecessor is not prime
• the successor is prime

Answer 2

Wolfram Language (Mathematica), 182 bytes

Union[Flatten[DeleteCases[Table[c@x_:=Module[{t=0,p=Prime@k},If[PrimeQ[(p-x)/2],1,While[PrimeQ@p,p=2p+x;t++];t]];{Prime@k,If[#==1,"I","II"],c@#},{k,7!}],{a_,b_,1}]&/@{1,-1},1]][[#]]&

Try it online!