El primer más pequeño con un toque (A068103)

33

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 2al 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 , el conteo de bytes más bajo será declarado ganador probablemente a finales de mes.

Urna de pulpo mágico
fuente
55
¿Existe un límite inferior para la altura de una entrada que debemos admitir?
ETHproductions
1
¿Hay un límite de tiempo?
Brad Gilbert b2gills
@ETHProductions lo siento, se fue bastante rápido después de escribir este. Si debe limitar su entrada, la limitación debe respaldarse con un argumento lógico de por qué el idioma no admite números superiores a x. Por ejemplo, si su idioma solo admite enteros de 32 bits, puede explicarlo.
Magic Octopus Urn

Respuestas:

12

Brachylog , 12 11 bytes

:2rj:Acb#p=

Prué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 Zcomo 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 que jparezca 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 de 2s, 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 especificaciones

Explicación

:2rjbAcb#p=
:2rj         2 repeated a number of times equal to the input plus one
    :Ac      with something appended to it
       b     minus the first element
        #p   is prime;
          =  figure out what the resulting values are and return them

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): :Acby b:Acson 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); Anteriormente b:Ac, lo que es más natural, pero se rompe en la entrada 0 (lo que supongo es porque se cniega 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). :Acbasegura que cnunca tenga que ver una lista vacía, lo que significa que el caso de la entrada 0 ahora también puede funcionar.


fuente
@muddyfish: lo hace. Sin embargo, no funcionó por 0ninguna razón aparente (Brachylog parece ser alérgico a los ceros por alguna razón; sospecho que ces el responsable). Dicho esto, es bastante fácil de arreglar, así que lo arreglaré ahora.
b:Acno funciona porque para la entrada 0que obtienes 2b:Ac: 2bda 0y no puedes usar ccon 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.
Fatalize
Además, puede acortar esto en un byte escribiendo en :2rjlugar de,2:?j
Fatalize
Me había olvidado de r; eso es solo una simple mejora. Entiendo lo que está sucediendo c(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.
Esto definitivamente es factible y lo agregaré en el rastreador de Github. Aunque la implementación de concatenate ya tiene casi 100 líneas, lo que es mucho para un predicado Prolog.
Fatalize
15

Java (OpenJDK 8) , 164 110 bytes

a->{int i=0;for(;!(i+"").matches("2{"+a+"}.*")|new String(new char[i]).matches(".?|(..+)\\1+");i++);return i;}

¡Gracias a @FryAmTheEggman por un montón de bytes!

Pruébalo en línea!

Pavel
fuente
2
¿Podría explicar cómo funciona principalmente una comprobación de expresiones regulares?
J. Antonio Perez
No tengo idea. No es mío, y no sé quién es el creador original. Acabo de tomar una cadena de longitud n y coincide si n no es primo.
Pavel
¿Sabes cuál es la fuente original? ¿Dónde lo aprendiste? ¿Has probado tu código?
J. Antonio Perez
3
@Pavel Esa comprobación de expresiones regulares hace que esta respuesta sea increíble, incluso si no la hiciste. Debe agregar eso al hilo "Consejos para jugar al golf en Java".
Urna de pulpo mágico
3
No puedo probar el código en este momento, pero estoy bastante seguro de que la expresión regular funciona así: 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.
FryAmTheEggman
5

Pyth, 12 bytes

f&!x`T*Q\2P_

En pseudocódigo:

f                key_of_first_truthy_value( lambda T:
  !                  not (
   x`T*Q\2               repr(T).index(input()*'2')
                     )
 &                   and
          P_T        is_prime(T)
                 )

Repite el lambdainicio desde T=1, aumentando en 1 hasta que se cumpla la condición. La cadena de 2s debe ser una subcadena desde el principio de la cadena, es decir, el método de índice debe regresar 0. Si no se encuentra la subcadena, regresa, lo -1que 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.

busukxuan
fuente
4

Perl, 50 bytes

49 bytes de código + -pbandera.

