¿Es una tortuga prima?

28

Como todos sabemos, son tortugas hasta el fondo . Pero, ¿está bien preparado también?

Un número se considera un "primo de tortuga" si cumple las siguientes condiciones:

1) It is prime.
2) It is possible to remove a single digit leaving a prime number.
3) Step 2 can be repeated until left with a single digit prime.

Por ejemplo, 239es un "tortuga-prime", ya que se puede reducir a 23continuación, ya sea 2o 3, ambos de los cuales son primos. También se puede reducir a 29entonces 2. 151no es un primo de tortuga, ya que se reduce a 15(no primo), 51(no primo) o 11. 11es primo, pero solo puede reducirse a 1, que no lo es.

Dado un número entero positivo, determine si es un "primo de tortuga". Su salida puede ser de cualquier forma siempre que proporcione la misma salida para cualquier valor verdadero o falso.

Casos de prueba:

input -> output
1     -> false
2     -> true
17    -> true
19    -> false
239   -> true
389   -> false

Tanteo

Este es el , por lo que gana la respuesta más corta en cada idioma.

Lord Farquaad
fuente
55
Relacionado
Urna de pulpo mágico
@MagicOctopusUrn WOW
Keyu Gan
8
Realmente relacionado
FryAmTheEggman
3
¿Podemos tomar la entrada como una lista de dígitos?
totalmente humano
1
Sus condiciones dicen que todos los primos de un solo dígito no son primos de tortuga. La condición 2 falla: no es posible eliminar un dígito y aún dejar un número primo, ya que eliminar el único dígito no deja nada.
hvd

Respuestas:

6

Jalea , 16 bytes

DŒPḊṖLÐṀḌ߀¬Ȧ<ÆP

Pruébalo en línea!

Cómo funciona

DŒPḊṖLÐṀḌ߀¬Ȧ<ÆP  Main link. Argument: n

