La tarea en cuestión es, dado un número n
, encontrar el primo más pequeño que comienza con AL MENOS n
el número 2
al comienzo del número. Esta es una secuencia que encontré en OEIS ( A068103 ).
Los primeros 17 números en la secuencia se dan a continuación, si desea más, tendré que implementar la secuencia, lo cual no me importa hacer.
0 = 2
1 = 2
2 = 223
3 = 2221
4 = 22229
5 = 2222203
6 = 22222223 # Notice how 6 and 7 are the same!
7 = 22222223 # It must be **AT LEAST** 6, but no more than necessary.
8 = 222222227
9 = 22222222223 # Notice how 9 and 10 are the same!
10 = 22222222223 # It must be **AT LEAST** 9, but no more than necessary.
11 = 2222222222243
12 = 22222222222201
13 = 22222222222229
14 = 222222222222227
15 = 222222222222222043
16 = 222222222222222221
Solo pensé que sería una combinación genial de manipulación de cuerdas, detección principal y secuencias. Este es el código de golf , el conteo de bytes más bajo será declarado ganador probablemente a finales de mes.
x
. Por ejemplo, si su idioma solo admite enteros de 32 bits, puede explicarlo.Respuestas:
Brachylog ,
1211 bytesPruébalo en línea!
Esto se traduce en Brachylog sorprendentemente directamente. Esta es una función, no un programa completo (aunque dar al intérprete
Z
como un argumento de línea de comandos hace que agregue el contenedor apropiado para convertir la función en un programa; eso es lo que hice para que el enlace TIO funcione). También es bastante desafortunado quej
parezca estar indexado en -1 y necesita una corrección para permitir eso.Puede hacer un argumento razonable de que
=
no es necesario, pero creo que, dada la forma en que está redactado el problema, lo es; sin, la función describe el conjunto de todos los números primos que comienzan con el número dado de2
s, y sin alguna declaración explícita de que el programa debe hacer algo con esta descripción (en este caso, generar el primer valor), probablemente no cumplir con las especificacionesExplicación
Cuando se usa como una función que devuelve un entero, nada solicita valores más allá del primero, por lo que lo primero es de lo que debemos preocuparnos.
Una sutileza (señalada en los comentarios):
:Acb
yb:Ac
son matemáticamente equivalentes (ya que una se elimina desde el principio y la otra se agrega al final, con la región intermedia nunca superpuesta); Anteriormenteb:Ac
, lo que es más natural, pero se rompe en la entrada 0 (lo que supongo es porque sec
niega a concatenar una lista vacía a cualquier cosa; muchas de las compilaciones de Brachylog tienden a romperse en listas vacías por alguna razón).:Acb
asegura quec
nunca tenga que ver una lista vacía, lo que significa que el caso de la entrada 0 ahora también puede funcionar.fuente
0
ninguna razón aparente (Brachylog parece ser alérgico a los ceros por alguna razón; sospecho quec
es el responsable). Dicho esto, es bastante fácil de arreglar, así que lo arreglaré ahora.b:Ac
no funciona porque para la entrada0
que obtienes2b:Ac
:2b
da0
y no puedes usarc
con un cero inicial. La razón de esto es evitar bucles infinitos en el caso general en el que siempre se puede anteponer un cero y obtener los mismos resultados.:2rj
lugar de,2:?j
r
; eso es solo una simple mejora. Entiendo lo que está sucediendoc
(no desea infinitos resultados cuando se ejecuta hacia atrás); sin embargo, una mejora probable es no permitir entradas degeneradas solo si no están vinculadas, mientras que las permiten cuando la entrada ya está vinculada a un valor degenerado.Java (OpenJDK 8) ,
164110 bytes¡Gracias a @FryAmTheEggman por un montón de bytes!
Pruébalo en línea!
fuente
new String(new char[i]))
hace una cadena unaria de longitud igual al número. Luego, la expresión regular coincide con un número compuesto al verificar si la repetición de un conjunto de dígitos se ajusta a toda la cadena (básicamente división de prueba). Si estoy en lo cierto, eso significa que deberías poder jugar golf la segunda parte para no tener un?
, te lo haré saber cuando llegue a una computadora.Pyth, 12 bytes
En pseudocódigo:
Repite el
lambda
inicio desdeT=1
, aumentando en 1 hasta que se cumpla la condición. La cadena de2
s debe ser una subcadena desde el principio de la cadena, es decir, el método de índice debe regresar0
. Si no se encuentra la subcadena, regresa, lo-1
que convenientemente también es verdadero, por lo que no existe un caso excepcional.Puede probarlo en línea aquí , pero el servidor solo permite una entrada de
4
.fuente
Perl, 50 bytes
49 bytes de código +
-p
bandera.Proporcione la entrada sin nueva línea final. Por ejemplo:
Esto toma un tiempo para ejecutar un número mayor que 4, ya que prueba cada número (hay 2 pruebas: la primera
/^2{$_}/
verifica si hay suficientes 2 al principio, y la segunda(1x$\)!~/^1?$|^(11+)\1+$/
prueba la primalidad (con desempeños muy pobres)).fuente
Haskell, 73 bytes
Ejemplo de uso:
f 3
->2221
.Fuerza bruta.
[1..n]>>"2"
crea una lista den
2
s que se compara con los primerosn
caracteres en la representación de cadena del primo actual.fuente
Mathematica, 103 bytes
Función sin nombre que toma un argumento entero no negativo
#
y devuelve un entero. Literalmente prueba todos los enteros positivos a su vez hasta que encuentra uno que comienza con#
2 y es primo. Horriblemente lento para entradas superiores a 5.resultado anterior: Mathematica, 155 bytes
Mathematica sería mejor para jugar al golf si no estuviera tan bien escrito; tenemos que cambiar explícitamente de un lado a otro entre tipos enteros / listas / cadenas.
Este algoritmo opera en listas de dígitos , extrañamente, comenzando con
{2,...,2,1}
. Mientras esos no sean los dígitos de un número primo, agrega uno al último dígito, utilizando la regla{j___,k_}/;!PrimeQ@d@{j,k}:>({j,k+1}
... y luego implementa manualmente llevar el uno al siguiente dígito siempre que cualquiera de los los dígitos equivalen a 10, usando la regla{a__,b_,10,c___}->{a,b+1,0,c}
... y luego, si hemos ido tan lejos que el último de los2
s principales se ha convertido en a3
, comienza de nuevo con otro dígito al final, usando la regla{a,b+1,0,c}/.{a:Repeated[2,#-1],3,b:0..}->{a,2,0,b}
. Al/. 23->2
final solo se soluciona el caso especial donde la entrada es1
: la mayoría de los números primos no pueden terminar2
, pero2
sí. (Se esparcen algunos errores en las entradas0
y1
, pero la función encuentra la respuesta correcta).Este algoritmo es bastante rápido: por ejemplo, en mi computadora portátil toma menos de 3 segundos calcular que el primer cebado que comienza con 1,000
2
s es22...220521
.fuente
Pyth, 17 bytes
Parece que no se puede resolver en
n = 4
línea, pero es correcto en teoría.Explicación
fuente
Perl 6 , 53 bytes
Intentalo
Expandido:
fuente
Jalea , 14 bytes
Muy ineficiente Pruébalo en línea!
fuente
Pyke, 14 bytes
Pruébalo aquí!
12 bytes después de la corrección de errores y una nueva característica
Pruébalo aquí!
fuente
Salvia,
6968 bytesUtiliza un generador para encontrar el primero (por lo tanto, el más pequeño) de infinitos términos.
fuente
Japt, 20 bytes
¡Pruébelo en línea! Termina en dos segundos en mi máquina para todas las entradas hasta 14, y después de eso, naturalmente, pierde precisión (JavaScript solo tiene una precisión entera de hasta 2 53 ).
Muchas gracias a @obarakon por trabajar en esto :-)
Explicación
En la última versión de Japt, esto puede ser de 12 bytes:
¡Pruébelo en línea! Termina en medio segundo en mi máquina para todas las entradas hasta 14.
fuente
2222203
, solo222223
y poco después2222210
. También falla en cualquier entrada que requiera tres o más dígitos adicionales después de la cadena de2
s, como la entrada 15.PHP, 76 bytes
toma información del argumento de la línea de comando. Corre con
-r
.Descompostura
fuente
Bash (+ coreutils), 53 bytes
Funciona hasta 2 ^ 63-1 (9223372036854775807) , toma un tiempo considerable para terminar para N> 8.
Golfed
Prueba
fuente
Python 3, 406 bytes
código de prueba
salida de prueba
Decidí ir por la velocidad en un rango bastante grande, en lugar de un tamaño de byte. :) Utilizo una prueba determinista de primalidad de Miller-Rabin que está garantizada hasta 3317044064679887385961981 con este conjunto de testigos. Los primos más grandes siempre pasarán con éxito la prueba, pero algunos compuestos también pueden pasar, aunque la probabilidad es extremadamente baja. Sin embargo, también probé los números de salida para i> 22 usando pyecm un programa de factorización de curva elíptica, y parecen ser primos.
fuente
p()
alinear la llamada ... OTOH, sería difícil escribir un programa significativamente más pequeño que pueda dar salida correcta para i> 20 en menos de un segundo (eso no "engaña" llamando a un incorporado corrector de primalidad). :)Python 3, 132 bytes
Cualquier esperanza de rendimiento se ha sacrificado por un recuento de bytes más pequeño.
fuente
Java, 163 bytes
código de prueba
salida:
582.5858 milisegundos
Explicación: recorre los números enteros y los agrega como cadenas a la cadena raíz, que es la cadena de "2" dada, y verifica si es primo o no.
fuente
isProbablePrime
tiene falsos positivos ocasionales . Eso invalidaría la respuesta, ya que hay circunstancias en las que devuelve el valor incorrecto.