++$\=~/^2{$_}/&&(1x$\)!~/^1?$|^(11+)\1+$/||redo}{

Proporcione la entrada sin nueva línea final. Por ejemplo:

echo -n 4 | perl -pE '++$\=~/^2{$_}/&&(1x$\)!~/^1?$|^(11+)\1+$/||redo}{'

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

Dada
fuente
3

Haskell, 73 bytes

f n=[x|x<-[2..],all((>0).mod x)[3..x-1],take n(show x)==([1..n]>>"2")]!!0

Ejemplo de uso: f 3-> 2221.

Fuerza bruta. [1..n]>>"2"crea una lista de n 2s que se compara con los primeros ncaracteres en la representación de cadena del primo actual.

nimi
fuente
3

Mathematica, 103 bytes

ReplaceRepeated[0,i_/;!IntegerDigits@i~MatchQ~{2~Repeated~{#},___}||!PrimeQ@i:>i+1,MaxIterations->∞]&

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.

(d=FromDigits)[2&~Array~#~Join~{1}//.{j___,k_}/;!PrimeQ@d@{j,k}:>({j,k+1}//.{a__,b_,10,c___}->{a,b+1,0,c}/.{a:Repeated[2,#-1],3,b:0..}->{a,2,0,b})]/. 23->2&

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 los 2s principales se ha convertido en a 3, 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->2final solo se soluciona el caso especial donde la entrada es 1: la mayoría de los números primos no pueden terminar 2, pero 2sí. (Se esparcen algunos errores en las entradas 0y 1, 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 2s es 22...220521.

Greg Martin
fuente
2

Pyth, 17 bytes

f&q\2{<`T|Q1}TPTh

Parece que no se puede resolver en n = 4línea, pero es correcto en teoría.

Explicación

               Th    Starting from (input)+1, 
f                    find the first T so that
      <              the first
          Q          (input) characters
         | 1         or 1 character, if (input) == 0
       `T            of T's string representation
     {               with duplicates removed
  q\2                equal "2", 
 &                   and
            }T       T is found in
              PT     the list of T's prime factors.
PurkkaKoodari
fuente
2

Perl 6 , 53 bytes

{($/=2 x$^n-1)~first {+($/~$_) .is-prime&&/^2/},0..*}

Intentalo

Expandido:

{
  ( $/ = 2 x $^n-1 )       # add n-1 '2's to the front (cache in 「$/」)
  ~
  first {
    +( $/ ~ $_ ) .is-prime # find the first that when combined with 「$/」 is prime
    &&
    /^2/                   # that starts with a 2 (the rest are in 「$/」)
  },
  0..*
}
Brad Gilbert b2gills
fuente
2

Pyke, 14 bytes

.fj`Q\2*.^j_P&

Pruébalo aquí!

.fj            - first number (asj)
   `    .^     -   str(i).startswith(V)
    Q\2*       -    input*"2"
             & -  ^ & V
          j_P  -   is_prime(j)

12 bytes después de la corrección de errores y una nueva característica

~p#`Q\2*.^)h

Pruébalo aquí!

~p           - all the primes
  #       )h - get the first where...
   `    .^   - str(i).startswith(V)
    Q\2*     -  input*"2"
Azul
fuente
2

Salvia, 69 68 bytes

lambda n:(x for x in Primes()if '2'*len(`x`)=>'2'*n==`x`[:n]).next()

Utiliza un generador para encontrar el primero (por lo tanto, el más pequeño) de infinitos términos.

busukxuan
fuente
2

Japt, 20 bytes

L²o@'2pU +Xs s1)nÃæj

¡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

                       // Implicit: U = input integer, L = 100
L²o                    // Generate the range [0...100²).
   @             Ã     // Map each item X through the following function:
    '2pU               //   Take a string of U "2"s.
         +Xs s1)n      //   Append all but the first digit of X, and cast to a number.
                       // If U = 3, we now have the list [222, 222, ..., 2220, 2221, ..., 222999].
                  æ    // Take the first item that returns a truthy value when:
                   j   //   it is checked for primality.
                       // This returns the first prime in the forementioned list.
                       // Implicit: output result of last expression

En la última versión de Japt, esto puede ser de 12 bytes:

_n j}b!+'2pU   // Implicit: U = input integer
_   }b         // Return the first non-negative bijective base-10 integer that returns
               // a truthy value when run through this function, but first,
      !+       //   prepend to each integer
        '2pU   //   a string of U '2's.
               // Now back to the filter function:
 n j           //   Cast to a number and check for primality.
               // Implicit: output result of last expression

¡Pruébelo en línea! Termina en medio segundo en mi máquina para todas las entradas hasta 14.

ETHproducciones
fuente
¡Gran solución!
Oliver
Esto falla en la entrada 5, ya que nunca prueba 2222203, solo 222223y poco después 2222210. También falla en cualquier entrada que requiera tres o más dígitos adicionales después de la cadena de 2s, como la entrada 15.
Greg Martin
@ GregMartin Maldición, tienes razón. Corregido a un costo de 5 bytes.
ETHproductions
Esto soluciona los casos de prueba, pero el algoritmo aún asume que uno nunca tendrá que agregar más de tres dígitos para encontrar un primo, que puede ser falso para entradas más grandes.
Greg Martin el
@ GregMartin Esto funciona para todos los casos de prueba hasta 14, y JS se encuentra con problemas de precisión de enteros en el caso 15. No creo que el algoritmo deba ser teóricamente correcto después de 2 ^ 53, pero tal vez me equivoque ...
ETHproductions
2

PHP, 76 bytes

for($h=str_pad(2,$i=$argv[1],2);$i>1;)for($i=$p=$h.++$n;$p%--$i;);echo$p?:2;

toma información del argumento de la línea de comando. Corre con -r.

Descompostura

for($h=str_pad(2,$i=$argv[1],2) # init $h to required head
    ;$i>1;                      # start loop if $p>2; continue while $p is not prime
)
    for($i=$p=$h.++$n               # 1. $p = next number starting with $h
                                    #    (first iteration: $p is even and >2 => no prime)
    ;$p%--$i;);                     # 2. loop until $i<$p and $p%$i==0 ($i=1 for primes)
echo$p?:2;                      # print result; `2` if $p is unset (= loop not started)
Titus
fuente
1

Bash (+ coreutils), 53 bytes

Funciona hasta 2 ^ 63-1 (9223372036854775807) , toma un tiempo considerable para terminar para N> 8.

Golfed

seq $[2**63-1]|factor|grep -Pom1 "^2{$1}.*(?=: \S*$)"

Prueba

>seq 0 7|xargs -L1 ./twist

2
2
223
2221
22229
2222203
22222223
22222223
zepelín
fuente
1

Python 3, 406 bytes

w=2,3,5,7,11,13,17,19,23,29,31,37,41
def p(n):
 for q in w:
  if n%q<1:return n==q
  if q*q>n:return 1
 m=n-1;s,d=-1,m
 while d%2==0:s,d=s+1,d//2
 for a in w:
  x=pow(a,d,n)
  if x in(1,m):continue
  for _ in range(s):
   x=x*x%n
   if x==1:return 0
   if x==m:break
  else:return 0
 return 1
def f(i):
 if i<2:return 2
 k=1
 while k:
  k*=10;l=int('2'*i)*k
  for n in range(l+1,l+k,2):
   if p(n):return n

código de prueba

for i in range(31):
    print('{:2} = {}'.format(i, f(i)))

salida de prueba

 0 = 2
 1 = 2
 2 = 223
 3 = 2221
 4 = 22229
 5 = 2222203
 6 = 22222223
 7 = 22222223
 8 = 222222227
 9 = 22222222223
10 = 22222222223
11 = 2222222222243
12 = 22222222222201
13 = 22222222222229
14 = 222222222222227
15 = 222222222222222043
16 = 222222222222222221
17 = 222222222222222221
18 = 22222222222222222253
19 = 222222222222222222277
20 = 2222222222222222222239
21 = 22222222222222222222201
22 = 222222222222222222222283
23 = 2222222222222222222222237
24 = 22222222222222222222222219
25 = 222222222222222222222222239
26 = 2222222222222222222222222209
27 = 2222222222222222222222222227
28 = 222222222222222222222222222269
29 = 2222222222222222222222222222201
30 = 222222222222222222222222222222053

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.

PM 2Ring
fuente
1
En primer lugar: las presentaciones deben tener una probabilidad de 1 probabilidad de salida correcta. en segundo lugar, esto es codegolf, por lo que en realidad debes elegir el tamaño de byte. Aparte de eso, agradable
Destructible Lemon
1
@DestructibleWatermelon ¡Gracias! Punto justo sobre el tamaño del byte. Supongo que podríap() 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). :)
PM 2Ring
Muchos programas no pueden manejar un número de 33 dígitos (n: = 30). Dado que el estándar de oro de OP solo llega a 18 dígitos y no existe un límite establecido por él / ella, es razonable suponer que n: = 30 es suficientemente buena IMO.
user3819867
@ PM2Ring No necesita estar en "menos de un segundo". Haga el código lo más corto posible e ignore la velocidad por completo. Ese es el espíritu de [code-golf]. Cambiaré mi voto a favor una vez que se haya jugado golf.
mbomb007
en realidad, si produce una salida correcta hasta el límite, entonces la respuesta funciona con probabilidad uno.
Destructible Lemon
1

Python 3, 132 bytes

def f(x):
 k=10;p=2*(k**x//9)
 while x>1:
  for n in range(p*k,p*k+k):
   if all(n%q for q in range(2,n)):return n
  k*=10
 return 2

Cualquier esperanza de rendimiento se ha sacrificado por un recuento de bytes más pequeño.

cdlane
fuente
-1

Java, 163 bytes

BigInteger f(int a){for(int x=1;x>0;x+=2){BigInteger b=new BigInteger(new String(new char[a]).replace("\0","2")+x);if(b.isProbablePrime(99))return b;}return null;}

código de prueba

    public static void main(String[] args) {
    for(int i = 2; i < 65; i++)
        System.out.println(i + " " + new Test20170105().f(i));
    }

salida:

2 223
3 2221
4 22229
5 2222219
6 22222223
7 22222223
8 222222227
9 22222222223
10 22222222223
11 2222222222243
12 22222222222229
13 22222222222229
14 222222222222227
15 222222222222222143
16 222222222222222221
17 222222222222222221
18 22222222222222222253
19 222222222222222222277
20 2222222222222222222239
21 22222222222222222222261
22 222222222222222222222283
23 2222222222222222222222237
24 22222222222222222222222219
25 222222222222222222222222239
26 2222222222222222222222222213
27 2222222222222222222222222227
28 222222222222222222222222222269
29 22222222222222222222222222222133
30 222222222222222222222222222222113
31 222222222222222222222222222222257
32 2222222222222222222222222222222243
33 22222222222222222222222222222222261
34 222222222222222222222222222222222223
35 222222222222222222222222222222222223
36 22222222222222222222222222222222222273
37 222222222222222222222222222222222222241
38 2222222222222222222222222222222222222287
39 22222222222222222222222222222222222222271
40 2222222222222222222222222222222222222222357
41 22222222222222222222222222222222222222222339
42 222222222222222222222222222222222222222222109
43 222222222222222222222222222222222222222222281
44 2222222222222222222222222222222222222222222297
45 22222222222222222222222222222222222222222222273
46 222222222222222222222222222222222222222222222253
47 2222222222222222222222222222222222222222222222219
48 22222222222222222222222222222222222222222222222219
49 2222222222222222222222222222222222222222222222222113
50 2222222222222222222222222222222222222222222222222279
51 22222222222222222222222222222222222222222222222222289
52 2222222222222222222222222222222222222222222222222222449
53 22222222222222222222222222222222222222222222222222222169
54 222222222222222222222222222222222222222222222222222222251
55 222222222222222222222222222222222222222222222222222222251
56 2222222222222222222222222222222222222222222222222222222213
57 222222222222222222222222222222222222222222222222222222222449
58 2222222222222222222222222222222222222222222222222222222222137
59 22222222222222222222222222222222222222222222222222222222222373
60 222222222222222222222222222222222222222222222222222222222222563
61 2222222222222222222222222222222222222222222222222222222222222129
62 2222222222222222222222222222222222222222222222222222222222222227
63 2222222222222222222222222222222222222222222222222222222222222227
64 2222222222222222222222222222222222222222222222222222222222222222203

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.

SamCle88
fuente
3
isProbablePrimetiene falsos positivos ocasionales . Eso invalidaría la respuesta, ya que hay circunstancias en las que devuelve el valor incorrecto.
La probabilidad de error es inferior a 2 ^ -99 (ver documentación ).
SamCle88
@ SamCle88 pequeña probabilidad o no, esto está mal en un tecnicismo. isProbablePrime no es aceptable para la verificación principal y se le ha denegado en otros desafíos.
Magic Octopus Urn