Os números primos sempre fascinaram as pessoas. 2300 anos atrás, Euclides escreveu em "Elementos"

Um número primo é aquele que é medido apenas por uma unidade.

o que significa que um primo só é divisível por 1(ou por si mesmo).

As pessoas sempre procuraram relações entre números primos e criaram coisas bem estranhas (como em "interessantes").

Por exemplo, um primo de Sophie Germain é um primo ppara o qual 2*p+1também é primo.

Um prime seguro é um primo ppara o qual (p-1)/2também é primo, que é exatamente a condição inversa de um primo da Sophie Germain.

Eles estão relacionados ao que estamos procurando neste desafio.

Uma cadeia de Cunningham do tipo I é uma série de primos, onde todos os elementos, exceto o último, são primos da Sophie Germain , e todos os elementos, exceto o primeiro, são primos seguros . O número de elementos nesta cadeia é chamado de comprimento .

Isso significa que começamos com um primo pe calculamos q=2*p+1. Se também qfor primo, temos uma cadeia Cunnigham do tipo I de comprimento 2. Então testamos 2*q+1e assim por diante, até que o próximo número gerado seja composto.

As cadeias de Cunningham do tipo II são construídas seguindo quase o mesmo princípio, a única diferença é que verificamos 2*p-1em cada estágio.

As cadeias de Cunningham podem ter um comprimento de 1 , o que significa que nem 2 * p + 1 nem 2 * p-1 são primos. Não estamos interessados ​​nisso .

Alguns exemplos de cadeias de Cunningham

2inicia uma cadeia do tipo I de comprimento 5.

2, 5, 11, 23, 47

O próximo número construído seria o 95que não é primo.
Isto também nos diz, que 5, 11, 23e 47não iniciar qualquer cadeia de tipo I , porque teria elementos precedentes.

2também inicia uma cadeia do tipo II de comprimento 3.

2, 3, 5

O próximo seria 9, o que não é primo.

Vamos tentar o 11tipo II (nós o excluímos do tipo I anteriormente).
Bem, 21seria o próximo, o que não é primo, então teríamos o comprimento 1 para essa "cadeia", que não contamos neste desafio.

Desafio

Escreva um programa ou função que, dado um número ncomo entrada, grave / retorne o número inicial da enésima cadeia Cunningham do tipo I ou II de pelo menos comprimento 2 , seguido por um espaço, seguido pelo tipo de cadeia que ele inicia ( I ou II ), seguido por dois pontos, seguido pelo comprimento desse tipo de cadeia. No caso de um primo iniciar os dois tipos de cadeias (tipo I e tipo II), a cadeia do tipo I é contada primeiro.

Exemplo: 2 I:5

Lembre-se de que isso npode fazer parte de uma cadeia iniciada anteriormente de qualquer tipo; nesse caso, não deve ser considerado o número inicial de uma cadeia desse tipo.

Vamos ver como isso começa

Começamos com 2. Como é o primeiro primo, podemos ter certeza de que não existe uma cadeia que comece com um primo mais baixo que contém 2.
O próximo número em uma cadeia do tipo que eu seria 2*2+1 == 5. 5é primo, então já temos uma cadeia de pelo menos 2.
Contamos isso como a primeira cadeia. E o tipo II? O próximo número seria 2*2-1 == 3. 3é primo, então uma cadeia de pelo menos comprimento 2 também para o tipo II.
Contamos isso como a segunda cadeia. E nós terminamos 2.

O próximo primo é 3. Aqui devemos verificar se é em uma cadeia que um primo mais baixo começou.
Verifique para o tipo I: (3-1)/2 == 1. 1não é primo, então 3 pode ser o ponto de partida para uma cadeia do tipo I.
Vamos verificar isso. O próximo seria 3*2+1 == 7. 7é primo, portanto, temos uma cadeia do tipo I de pelo menos 2. Comprimento. Contamos isso como a terceira cadeia.
Agora, verificamos se 3aparece em uma cadeia do tipo II que um prime mais baixo foi iniciado. (3+1)/2 == 2. 2é primo, então 3 não pode ser considerado como um número inicial para uma cadeia do tipo II. Portanto, isso não é contado, mesmo se o próximo número depois 3dessa cadeia, que seria5, é primo. (É claro que já sabíamos disso, e você pode e deve, é claro, pensar em seu próprio método como fazer essas verificações.)

E, assim, verificar para 5, 7, 11e assim por diante, a contagem até encontrar a cadeia Cunningham enésimo de pelo menos comprimento 2.

Então (ou talvez algum tempo antes ;)) precisamos determinar o comprimento completo da cadeia que encontramos e imprimir o resultado no formato mencionado anteriormente.

A propósito: nos meus testes, não encontrei nenhum primo além do 2que iniciou os dois tipos de correntes com um comprimento maior que 1.

Exemplos de entrada / saída

Entrada

1

Resultado

2 I:5

Entrada

10

Resultado

79 II:3

Entrada

99

Resultado

2129 I:2

As saídas para as entradas 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

Uma lista das primeiras 5000 saídas pode ser encontrada aqui .

Isso é código de golfe. O espaço em branco arbitrário é permitido na saída, mas o tipo e os números devem ser separados por um único espaço e dois pontos, como visto nos exemplos. Usando eventuais lacunas não é permitido, especialmente obtendo os resultados da web é não permitido.

Boa sorte :)

Javascript, 236 208 bytes

Salvou 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`))}

Salvou 9 bytes na pfunção com: p=(n,i=n)=>n%--i?p(n,i):i==1
A tfunção foi substituída pela eval(...)instrução diretamente na ffunção.

Solução anterior:

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)}`)}

Exemplo: f(6)

Resultado: 29 I:2

Explicação
: estou usando 3 funções

1 p : para saber se n é primo: p=n=>{for(i=n;n%--i&&i;);return 1==i}

2 t : saber o comprimento da cadeia de Cunningham começando com n do tipo I ou II, dependendo do parâmetro m que será 1 ou -1: t=(n,m)=>{for(j=1;p(n=2*n+m);j++);return j}

3 f : conta as cadeias ( loop for ) e exibe o resultado

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)}`)}

loop for : para cada número a cadeia de Cunningham (eu então II se necessário) é válida se

• o número é primo
• o antecessor não é primo
• o sucessor é primo