Contando cadeias de Cunningham

14

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 :)

Cabbie407
fonte
3
Esqueci de mencionar na caixa de areia: é fácil provar isso 2e 3são os únicos números primos ppara os quais ambos 2p-1e 2p+1são números primos, assim 2como o único número primo que inicia cadeias não triviais de Cunningham dos dois tipos.
Peter Taylor
OK. Obrigado pela sua ajuda:)
Cabbie407
3
(Comentário convertido da resposta.) Não números primos além de 2um comprimento de cadeia dupla maior que 1. Aqui está uma prova por eliminação.
pbeentje
Bem, obrigado por apontar isso com mais detalhes novamente. Você só queria comentar isso ou acha que devo mudar o desafio de alguma forma por causa disso?
precisa saber é o seguinte
Apenas uma observação. Eu não acho que isso mude o desafio de qualquer forma, apenas potencialmente útil para o golfe: quando uma corrente é encontrada, a outra não precisa ser verificada.
pbeentje 25/09

Respostas:

2

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
Hedi
fonte