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 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
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.
11 for type II (we excluded it from type I earlier).
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.
Write a program or function that, given a number
nas 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.
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
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
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
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
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.
3are the only primes
pfor which both
2p+1are primes, so
2is the only prime which starts non-trivial Cunningham chains of both types. \$\endgroup\$
2with a dual chain length greater than 1. Here is a proof by elimination. \$\endgroup\$