Imprime la enésima prima que contiene n

39

Esta pregunta será un giro en la búsqueda del nnúmero primo th.

Reto

Debe escribir un programa que tomará una entrada ny generará el nnúmero primo th cuya representación decimal contiene la representación decimal de ncomo una subcadena.

¿Confuso? Aquí hay unos ejemplos.

n=1
Primes: 2, 3, 5, 7, 11
                    ^1 first prime that contains a 1
Output: 11

n=2
Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23
        ^1                          ^2 second prime that contains a 2
Output: 23

n=3
Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23
           ^1           ^2          ^3 third prime that contains a 3
Output: 23

n=10
Primes: 2, 3, 5, 7, 11, ..., 97, 101, 103, 107, 109, ..., 997, 1009, 1013, 1019, 1021, 1031, 1033
                                 ^1   ^2   ^3   ^4             ^5    ^6    ^7    ^8    ^9    ^10 tenth prime that contains a 10
Output: 1033

Este es el , por lo que gana el conteo de bytes más bajo.

Si algo es confuso, por favor deje un comentario.

ericw31415
fuente
2
¿Hay un OEIS para esto? Parece que debería haber
MayorMonty
@SpeedyNinja No, ya lo he comprobado.
Adnan
Relacionado
Alex A.
1
No puedo creer que esto haya llegado al número 5 en la Hot Network Questionslista.
ericw31415
Una secuencia similar
Nathan Merrill

Respuestas:

12

05AB1E , 8 bytes

Código:

µN¹åNp*½

Explicación:

µ          # Run this until the counting variable has reached the input value.
 N¹å       # Check if the input number is in the range variable.
    Np     # Check if the range variable is prime.
      *    # Multiply those two numbers (which is basically an AND operator).
       ½   # If true, increment the counting variable.
           # After the loop, the stack is empty and implicitly prints N.

Utiliza la codificación CP-1252 . Pruébalo en línea! .

Adnan
fuente
8

Python 2, 67 65 62 bytes

f=lambda n,k=0,m=2,p=1:k/n or-~f(n,k+p%m*(`n`in`m`),m+1,p*m*m)

Pruébalo en Ideone .

Cómo funciona

Usamos un corolario del teorema de Wilson :

corolario del teorema de Wilson

En todo momento, la variable p es igual al cuadrado del factorial de m - 1 .

Si k <n , k/nrendirá 0 y f se llama de forma recursiva. m se incrementa, p se actualiza y k se incrementa si y solo si m es un primo que contiene n .

Este último se consigue añadiendo el resultado de p%m*(`n`in`m`)a k . Según el corolario del teorema de Wilson, si m es primo, p%mdevuelve 1 , y si no, devuelve 0 .

Una vez k alcances n , encontramos q , el n º primordial que contiene n .

Estamos en la próxima llamada durante la verificación, entonces m = q + 1 . k/ndevolverá 1 , y los operadores bit a bit -~incrementarán ese número una vez por cada llamada de función. Dado que se requieren q - 1 llamadas a f para incrementar m de 2 a q + 1 , la llamada externa a f devolverá 1 + q - 1 = q , según lo previsto.

Dennis
fuente
6

Bash, 27 bytes

primes 0|grep $1|sed $1q\;d

primes proviene de bsdgames.

Toma la entrada como un argumento de línea de comando y sale en STDOUT.

Pomo de la puerta
fuente
4

Mathematica, 75 bytes

