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 :)
2
and3
are the only primesp
for which both2p-1
and2p+1
are primes, so2
is the only prime which starts non-trivial Cunningham chains of both types. \$\endgroup\$:)
\$\endgroup\$2
with a dual chain length greater than 1. Here is a proof by elimination. \$\endgroup\$