Problema
El objetivo es, como dice el título, encontrar el enésimo primo de modo que el primo - 1 sea divisible por n.
Explicación
Aquí hay un ejemplo para que entienda la pregunta, esta no es necesariamente la forma en que debe resolverse. Simplemente como una forma de explicar la pregunta
dado 3 como entrada, primero miraríamos todos los primos
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 ...
Luego seleccionamos los primos de manera que el primo - 1 sea divisible por n (3 en este caso)
7 13 19 31 37 43 61 67 73 79 97 103 107 109 127 ...
Luego seleccionamos el enésimo término en esta secuencia
Produciríamos 19 para una entrada de 3
Nota
También podemos pensar en esto como el enésimo en la secuencia {1, n + 1, 2n + 1, 3n + 1 ... kn + 1} donde k es cualquier número natural
Casos de prueba
1 --> 2
2 --> 5
3 --> 19
4 --> 29
100 --> 39301
123 --> 102337
code-golf
number
number-theory
primes
Ando Bando
fuente
fuente
Respuestas:
05AB1E ,
98 bytes05AB1E utiliza la codificación CP-1252 .
Guardado un byte gracias a Osable
Pruébalo en línea!
Explicación
fuente
µN¹*>Dp½
que guarda un byte y acelera el cálculo.Python 2, 58 bytes
fuente
Mathematica, 48 bytes
Función sin nombre que toma un único argumento, que nombra
n
. Genera una lista de los primerosn^3
primos, selecciona los que son congruentes con 1 módulon
, luego toma eln
elemento th del resultado. Se ejecuta en varios segundos en la entrada 123.Actualmente no se sabe si siempre hay un solo primo, entre los primeros
n^3
primos, que sea congruente con 1 módulon
, mucho menosn
de ellos. ¡Sin embargo, el algoritmo puede probarse correcto (al menos para grandesn
) bajo el supuesto de la hipótesis generalizada de Riemann !fuente
Haskell,
5947 bytesEjemplo de uso:
f 4
->29
.Cómo funciona:
Editar: Gracias @Damien por 12 bytes eliminando la prueba de divisibilidad y solo mirando los múltiplos en primer lugar.
fuente
f n=[p|p<-[1,n+1..],all((<2).gcd p)[2..p-1]]!!n
Jalea , 9 bytes
Pruébalo en línea!
Cómo funciona
fuente
Java 7, 106 bytes
Sin golf:
Código de prueba:
Pruébelo aquí (el último caso de prueba da como resultado un límite de tiempo excedido en ideone)
Salida:
fuente
System.out.println
agregan principalmente para que vea qué entrada he usado para dar el resultado mostrado, y todo también se da en caso de que alguien quiera copiarlo y pegarlo en su IDE para jugar.Nasm 679 bytes (Instrucción Intel 386 cpu 120 bytes)
este no es un golfista y los resultados
fuente
En realidad , 13 bytes
Sugerencias de golf bienvenidas! Pruébalo en línea!
Ungolfing
fuente
Lisp común, 162 bytes
Uso:
Sin golf:
Algunas de esas
loop
construcciones probablemente se pueden acortar endo
bucles, pero esto es lo que tengo por ahora.fuente
MATL , 12 bytes
Pruébalo en línea!
(Para la entrada,
123
se agota el tiempo de espera en el compilador en línea, pero funciona sin conexión).Explicación
fuente
Perl,
7776 + 1 = 77 bytesUtiliza la expresión regular de prueba principal para determinar si
$p
es primo, y se asegura de que sea congruente con 1 mod de entrada (los únicos enteros no negativos por debajo de 2 son 0 y 1, pero no puede ser 0 si es primo, por lo que debe ser 1. ahorra 1 byte más==1
).fuente
(1 x++$.)!~/^(11+?)\1+$/&&($.%$_<2)&&push@a,$.while@a<$_;say$a[-1]
(es de lo que estaba hablando en mi comentario anterior). Sin embargo, la salida (de cualquiera de las versiones) parece mal durante al menos 2 y 3 ...Mathematica 44 Bytes
Muy rapido. Utiliza la idea de la "Nota"
Salida
fuente
Perl 6 ,
46 3937 bytesfuente
Java 8, 84 bytes
Golfed
Sin golf
Explicación
Solución inspirada en varias otras respuestas. La función es una lambda que espera un solo int.
los
n>1?i:2
es un truco barato porque no pude encontrar una mejor manera de considerar el caso de n = 1.Además, esta solución supera el tiempo de espera de Ideone, pero se ha probado para todos los casos de prueba. Se agota el tiempo de espera porque para reducir un par de bytes, saqué la
j<i
verificación explícita en el bucle interno. Está implicado principalmente pori%j>0
... excepto en el caso dei=1
yj=2
(la primera iteración), en cuyo caso el ciclo se ejecuta hasta que j se desborde (supongo). Entonces funciona bien para todas las iteraciones posteriores.Para una versión que no agota el tiempo, es un par de bytes más, ¡ mira aquí!
fuente
Raqueta 109 bytes
Sin golf:
Pruebas:
Salida:
fuente
Ruby 64 bytes
Llamado así:
Además, esta aplicación de línea de comandos funciona:
llamado así
pero no estoy tan seguro de cómo contar los personajes. Creo que puedo ignorar el nombre del idioma, pero tengo que incluir el
-rprime
espacio y antes del nombre del script, por lo que es un poco más corto, en 63. . .fuente
R, 72 bytes
Terriblemente ineficiente y lento, pero funciona. Lee la entrada de stdin y luego usa la
isPrime
función delnumbers
paquete para encontrar los primos. El resto es solo verificar siprime - 1
es divisible porn
.fuente
JavaScript (ES6), 65 bytes
Utiliza el probador de primidad regexp, ya que es a) 8 bytes más corto yb) menos recursivo que mi enfoque recursivo puro.
fuente
Axioma 64 bytes
¿Alguien sabe cómo escribir arriba usando secuencias de Axiom? ... algún ejemplo
Tipo: Tupla Entero no negativo
fuente