Nest[NestWhile[b=NextPrime,b@#,!StringContainsQ@@ToString/@{#,a}&]&,1,a=#]&

Todavía puede ser golfable.

LegionMammal978
fuente
Esta es probablemente la solución más rápida ya que utiliza NextPrime :)
4

Java, 194 180 173 171 112 Bytes

Código:

a->{int i=1,j,n,r=0;for(j=n=new Integer(a);(r+=++i>=j&(""+j).contains(""+n)?1:0)!=n;j+=j%i==0?i=1:0);return j;}

Sin golf:

class P{
    static int i=1,j,n,r;
    public static void main(String[]s) {
        for(
                j=n=new Integer(s[0]); //executes once before first iteration
                (r+=++i>=j&(""+j).contains(""+n)?1:0)!=n; //executes on first and every iteration
                j+=j%i==0?i=1:0 //executes after first and every iteration
           ) {
            ;
        }
        System.out.print(j);
    }
}
Con suerte
fuente
Hola, bienvenido a PPCG! Dos cosas a tener en cuenta: 1. Puede eliminar dos espacios en P {y String[] s. Y 2. actualmente solo está dando la salida 10, pero el desafío del código de golf era tomar una entrada ny dar la salida adecuada en función de esa entrada. Además, puede encontrar esto interesante: consejos para jugar al golf en Java.
Kevin Cruijssen
3

Ruby, 62 61 bytes

->i{Prime.lazy.map(&:to_s).grep(/#{i}/).first(i)[-1]}

Requiere la -rprimebandera (+8 bytes).

->i{            # lambda with one argument
Prime           # iterator over all primes
.lazy           # make the iterator lazy (can't evaluate infinite primes)
.map(&:x.to_s)  # convert the primes to strings
.grep(/#{i}/)   # find primes that regex match on the input (contain it)
.first(i)       # take the first (input) primes that satisfy this
[-1]            # take the last of those
}
Pomo de la puerta
fuente
3

MATL , 18 bytes

`@YqVGVXf?3M]NG<]&

Pruébalo en línea!

Explicación

Esto genera números primos en orden usando un do...whilebucle. Para cada cebado, se prueba la condición (y se consume el cebado). Si está satisfecho, esa prima se empuja a la pila nuevamente. El número de elementos en la pila se usa como recuento de cuántos primos calificados hemos encontrado. Cuando hay suficientes, se muestra el último.

`         % Do...while
  @       %   Push iteration index, k. Starts at 1
  YqV     %   k-th prime. Convert to string
  GV      %   Push input, n. Convert to string
  Xf      %   Find string within another
  ?       %   If non-empty
    3M    %     Push k-th prime again (increase stack size by 1)
  ]       %   End if
  NG<     %   Is stack size less than input number? If so proceeed with
          %   a new iteration; else exit do...while loop
]         % End do...while
&         % Implicitly display only top number in the stack 
Luis Mendo
fuente
1

Bash + GNU coreutils, 66 Bytes

A diferencia de la solución de @ Doorknob, esta solo necesita cosas que están instaladas en cada GNU / Linux:

for((n=2;;n++)){
[ `factor $n|wc -w` -eq 2 ]&&grep $1<<<$n&&exit
}
rexkogitans
fuente
seq 1e20|factor|grep -Po "(?<=: )\d*$2\d$"|sed $1q\;d
Trauma digital
@DigitalTrauma, mi cerebro no funciona de esta manera ;-)
rexkogitans
¿Necesita las nuevas líneas?
ericw31415
Después for((...)){, debe haber un espacio o una nueva línea, por lo que no importa. Antes del cierre }, debe haber una ; o una nueva línea, por lo que tampoco importa.
rexkogitans
1

Perl 6 , 41 bytes

->$n {grep({.is-prime&&/$n/},2..*)[$n-1]}

Explicación:

-> $n { # has one parameter
  grep(
    {
      .is-prime # check that it is prime
      &&        # and
      / $n /    # that it contains the argument in the "string"
    },
    2 .. *      # for all numbers starting with 2
  )[ $n - 1 ]   # only take the $n-th one
                # ( accounting for 0 based array access )
}

Prueba:

#! /usr/bin/env perl6
use v6.c;
use Test;

my &prefix:<ℙ𝕟> = ->$n {grep({.is-prime&&/$n/},2..*)[$n-1]}

my @test = (
  1  => 11,
  2  => 23,
  3  => 23,
  10 => 1033,
);

plan +@test;

for @test {
  is ℙ𝕟.key, .value, .gist
}
1..4
ok 1 - 1 => 11
ok 2 - 2 => 23
ok 3 - 3 => 23
ok 4 - 10 => 1033
Brad Gilbert b2gills
fuente
1

Java 8, 192 183 181 171 bytes (programa completo)

interface M{static void main(String[]a){long n=new Long(a[0]),c=0,r=1,m,i;for(;c<n;c+=m>1&(r+"").contains(a[0])?1:0)for(m=++r,i=2;i<m;m=m%i++<1?0:m);System.out.print(r);}}

Pruébalo en línea.

Explicación:

interface M{                    // Class
  static void main(String[]a){  //  Mandatory main-method
    long n=new Long(a[0]),      //   Input argument as number
         c=0,                   //   Counter, starting at 0
         r=1,                   //   Result-number, starting at 1
         m,i;                   //   Temp number
    for(;c<n;                   //   Loop as long as `c` does not equals `n`
        c+=                     //     After every iteration: increase `c` by:
           m>1                  //      If the current `r` is a prime,
           &(r+"").contains(a[0])?
                                //      and this prime contains the input `n`
            1                   //       Increase `c` by 1
           :                    //      Else:
            0)                  //       Leave `c` the same
      for(m=++r,                //    Increase `r` by 1 first with `++r`, and set `m` to it
          i=2;i<m;              //    Inner loop `i` in the range [2, `m`)
        m=m%i++<1?              //     If `m` is divisible by `i`
           0                    //      Change `m` to 0 (so it's not a prime)
          :                     //     Else:
           m);                  //      Leave `m` unchanged
    System.out.print(r);}}      //    Print `r` as result

Java 8, 105 bytes (función lambda)

n->{int c=0,r=1,m,i;for(;c<n;c+=m>1&(r+"").contains(n+"")?1:0)for(m=++r,i=2;i<m;m=m%i++<1?0:m);return r;}

Pruébalo en línea.

Igual que el anterior, pero con una nentrada entera y sin el material de clase detallado.

Kevin Cruijssen
fuente
1
se puede reemplazar &&con &y quitar ?de su expresión regular.
Cliffroot
@cliffroot Gracias, editó la publicación. Siempre me olvido &&y &por alguna razón ..
Kevin Cruijssen
0

Clojure, 118 bytes

(defn s[n](nth(filter(fn[x](if(.contains(str x)(str n))(not-any? #(=(mod x %)0)(range 2 x))))(drop 2(range)))(dec n)))

Solo obtiene el enésimo elemento de la secuencia infinita perezosa de números que son primos y tienen nen su representación de cadena.

Puedes probarlo aquí: https://ideone.com/ioBJjt

acantilado
fuente
0

En realidad, 16 bytes

;$╗`P$╜@íu`╓dP.X

Pruébalo en línea!

Explicación:

;$╗`P$╜@íu`╓dP.X
;$╗               make a copy of n, push str(n) to reg0
   `      `╓      push the first n values where f(k) is truthy, starting with k=0:
    P$              kth prime, stringified
      ╜@íu          1-based index of n, 0 if not found
            d     remove last element of list and push it to the stack (dequeue)
             P    nth prime
              .   print
               X  discard rest of list
Mego
fuente
0

PowerShell v2 +, 108 99 bytes

Ooof La falta de cualquier tipo de cálculo / verificación primo incorporado realmente duele aquí.

param($n)for(){for(;'1'*++$i-match'^(?!(..+)\1+$)..'){if("$i"-like"*$n*"){if(++$o-eq$n){$i;exit}}}}

Toma entrada $n, ingresa un for()bucle infinito . Cada iteración, usamos un forbucle envuelto alrededor del comprobador de expresiones regulares de PowerShell regex (h / t para Martin) para convertirlo en un generador principal incrementando $icada vez a través del bucle. (Por ejemplo, ejecutar solo for(){for(;'1'*++$i-match'^(?!(..+)\1+$)..'){$i}}generará resultados 2, 3, 5, 7...separados por nuevas líneas).

Luego, una simple -likeverificación para ver si $nestá en algún lugar $ie incrementar nuestro contador $o. Si hemos llegado a donde $ny $oson iguales, salida $iy exit. De lo contrario, continuamos forhasta encontrar el próximo primo y el proceso se repite.

AdmBorkBork
fuente
0

APL (NARS), 39 caracteres, 78 bytes

{s←⍕w←⍵⋄2{(w≤⍵)∧k←∨/s⍷⍕⍺:⍺⋄(1π⍺)∇⍵+k}1}

1π es el siguiente número primo ...; prueba:

  f←{s←⍕w←⍵⋄2{(w≤⍵)∧k←∨/s⍷⍕⍺:⍺⋄(1π⍺)∇⍵+k}1}
  f¨1 2 3 10
11 23 23 1033 

pero eso ya a las 20 sale el espacio de la pila ... En cambio, esto a continuación parece estar bien, incluso si ha durado un poco más (61 caracteres)

∇r←f w;i;k;s
r←2⋄s←⍕w⋄i←1
→0×⍳(w≤i)∧k←∨/s⍷⍕r⋄r←1πr⋄i+←k⋄→2
∇

  f¨1 2 3 10 20 100
11 23 23 1033 4201 100999 
RosLuP
fuente
0

Añadir ++ , 36 bytes

L,5*2^RßÞPABDBJVB]dG€Ωezߣ*BZB]A1_$:

Pruébalo en línea!

Bastante ineficiente. Itera sobre cada enteroyo tal que yo25X2 y filtra compuestos y primos que no contienen norte. Finalmente, tomamos elnorteEl valor de los enteros restantes.

caird coinheringaahing
fuente