D                 Decimal; convert n to base 10.
 ŒP               Powerset; get all sub-arrays of n's decimal digits.
   Ḋ              Dequeue; remove the first sub-array (empty array).
    Ṗ             Pop; remove the last sub-array (all of n's digits).
     LÐṀ          Maximal by length; keep those of the remaining subarrays that
                  have maximal length. This keep exactly those sub-arrays that have
                  one (and only one) digit removed. If n < 10, this yields an empty
                  array. Without Ḋ, it would yield [[]] instead.
        Ḍ         Undecimal; turn the generated digit arrays into integers.
         ߀       Recursively map the main link over the generated integers.
           ¬      Negate; map 1 to 0 and 0 to 1.
            Ȧ     Any and all; yield 0 if the array is empty (n < 10) or any of the
                  recursive calls returned 1 (mapped to 0). If all calls returned
                  0, this will yield 1.
              ÆP  Test n for primality, yielding 1 for primes, 0 otherwise.
             <    Test if the result to the left is less than the result to the
                  right. This is possible only if the left result is 0 (n < 10 or
                  removing a digit results in a turtle prime) and the right result
                  is 1 (n itself is prime).
Dennis
fuente
¡Más gelatina mágica! Hombre, esto llega a todas partes ...
caird coinheringaahing
7

Haskell , 104 102 99 98 97 95 91 bytes

p x=product[2..x-1]^2`mod`x>0
f[]=1>0
f x|y<-zip[0..]x=or[f[snd b|b<-y,b/=a]|a<-y,p$read x]

Pruébalo en línea!

Explicación

Primero configuramos una prueba de primalidad

p x=product[2..x-1]^2`mod`x>0

Esto utiliza el teorema de Wilson para determinar la primalidad de una entrada.

Luego declaramos un caso base, que afirmará que la cadena vacía es verdadera.

f[]=1>0

Ahora definimos la función real

f x|y<-zip[0..]x=or[f[snd b|b<-y,b/=a]|a<-y,p$read x]

Utilizamos un guardia patrón para unen zip[0..]xa y, porque tenemos que utilizar dos veces más tarde. Luego afirmamos que la respuesta es

or[f[snd b|b<-y,b/=a]|a<-y,p$read x]

[[snd b|b<-y,b/=a]|a<-y]son todos los números que son un dígito eliminado de nuestra entrada. Por lo tanto, estamos afirmando que al menos uno de estos números es verdadero f. Para garantizar que los números compuestos sean falsos, agregamos prime$read x. Si el número no es primo, la lista quedará vacía y el anyde una lista vacía es falso.

Asistente de trigo
fuente
1
−2 bytes: any f[[or[f[
Anders Kaseorg
1
−4 bytes: [b|(i,b)<-y,i/=a]|(a,_)<-y[snd b|b<-y,b/=a]|a<-y
Anders Kaseorg
6

R, 124 122 120 113 95 93 106 105 bytes

 g=pryr::f(`if`(gmp::isprime(sum(x*10^((l<-sum(x|1)-1):0))),any(!l,sapply(0:l+1,function(z)g(x[-z]))),!1))

Lo que evalúa la función:

function (x) 
if (gmp::isprime(sum(x * 10^((l <- sum(x | 1) - 1):0)))) any(!l, 
    sapply(0:l + 1, function(z) g(x[-z]))) else !1

Solución recursiva. Toma la entrada como una lista de dígitos.

Tiene 2 declaraciones lógicas:

  1. ¿Es xprimo cuando se concatena?

  2. Es alguno de los siguientes TRUE:

    1. ¿Es la longitud de xcero? Esta es nuestra condición final de terminación.

    2. Es f TRUEpara cualquier subconjunto de x?

La primera declaración asegura que seguimos trabajando solo con números primos. El segundo hace la recursión real.

Ahorré dos bytes gracias a @Giuseppe.

Tuve que revertir algunos de mis campos de golf debido a un error, donde estaba probando con una definición de función previa por accidente.

R, 98 bytes, no competidores

Como mencioné en los comentarios, hice un paquete . Dado que el desafío es anterior a esto, esto no es competitivo, pero quería mostrarlo un poco. No es mucho hasta ahora, pero llegaremos allí.

g=pryr::f(`if`(gmp::isprime(RG::C(x)),any(!(l<-sum(x|1)-1),sapply(0:l+1,function(z)g(x[-z]))),!1))

C() es la primera función del paquete y se encarga de concatenar dígitos en un número.

JAD
fuente
Algunas de estas operaciones (Mirándote sum(x*10^(((l<-sum(x|1))-1):0))) son muuuuy vergonzosas. Realmente estoy considerando crear un paquete de golf para R.
JAD
esto habría sido mi solución, pero no podía hacerme a la sapply... También creo que es posible que desee hacer f=pryr::f(...)o de lo que necesita para utilizar fen el sapply.
Giuseppe
1
@Giuseppe Nombres de letras individuales para todo: D ¿Por qué no llamar al paquete go algo así?
JAD
1
@Giuseppe creó el inicio de un paquete: p Echa un vistazo: github.com/JarkoDubbeldam/RG
JAD
1
@JarkoDubbeldam hermosa. Estoy seguro de que los desafíos futuros harán obvio qué funciones adicionales deben agregarse. La manipulación de cadenas es grande: algo para el(strsplit(x,''))ahorraría una tonelada de bytes.
BLT
5

Jalea , 19 bytes

DJḟЀ`ịDḌḟ0߀¬Ȧ¬aÆP

Pruébalo en línea!

Cómo funciona

DJḟЀ`ịDḌḟ0߀¬Ȧ¬aÆP                input:239

D                    decimal         [2,3,9]
 J                   range@length    [1,2,3]
  ḟЀ`               filter out each [[2,3],[1,3],[1,2]]
      ịD             index&decimal   [[3,9],[2,9],[2,3]]
        Ḍ            undecimal       [39,29,23]
         ḟ0          filter out 0    [39,29,23]
           ߀        this@each       [1,1,1]
             ¬       logical not     [0,0,0]
              Ȧ      any and all     0
               ¬     logical not     1
                aÆP  and&is_prime    1

Recursión sin caja base ftw.

Monja permeable
fuente
3

Gelatina , 27 26 bytes

DµœcL’$Ḍµ€FÆPÐf
×⁵WÇÐĿFṪ<8

Un enlace monádico que toma y devuelve enteros (1 para tortuga de lo 0contrario).

Pruébalo en línea!

¿Cómo?

DµœcL’$Ḍµ€FÆPÐf  Link 1: primes by digit removal: list of numbers  e.g. [19790]
D                cast to decimal list (vectorises)                      [[1,9,7,9,0]]
 µ      µ€       monadic chain for €ach:
      $            last two links as a monad:
    L                length                                             5
     ’               decrement                                          4
  œc             combinations without replacement                       [[1,9,7,9],[1,9,7,0],[1,9,9,0],[1,7,9,0],[9,7,9,0]]
       Ḍ         cast from decimal list (vectorises)                    [1979,1970,1990,1790,9790]
          F      flatten (from a list of lists form the for €ach to a single list)
             Ðf  filter keep if:
           ÆP      is prime?

×⁵WÇÐĿFṪ<8  Main Link: number, n             e.g. 1979
 ⁵          literal 10
×           multiply                              19790
              (this is so the first number is tested as prime too)
  W         wrap in a list                        [19790]
    ÐĿ      loop, collecting results (including the input×10) while change still occurs:
   Ç          call the last (1) link as a monad   [[19790],[1979],[197,199,179],[19,17,97,19,19,17,19,79],[7,7,7,7],[]]
      F     flatten                               [19790,1979,197,199,179,19,17,97,19,19,17,19,79,7,7,7,7]
       Ṫ    tail                                  7
        <8  less than 8?                          1
              (if a single digit prime was reached this will be 1
               otherwise it will be 0
               e.g. an input of 4 yields 40 at the end which is not <8)
Jonathan Allan
fuente
1
Es interesante ver dos respuestas Jelly sustancialmente diferentes. Veamos quién puede cortar el suyo más pequeño.
Lord Farquaad
2

Ruby , 72 57 + 8 = 80 65 bytes

Usa la -rprimebandera. -15 bytes de histocrat!

f=->n{n==''||n.to_i.prime?&!n.scan(/./){f[$`+$']&&break}}

Pruébalo en línea!

Tinta de valor
fuente
Puede reemplazar &&!!con solo &, convertirá el resultado en un booleano. Su llamada recursiva también puede acortarse un poco usando perlismos:!n.scan(/./){f[$`+$']&&break}}
histocrat
@histocrat Ah, sí, olvidé que en realidad no necesitaba un cortocircuito booleano para esa última parte debido a la condición inicial. ¿Sabes por qué el n.scantruco funciona como lo hace?
Value Ink
1
Sí, las dos variables globales están configuradas en la cadena a la izquierda y a la derecha de la coincidencia más reciente, por lo que al concatenarlas se obtiene la cadena menos un carácter. Dado que necesitamos un estado en cada punto de la iteración, no podemos hacer nada parecido .scan.find, pero podemos salir del ciclo manualmente en caso de éxito. Si rompemos, scanregresa nil, de lo contrario, devuelve la cadena que siempre es verdadera.
histocrat
2

Java, 220 bytes

Pruébalo en línea!

Golfizado:

boolean t(String n){int l=n.length();if(f(x->{for(int i=2;i<x;)if(x%i++==0)return 1<0;return x>1;},new Integer(n)))if(l<2)return 1>0;else for(int i=0;i<l;)if(t(n.substring(0,i)+n.substring(++i,l)))return 1>0;return 1<0;}

Sin golf:

  boolean t(String n) {
    int l = n.length();
    if (f(x -> {
      for (int i = 2; i < x;) {
        if (x % i++ == 0) {
          return 1 < 0;
        }
      }
      return x > 1;
    } , new Integer(n))) {
      if (l < 2) {
        return 1 > 0;
      }
      else {
        for (int i = 0; i < l;) {
          if (t(n.substring(0, i) + n.substring(++i, l))) {
            return 1 > 0;
          }
        }
      }
    }
    return 1 < 0;
  }

fuente
Ignora mi comentario anterior. Pero puedes boolean t(String n){int l=n.length(),x=new Integer(n),i;for(i=2;i<x;x=x%i++<1?0:x);if(x>1)if(l<2)return 1>0;else for(i=0;i<l;)if(t(n.substring(0,i)+n.substring(++i,l)))return 1>0;return 1<0;}
jugarlo
Puede guardar algunos bytes devolviendo 1 y 0 en lugar de verdadero y falso.
Nevay
@Nevay Eso funcionaría en C ++, pero no en Java. Los enteros no se pueden convertir implícitamente en booleanos.
1
No estoy seguro, pero ¿de dónde fviene?
Roman Gräf
La pregunta establece que cualquier valor puede usarse para verdadero / falso; el único lugar donde necesita un resultado booleano del método es en la última condición if (donde puede agregar >0para convertir el int a un booleano) que debería ahorrar 2 * 2 + 1 * 4 = 8 bytes en la versión de Kevin Cruijssen.
Nevay
1

05AB1E , 28 27 bytes

Solución iterativa.

¸[D0èg2‹#εæ¨D€gZQÏDpÏ}˜]p1å

Pruébalo en línea!

Explicación

¸                              # wrap input in a list
 [                             # start a loop
  D0èg2‹#                      # if the length of the first element is less than 2, break
         ε                     # apply to each element in the list
          æ                    # compute powerset
           ¨                   # remove last element (the full number)
            D€gZQÏ             # keep only the elements whose length is the max length
                  DpÏ          # keep only primes
                     }         # end apply
                      ˜        # flatten list
                       ]       # end loop
                        p1å    # is any element in the resulting list prime
Emigna
fuente
1

Python 2 , 132 124 119 bytes

-8 Gracias a @WheatWizard

-5 Gracias a @LeakyNun

p=lambda i:i>1and all(i%v for v in range(2,i))
f=lambda n:n<'0'or any(f(n[:i]+n[i+1:])for i in range(len(n)))*p(int(n))

Pruébalo en línea!

No se me ocurre nada para afinarlo sin algún corrector de primer orden incorporado. Toma el número como una cadena (supuse que esto dado que el OP permitió una lista de dígitos, pero si no, entonces +14 bytes para otra lambda), y calcula recursivamente la tortuga de cada número "torturado".

Arnold Palmer
fuente
Creo que f=lambda n,i=0:n==''or p(int(n))and i<len(n)and(f(n[:i]+n[i+1:])or f(n,i+1))guarda un byte. Alguien con mejores habilidades de golf en Python probablemente podría acortar eso aún más.
Neil
@Neil, guarda un byte, pero la frase "la misma salida para cualquier valor verdadero o falso" me impide tomarlo, ya que ingresar 1 devuelve 0 en lugar de Falso como los otros casos (debido a la comprobación de primalidad de -8) . Si el OP permite diferentes (aunque también) salidas, entonces lo cambiaría.
Arnold Palmer
1
Lo sentimos, mi sugerencia anterior no es válida. 119 bytes
Leaky Nun
1

C #, 355 bytes

namespace System{using B=Numerics.BigInteger;class A{static void Main(){Console.WriteLine(D(Console.ReadLine()));}static bool P(B x){if(x<2)return 1<0;B r=1;for(int i=1;i<=x-1;i++)r*=i;return(r+1)%x==0;}static bool D(string x){if(x.Length==0)return 1>0;bool b;if(b=P(B.Parse(x))){var n=1<0;for(int i=0;i<x.Length;i++)n|=D(x.Remove(i,1));b&=n;}return b;}}}

Pruébalo en línea!

Mi primer código de golf, así que espero haberlo hecho bien. No se me ocurrió una forma de hacerlo aún más pequeño (aparte de usar int en lugar de BigInteger, pero lo hice para que funcione para todos los casos de prueba proporcionados). De todos modos, aquí está el mismo formateado correctamente:

namespace System
{
    using B = Numerics.BigInteger;
    class A
    {
        static void Main()
        {
            Console.WriteLine(D(Console.ReadLine()));
        }

        static bool P(B x)
        {
            if (x < 2)
                return 1<0;
            B r = 1;
            for (int i = 1; i <= x - 1; i++)
                r *= i;
            return (r + 1) % x == 0;
        }

        static bool D(string x)
        {
            if (x.Length == 0)
                return 1>0;
            bool b;
            if (b = P(B.Parse(x)))
            {
                var n = 1<0;
                for (int i = 0; i < x.Length; i++)
                    n |= D(x.Remove(i, 1));
                b &= n;
            }
            return b;
        }
    }
}
Grzegorz Puławski
fuente
0

PHP , 164 bytes

function t($n){for($i=1;++$i<$n;)if($n%$i<1)return 0;if($n<10)return $n>1;foreach($r=str_split($n)as$k=>$v){$q=$r;array_splice($q,$k,1);$z|=t(join($q));}return $z;}

Pruébalo en línea!

Comienza probando el número de primalidad, luego recorre los dígitos como una matriz, saca cada uno y une el resto nuevamente y los alimenta recursivamente a través de la función nuevamente. Cada enlace hacia abajo hace un OR lógico con las rutas inferiores, solo regresa truesi existe al menos una ruta de todos los números primos.

Xanderhall
fuente
0

Javascript 167 bytes

n=>{a=[];for(i=1;i++<=n;)a.every(x=>i%x)?a.push(i):0;b=k=>(s=''+k,a.indexOf(k)>-1&&(k<10||[...s].some((x,i)=>(r=[...s],r.splice(i,1),b(~~(r.join('')))))));return b(n)}

Explicación

n=>{
    a=[];                             // create array to store primes in
    for(i=1;i++<=n;)                  // iterate from 2 to n
        a.every(x=>i%x)?a.push(i):0;  // if i % x is truthy for all x in a,
                                      // then i is prime
    b=k=>(                            // function to test is k is turtle prime
        s=''+k,                       // convert k to a string
        a.indexOf(k)>-1 && (          // if k is prime and
            k<10 ||                   // k is a single digit or
            [...s].some((x,i)=>(      // iterate over the digits of k
                                      // and check to see if, by removing each
                                      // any of the resulting numbers is turtle prime
                                      // ... is spread operator
                                      // [...s] converts string s to an array of characters 
                r=[...s],             // convert s to an array again,
                                      // importantly, this cannot be the same array
                                      // we created above, as we need to
                r.splice(i,1),        // splice out the ith element of the array
                b(~~(r.join('')))     // join the array to a string, convert to int,
                                      // and check if this number is turtle prime
                                      // ~ is bitwise negate, implicitly converts to int first before negating
                                      // ~~ negates the negation, getting us the int
            ))
        )
    );
    return b(n)
}

asgallant
fuente