Primas repetidas de dígitos

13

Otra secuencia, otro desafío. *

Definición

Un primo pestá en esta secuencia, llamémoslo A, si por cada dígito den pla expansión decimal de, reemplaza dcon dcopias de dy el entero resultante sigue siendo primo; los ceros no están permitidos.

Por ejemplo, 11es trivial en esta secuencia (es el primer número, por cierto). El siguiente en la secuencia es 31, porque 3331también es primo; entonces 53porque 55555333también es primo, y así sucesivamente.

Desafío

Dada una entrada n, devuelve A(n), es decir, el nelemento th en esta secuencia.

Ejemplos

Aquí están los primeros 20 términos para comenzar. Este es A057628 en OEIS.

11, 31, 53, 131, 149, 223, 283, 311, 313, 331, 397, 463, 641, 691, 937, 941, 1439, 1511, 1741, 1871

Esto significa A(0) = 11, A(1) = 31etc., cuando se usa la indexación cero.

Reglas

  • Puede elegir indexación basada en cero o en una; especifique en su respuesta cuál.
  • En lugar de devolver solo el nelemento th, puede optar por devolver los primeros ntérminos.
  • Puede suponer que la entrada / salida no será mayor que el formato entero nativo de su idioma; sin embargo, el primer dígito repetido puede ser mayor que el formato nativo de su idioma, por lo que será necesario tenerlo en cuenta.
  • Por ejemplo, 1871el último número de ejemplos tiene un primo correspondiente de 18888888877777771, que es bastante más grande que el INT32 estándar.
  • Un programa completo o una función son aceptables. Si es una función, puede devolver el resultado en lugar de imprimirlo.
  • La salida puede ser a la consola, devuelta desde una función, mostrada en una ventana emergente de alerta, etc.
  • Las lagunas estándar están prohibidas.
  • Este es el por lo que se aplican todas las reglas habituales de golf, y gana el código más corto (en bytes).

* Para ser justos, se me ocurrieron los primeros términos de la secuencia jugando con algunos números, y luego fui a OEIS para obtener el resto de la secuencia.

AdmBorkBork
fuente
2
Me pregunto si existe un primo cuyo resultado de dígitos repetidos también está en esta secuencia, y cuyo resultado de dígitos repetidos también está en esta secuencia, y así sucesivamente, hasta el infinito. Parece altamente improbable.
Steadybox
1
@ Steadybox 11 cumple esta condición, hasta el infinito. Pero aparte de eso, sería interesante ver cuántas veces podría aplicar la operación de repetición de dígitos y seguir obteniendo números primos.
dylnan
Dado que 1666666999999999 es primo, ¿por qué no 169 en la secuencia?
Pablo Oliva
2
@PabloOliva Porque en 169sí mismo no es primo, lo es 13 * 13.
AdmBorkBork

Respuestas:

6

Casco , 15 bytes

!fo§&öεpd´ṘΠdİp

Pruébalo en línea!

!                 Index into
             İp     the list of primes
 f                    for which:
            d            the digits of p
  o§&                      satisfy both:
     öεpd´Ṙ                  repeated "themselves" times, they form a prime.
           Π                 they are all nonzero.

Erik el Outgolfer salvó un byte. Usar en lugar de εpguardaría otro byte, pero eso hace que el programa sea tan lento que incluso iguala para n = 2.

Lynn
fuente
1
@ H.PWiz No creo que juzguemos la velocidad aquí ...
Erik the Outgolfer
Realmente debería acelerar en el intérprete, es una locura cómo es más lento que encontrar todos los factores primos ...
Zgarb
6

05AB1E , 14 13 bytes

-1 byte gracias a Emigna !

µNSÐPŠ×JpNpPĀ½

Pruébalo en línea!

Explicación

µNSÐPŠ×JpNpPĀ½
µ              # Do until the input is reached...
 N              # Push the iteration counter
  S             # Split it to its digits
   Ð            # And push two copies of it to the stack
    P           # Get the digital product of the counter
     Š          # And place it two places down the stack
      ×J        # Repeat each digit by itself and join it back to a number
        p       # Check for primality on that result
         Np     # And on the original counter as well
           PĀ   # Create the product and truthify the result
                # Implicit: If it is true increment the input number
