Los números primos siempre han fascinado a las personas. Hace 2300 años, Euclides escribió en sus "Elementos"
Un número primo es el que se mide solo por una unidad.
lo que significa que un primo solo es divisible por 1
(o por sí mismo).
La gente siempre ha buscado relaciones entre números primos, y ha encontrado algunas cosas bastante extrañas (como en "interesantes").
Por ejemplo, una prima de Sophie Germain es una prima p
para la que 2*p+1
también es primo.
Una prima segura es una prima p
para la que (p-1)/2
también es prima, que es exactamente la condición inversa de una prima de Sophie Germain.
Estos están relacionados con lo que estamos buscando en este desafío.
Una cadena de Cunningham de tipo I es una serie de números primos, donde cada elemento, excepto el último, es un número primo de Sophie Germain , y cada elemento, excepto el primero, es un número primo seguro . El número de elementos en esta cadena se llama longitud .
Esto significa que comenzamos con un primo p
y calculamos q=2*p+1
. Si también q
es primo, tenemos una cadena de Cunnigham de tipo I de longitud 2. Luego probamos 2*q+1
y así sucesivamente, hasta que el siguiente número generado sea compuesto.
Las cadenas de Cunningham de tipo II se construyen siguiendo casi el mismo principio, la única diferencia es que verificamos 2*p-1
en cada etapa.
Las cadenas de Cunningham pueden tener una longitud de 1 , lo que significa que ni 2 * p + 1 ni 2 * p-1 son primos. No nos interesan estos .
Algunos ejemplos de cadenas de Cunningham.
2
inicia una cadena de tipo I de longitud 5.
2, 5, 11, 23, 47
El siguiente número construido sería el 95
que no es primo.
Esto también nos dice, que 5
, 11
, 23
y 47
no inicie ninguna cadena de tipo I , porque tendría los elementos precedentes.
2
También comienza una cadena de tipo II de longitud 3.
2, 3, 5
El siguiente sería 9
, que no es primo.
Probemos con el 11
tipo II (lo excluimos del tipo I anteriormente).
Bueno, 21
sería el siguiente, que no es primo, por lo que tendríamos longitud 1 para esa "cadena", que no contamos en este desafío.
Desafío
Escriba un programa o función que, dado un número
n
como entrada, escriba / devuelva el número inicial de la enésima cadena de Cunningham de tipo I o II de al menos longitud 2 , seguido de un espacio, seguido del tipo de cadena que comienza ( I o II ), seguido de dos puntos, seguido de la longitud de ese tipo de cadena. En caso de que un primer arranque ambos tipos de cadenas (tipo I y tipo II), la cadena del tipo I se cuenta primero.Ejemplo:
2 I:5
Tenga en cuenta que eso n
podría ser parte de una cadena iniciada previamente de cualquier tipo, en cuyo caso no debería considerarse un número inicial de una cadena de ese tipo.
Veamos cómo comienza esto
Comenzamos con 2
. Como es el primer cebado, podemos estar seguros de que no hay una cadena que comience con un cebado más bajo que contenga 2
.
El siguiente número en una cadena de tipo que sería 2*2+1 == 5
. 5
es primo, por lo que ya tenemos una cadena de al menos longitud 2.
Contamos eso como la primera cadena. ¿Qué pasa con el tipo II? El siguiente número sería 2*2-1 == 3
. 3
es primo, por lo que una cadena de al menos longitud 2 para el tipo II también.
Contamos eso como la segunda cadena. Y hemos terminado 2
.
Siguiente primo es 3
. Aquí deberíamos verificar si es en una cadena que comenzó un cebado inferior.
Compruebe si el tipo I: (3-1)/2 == 1
. 1
no es primo, por lo que 3 podría ser un punto de partida para una cadena de tipo I.
Vamos a ver eso. El siguiente sería 3*2+1 == 7
. 7
es primo, por lo que tenemos una cadena de tipo I de al menos longitud 2. Contamos eso como la tercera cadena.
Ahora verificamos si 3
aparece en una cadena tipo II que comenzó un cebado inferior.
(3+1)/2 == 2
. 2
es primo, por lo que 3 no puede considerarse como un número inicial para una cadena de tipo II. Por lo tanto, esto no se cuenta, incluso si el siguiente número después 3
en esta cadena, que sería5
, es primo. (Por supuesto, eso ya lo sabíamos, y usted puede y debe, por supuesto, pensar en su propio método para hacer estas comprobaciones)
Y así, comprobamos por 5
, 7
,11
y así sucesivamente, a contar hasta que nos encontramos con la cadena de Cunningham n de al menos 2 de longitud.
Luego (o tal vez algún tiempo antes ;)
) necesitamos determinar la longitud completa de la cadena que encontramos e imprimir el resultado en el formato mencionado anteriormente.
Por cierto: en mis pruebas no he encontrado ningún primo además de 2
que comenzó ambos tipos de cadenas con una longitud mayor que1
.
Ejemplos de entrada / salida
Entrada
1
Salida
2 I:5
Entrada
10
Salida
79 II:3
Entrada
99
Salida
2129 I:2
Las salidas para las 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
Una lista de las primeras 5000 salidas se puede encontrar aquí .
Este es el código de golf. El espacio en blanco arbitrario está permitido en la salida, pero el tipo y los números deben estar separados por un solo espacio y dos puntos como se ve en los ejemplos. No se permite el uso de escapatorias, especialmente obtener los resultados de la web no está permitido.
Buena suerte :)
fuente
2
y3
son los únicos números primosp
para los que tanto2p-1
y2p+1
son números primos, por lo que2
es el único primer cuales comienza cadenas Cunningham no triviales de ambos tipos.:)
2
con una longitud de cadena doble mayor que 1. Aquí hay una prueba de eliminación.Respuestas:
Javascript,
236208bytes28 bytes guardados:
Se guardaron 9 bytes en la
p
función con:p=(n,i=n)=>n%--i?p(n,i):i==1
La
t
función fue reemplazada por laeval(...)
instrucción directamente en laf
función.Solución previa:
Ejemplo:
f(6)
Salida:
29 I:2
Explicación
Estoy usando 3 funciones
1 p : para saber si n es primo:
p=n=>{for(i=n;n%--i&&i;);return 1==i}
2 t : para conocer la longitud de la cadena de Cunningham comenzando con n de tipo I o II dependiendo del parámetro m que será 1 o -1:
t=(n,m)=>{for(j=1;p(n=2*n+m);j++);return j}
3 f : cuenta las cadenas ( para bucle ) y luego muestra el resultado
for loop : para cada número, la cadena Cunningham (I luego II si es necesario) es válida si
fuente