Datboi
fuente
5

Jalea , 18 14 bytes

ÆPaDxDḌÆPaDẠµ#

Pruébalo en línea!

Sr. Xcoder: -1 Byte (lógico todo)

Erik the Outgolfer: -2 Bytes (una línea en lugar de dos)

HyperNeutrino: -1 Byte (devuelve los primeros n elementos de secuencia)

Explicación

ÆPaDxDḌÆPaDẠµ#     First Link
ÆP                Is prime?
  a               logical and
   D              convert number to list of digits
    xD            repeat each digit as many times as it's value
      Ḍ           convert to an integer
       ÆP         is prime?
         a        logical and
          D       list of digits
           Ạ      logical all
            µ     the following link as a monad
             #    Do this until n matches are found and return them all

Editar: originalmente envió una respuesta que incluía números con 0 en su representación decimal, lo que específicamente no está permitido.

dylnan
fuente
Intenté hacer una respuesta más corta e independiente, pero acabo de recibir lo mismo :( xD
HyperNeutrino
5

Wolfram Language (Mathematica) , 100 bytes

Nest[#+1//.i_/;!PrimeQ@FromDigits[##&@@#~Table~#&/@(l=IntegerDigits@i)]||Min@l<1:>NextPrime@i&,1,#]&

Pruébalo en línea!

Jonathan Frech ahorró 3 bytes

y -7 bytes de JungHwan Min

-15 bytes de Martin Ender

También gracias a Jenny Mathy

Glorfindel
fuente
4

Alice , 72 70 66 62 56 bytes

Gracias a Leo por guardar 5 bytes.

/.\&wh...tz~F0/*$\W.tzt$W?K/ o
\i/&.,a:.$K;d&\FR/K.!w.a%

Pruébalo en línea!

Utiliza una entrada basada en 1.

Explicación

El truco más aseado golf aquí (aunque sólo ahorra un par de bytes) es que estoy usando un test de primalidad que da 0de compuesto n para npara no compuesto n . De esa manera, no tenemos que usar el resultado directamente en un condicional, pero podemos pasarlo directamente a la siguiente parte que verifica que la entrada no contenga ceros.

/i\       Read all input in Ordinal mode (the usual way to read decimal input).
&w        Push the current IP position onto the return address stack (RAS)
          n times. This effectively begins our main loop. We will return
          here after each number we've checked, but whenever we come across
          a repeated digit prime (RDP), we will pop one copy of the address
          from the RAS, so that the loops ends once we've found n RDPs.

h.        Increment our main loop iterator X (initially an implicit zero on
          the empty stack) and duplicate it.
.         Make another copy.
.tz       Drop all factors less than X. This gives X for prime X and 1 for
          non-prime X.
~F        Check whether X divides this value. Of course, X divides X so this
          gives X for non-composite X. But X doesn't divide 1 (unless X is 1),
          so we get 0 for composite X. Call this Y.
0         Push a 0.
\         Switch to Ordinal mode.
F         Implicitly convert both to string and check whether Y contains 0.
$/K       If it does, return to the w. Either way, switch back to Cardinal mode.
          Note that the only numbers that get to this point are 1 and prime
          numbers which don't contain 0. It's fine that we let 1 through here,
          because we'll use a proper primality test for the digit-expanded
          version later on.
.!        Store a copy of X on the tape. Let's call the copy that remains on
          the stack Z, which we're now decomposing into digits while expanding
          them.
w         Push the current IP position to the RAS. This marks the beginning
          of an inner loop over the digits of Z.

  .a%       Duplicate Z and retrieve its last digit D by taking Z % 10.
  \./       Duplicate D (in Ordinal mode but that doesn't matter).
  &.        Duplicate D, D times. So we end up with D+1 copies of D.
  ,         Pop the top D and pull up the Dth stack element, which is Z.
  a:        Discard the last digit by taking Z / 10.
  .$K       If Z is zero now, skip the K and end the inner loop, otherwise
            repeat the inner loop.
;         Discard the 0 (what used to be Z).
          We now have D copies of each digit D on the stack, but the digits
          were processed in reverse order, so the last digit is at the bottom.
d&        Repeat the next command once for each stack element.
\*        Concatenate in Ordinal mode. This joins all the digits on the
          stack into a single string.
R         Reverse that string. This is the digit-expanded version of X.
/         Switch back to Cardinal mode.
W         Pop the inner loop's return address from the RAS. We could have done
          this right after the most recent K, but putting it here helps lining
          up the two Ordinal sections in the program layout.
.tzt      Is the digit-expanded number a prime?
$W        If so, we've found an RDP. Pop one copy of the main loop address 
          from the RAS.
g         Recover the current value of X from the top left grid cell.
K         Jump back to the w if any copies of the return address are left 
          on the RAS. Otherwise, we leave the main loop.
/o        Implicitly convert the result to a string and print it in
          Ordinal mode.
          The IP will then bounce off the top right corner and start
          travelling through the program in reverse. Whatever it does
          on the way back is utter nonsense, but it will eventually get
          back to the division (:). The top of the stack will be zero
          at that point and therefore the division terminates the program.
Martin Ender
fuente
4

Python 2 , 130 bytes

  • Gracias a ArBo por esta solución más corta de cuatro bytes.
f=lambda n,c=9:n and f(n-(('0'in`c`)<p(c)*p(int("".join(d*int(d)for d in`c`)))),c+1)or~-c
p=lambda n:all(n%m for m in xrange(2,n))

Pruébalo en línea!


Python 2 , 195 179 167 140 138 136 135 134 bytes

  • Guardado 27 bytes gracias a los ovs ; usando en xrangelugar de range, evitando así a MemoryErrory compactando la función principal; mejorando el conteo de índices enteros.
  • Guardado dos bytes; utilizando canalización binaria u operaciones |para guardar bytes or.
  • Guardado dos bytes; invirtiendo la función principal y haciendo alguna manipulación lógica adicional.
  • Guardado un byte; usando en ~-lugar de 0**invertir la existencia de un cero en j, &seguido de un valor booleano verdadero, se aísla la propiedad booleana de este valor.
  • Salvó un byte gracias a Lynn ; golf ~-A&B&C(equivalente a (not A) and B and C) con A, B, Cser booleanos A<B==C.
def f(n,j=9,p=lambda n:all(n%j for j in xrange(2,n))):
 while n:j+=1;n-=("0"in`j`)<p(j)==p(int("".join(d*int(d)for d in`j`)))
 print j

Pruébalo en línea! (1 indexado)

Explicación

Define una función principal fque toma un índice entero ny, por defecto, un valor establecido j, la secuencia actual canditate (iniciada 9para mejorar el rendimiento manteniendo el tamaño del programa) y una función de comprobación principal.
Mientras nno sea cero, la nentrada de la secuencia -ésima aún no se encuentra. Por jlo tanto, se incrementa y nse disminuye en uno si f jes un número que satisface las propiedades requeridas.
Cuando finaliza el bucle, jes la nentrada de la secuencia -th y, por lo tanto, se imprime.

Jonathan Frech
fuente
Llego un poco tarde a la fiesta, pero puedes
ahorrar
@ArBo Gracias.
Jonathan Frech
3

Pyth , 21 bytes

.f&.AKjZT&P_ss*VK`ZP_

Pruébalo aquí!

Más bien largo, ya que Pyth no tiene una expansión decimal incorporada.

  • Tome los primeros N enteros positivos ( .f), que:
    • Tener todos los dígitos veraces ( .AKjZT) y ( &) ...
    • La multiplicación vectorizada de su representación de cadena con sus dígitos ( *VK`Z), unidos y convertidos en un entero ( ss) son primos ( P_) y ( &) ...
    • Eso son primos en sí mismos ( P_).
Sr. Xcoder
fuente
Puede eliminar esegún una nueva enmienda de la regla.
Erik the Outgolfer
@EriktheOutgolfer Hecho, gracias
Sr. Xcoder
2

Perl 6 , 51 bytes

{(grep {!/0/&is-prime $_&S:g/./{$/x$/}/},2..*)[$_]}

Pruébalo en línea!

  • grep {...}, 2..*filtra la secuencia infinita de números naturales a partir de 2 utilizando la función de predicado entre llaves. (...)[$_]indexa en esta lista filtrada utilizando el argumento de la función $_.
  • !/0/ filtra los números que contienen un dígito cero.
  • S:g/./{$/ x $/}/ replica cada dígito en la expansión decimal del número de prueba.
  • is-prime $_ & S:g/./{$/ x $/}/llama a la is-primefunción incorporada con una unión y de $_, el número de prueba y el número resultante de replicar sus dígitos. La función devolverá verdadero si ambos miembros de la unión y son primos.
Sean
fuente
2

J, 81 bytes

f=.[:1&p:(*@(*/)*x:@#~)&.(10&#.inv)
[:{.(4&p:@{.@]([,]+f@[){:@])^:([>{:@])^:_&2 0

Esta es una de esas situaciones para las que aún no he encontrado una buena solución J.

Sin embargo, publico esto con la esperanza de aprender algo nuevo.

fnos dice si un número dado es un "primer dígito repetido". Se descompone de la siguiente manera:

[:1&p:                               is the following a prime?
      (*@                            the signum of...
         (*/)                        the product of the digits
             *                       times...
              x:@                    force extended precision of...
                 #~)                 self-duplicated digits
                    &.               "Under": perform this, then perform its inverse at the end
                      (10&#.inv)     convert to a list of digits

Y, finalmente, el principal Do ... Mientras que el verbo, con su molesto, aparentemente inevitable repetitivo, que surge del hecho de que necesitamos usar una lista para almacenar nuestro progreso, que requiere registros "actuales" y "encontrados hasta ahora" , ya que nuestro argumento izquierdo ya está siendo usado para almacenar la condición de parada, es decir, n. Esto significa que debemos usar muchos bytes preciosos para la simple tarea de especificar args ([ y ]) y desempaquetar nuestra lista de 2 elementos ( {.y {:):

[:{.                                                take the first element of the final result, of the following Do... While:
    (4&p:@                                          the next prime after...
          {.@                                       the first element of...
             ]                                      the right arg 
                       {:@])                        the last (2nd) elm of the arg...
              ([,]+f@[)                             those two now become the left and right args to this verb...
               [,                                   left arg appended to...
                 ]+                                 right arg plus...
                   f@[                              f of the left arg...
                             ^:(      )^:_          keep doing all that while...
                                [>                  the left is bigger than...
                                  {:@]              the last elm of the right arg
                                          &2 0      seed the process with 2 0, ie,
                                                    the first prime, and 0 rdps found so far.

Pruébalo en línea!

Jonás
fuente
¿Es realmente menos bytes tener una función auxiliar? ¿No puede simplemente reemplazarlo fcon la función auxiliar envuelta entre paréntesis? Además, intenté jugar golf con la función de ayuda y se me ocurrió1 p:('x',~"."0#])&.": , que desafortunadamente no excluye con éxito los números primos con '0' en ellos. ¿Que piensas? También tiene que tener la 'x',~parte para obtener una precisión adicional ...
cole
@cole yes re: la función de ayuda agrega un byte, pero en este punto estamos puliendo latón en el Titanic, así que pensé por qué molestarse, solo mantén la claridad y tal vez millas o FrownyFrog intervengan con una idea que ahorra bytes reales
Jonás
Veré su golf de la función de ayuda más tarde
Jonás
57 bytes hasta el momento (((0>.-)((*&(1&p:)0&e.|10#.#~),.&.":))([,(+*)~)])/^:_@,&2, el uso 10xde expandir la gama de lo contrario n = 15 se saltará 937
millas
@miles, eres un dios J. Ya encontré algunos buenos trucos nuevos aquí. voy a revisarlo de nuevo mañana para asegurarme de que entiendo la iteración / disminución. No sé si notó el enlace a mi pregunta SO, pero ¿diría que esta es una técnica general que podría resolver el problema que planteé allí?
Jonás